Cod sursa(job #1135283)

Utilizator ELHoriaHoria Cretescu ELHoria Data 7 martie 2014 17:02:41
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <fstream>
#include <algorithm>
#include <functional>

using namespace std;

int main()
{

    ifstream cin("lupu.in");
    ofstream cout("lupu.out");
    int n, x ,l;
    cin >> n >> x >> l;
    int d, a;
    long long ret = 0;
    vector< vector<int> > sheep(n,vector<int>());
    vector<int> bst(n,0);
    for (int i = 0; i < n; i++) {
        cin >> d >> a;
        if (d > x) continue;
        int steps = (x - d) / l;
        if (steps >= n) {
            ret += a; 
        } else {
            sheep[steps].push_back(a);
        }
    }

    for (int i = 0; i < n; i++) {
        sort (sheep[i].begin(),sheep[i].end(),greater<int>());
        for (int  k = 0;k < (int)sheep[i].size() && i - k >= 0; k++) {
            bst[i - k] = max(bst[i - k],sheep[i][k]);
        }
    }

    for (int i = 0;i < n;i++) {
        ret += bst[i];
    }


    cout << ret << "\n";
    return 0;
}