Cod sursa(job #2288433)

Utilizator mariusgrafuMarius Grafu mariusgrafu Data 23 noiembrie 2018 13:39:59
Problema Lupul Urias si Rau Scor 8
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.84 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

struct oaie {
    int d, a;

    oaie(int _d = 0, int _a = 0) {
        d = _d;
        a = _a;
    }

    friend ostream& operator<<(ostream& out, oaie& o) {
        out << "d: " << o.d << " a: " << o.a;
        return out;
    }
};

int strangeLana(int X, int L, vector<oaie> O) {
    sort(O.begin(), O.end(), [](oaie a, oaie b){
         return a.d > b.d;
         });
    int lana = 0;
    int upperLimit = X;
    //int lowerLimit = X - L;

    do {
        //cout << "(" << lowerLimit << ", " << upperLimit << "]\n";
        /*for(int i = 0; i < O.size(); ++i) {
        cout << O[i] << "\n";
        }*/
        int maxL = 0, maxLindex = 0;
        int last = -1;
        for(int i = 0; i < O.size(); ++i) {
            if(O[i].d > upperLimit - L) {last = i;}
            if(O[i].d > upperLimit) { continue;}
            //if(O[i].d <= lowerLimit) break;
            if(O[i].a > maxL) {
                maxL = O[i].a;
                maxLindex = i;
            }
            //cout << O[i] << "\n";
        }
        //cout << "best: " << O[maxLindex] << "\n";
        lana += maxL;
        O.erase(O.begin() + maxLindex);

        if(maxLindex <= last) last--;
        if(!last) O.erase(O.begin());
        else if(last != -1) O.erase(O.begin(), O.begin() + last);

        upperLimit -= L;
        //lowerLimit -= L;
    }while(upperLimit >= 0);

    return lana;
}

int main()
{
    ifstream in("lupu.in");
    ofstream out("lupu.out");

    int N, X, L;
    vector<oaie> O;

    in >> N >> X >> L;

    for(int i = 0; i < N; ++i) {
        int d, a;
        in >> d >> a;
        O.push_back(oaie(d, a));
    }

    out << strangeLana(X, L, O);

    in.close(); out.close();
    return 0;
}