Rezultati

Up. imeNalogaJezikRezultatČas oddaje
ASMx64-2018 Arbitraža C++ 100/100OK 13. okt '18 @ 14:29

Test Točke Porabljen spomin Porabljen čas Status
#1 11/11 3,219 MiB 0,000 s OK
#2 11/11 5,500 MiB 0,203 s OK
#3 11/11 4,074 MiB 0,075 s OK
#4 11/11 3,977 MiB 0,098 s OK
#5 11/11 3,914 MiB 0,074 s OK
#6 11/11 5,438 MiB 0,105 s OK
#7 11/11 5,434 MiB 0,141 s OK
#8 11/11 3,246 MiB 0,000 s OK
#9 12/12 3,035 MiB 0,000 s OK

Ocenjevani program (petaPanterskaNaloga.cpp):
//#define DEBUG

#ifdef DEBUG
#include <fstream>
#else
#include <iostream>
#endif

#include <queue>
#include <vector>
#include <string>
#include <map>
#include <algorithm>
#include <cstring>
using namespace std;

#ifdef DEBUG
ifstream cin("input");
ofstream cout("output");
#endif
#define SIZE 100002

int numP, numS, steviloArg;
unsigned long long int sumKrat[SIZE];
unsigned long long int sumP[SIZE];
unsigned long long int sumS[SIZE];

bool compare(unsigned long long int a, unsigned long long int b){
return a > b;
}

unsigned long long int resi(int s, int p){
    unsigned long long int rez = 0;

    if(min(s, p) > 0)
        rez += sumKrat[min(s, p) - 1];

    if(s > p){
        if(p > 0)
            rez += sumS[s - 1] - sumS[p - 1];
        else rez += sumS[s - 1];
    }
    else if(p > s){
        if(s > 0)
            rez += sumP[p - 1] - sumP[s - 1];
        else
            rez += sumP[p - 1];
    }

    return (unsigned long long int)max(s, p) * rez;
}

int main()
{
    cin >> numP >> numS >> steviloArg;

    for(int i = 0; i < numP; ++i)
        cin >> sumP[i];

    for(int i = 0; i < numS; ++i)
        cin >> sumS[i];

    sort(sumP, sumP + numP, compare);
    sort(sumS, sumS + numS, compare);


    int mmin = min(numS, numP);
    sumKrat[0] = sumS[0] * sumP[0];

    for(int i = 1; i < mmin; ++i)
        sumKrat[i] = sumKrat[i - 1] + sumP[i] * sumS[i];

    for(int i = 1; i < numP; ++i)
        sumP[i] += sumP[i - 1];

    for(int i = 1; i < numS; ++i)
        sumS[i] += sumS[i - 1];
/*
    for(int i = 0; i < mmin; ++i)
        cout << sumKrat[i] << ' ';
        cout << endl;

    for(int i = 0; i < numP; ++i)
        cout << sumP[i] << ' ';
        cout << endl;


    for(int i = 0; i < numS; ++i)
        cout << sumS[i] << ' ';
        cout << endl;

*/
    if(numS + numP <= steviloArg){
        cout << resi(numS, numP);
        return 0;
    }

    int s = min(steviloArg, numS);
    int p = steviloArg - s;

    int temps, tempp;

    unsigned long long int res = 0;
    unsigned long long int curr;
    while(p <= steviloArg && p <= numP){
        curr = resi(s, p);
        /*
        if(curr > res){
            temps = s;
            tempp = p;
        }
        */

        res = max(res, curr);
        p++;
        if(s == 0) break;
        s--;
    }
    cout /*<< temps << ' ' << tempp << ' ' */<< res;

    return 0;
}