Cod sursa(job #964310)

Utilizator costinbanuCostin Banu costinbanu Data 20 iunie 2013 16:09:35
Problema Lupul Urias si Rau Scor 8
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

vector < pair < int, int > > oi; //dist, lana
vector < pair < int, int > > rez; //lana, indicele

inline bool cmp (pair <int, int> a, pair <int, int> b){
    return (a.first == b.first) ? (a.second > b.second) : (a.first > b.first);
}

int n, x, l, d;
long long sum;

int main(){
    FILE *in = fopen("lupu.in", "r"), *out = fopen("lupu.out", "w");
    if (in && out) {
        int a, b, j;
        fscanf(in, "%d %d %d\n", &n, &x, &l);
        for (int i = 0; i < n; i++){
            fscanf(in, "%d %d\n", &a, &b);
            oi.push_back(pair<int,int>(a,b));
        }
        sort(oi.begin(), oi.end(), cmp);
        a = oi[0].first;
        rez.push_back(pair < int, int > (oi[0].second, 0));
        for (int i = 1; i < n; i++){
            if (oi[i].first != a) {
                rez.push_back(pair < int, int > (oi[i].second,i));
                sort(rez.begin(), rez.end());
                j = rez.size()-1;
                while(j >= 0 && oi[rez[j].second].first + d > x)  j--;
                if (j >= 0) {
                    sum += rez[j].first;
                    rez.erase(rez.begin()+j);
                    a = oi[i].first;
                    d += l;
                }
            }
            else {
                rez.push_back(pair < int, int > (oi[0].second,i));
            }
        }
        sort(rez.begin(), rez.end());
        for (j = rez.size()-1; j >= 0; j--){
            if (oi[rez[j].second].first + d > x) continue;
            sum += rez[j].first;
            rez.erase(rez.begin()+j);
            d += l;
        }
        fprintf(out, "%lld", sum);
        fclose(in), fclose(out);
    }
    return 0;
}