Cod sursa(job #359014)

Utilizator vladiiIonescu Vlad vladii Data 25 octombrie 2009 14:19:28
Problema Lupul Urias si Rau Scor 16
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
#include <iostream>
#include <fstream>
#include <deque>
#include <algorithm>
using namespace std;
int main() {
    fstream f1, f2;
    long long int n, x, l, i, j, k, elem, cost, vecs[100000], vecf[100000], suma=0, p=0, ok=1;
    deque<pair<long long int, long long int> > deq;
    f1.open("lupu.in", ios::in);
    f1>>n>>x>>l;
    f1>>elem>>cost;
    deq.push_front(make_pair(elem, cost));
    for(i=1; i<n; i++) {
             f1>>elem>>cost;
             j=0;
             for(deque<pair<long long int, long long int> >::iterator it=deq.begin(); it!=deq.end(); it++) {
                                 if(cost<(*it).second) {
                                                       j++;
                                 }
                                 else { break; }
             }
             for(k=0; k<j; k++) {
                      vecs[k]=deq.front().first;
                      vecf[k]=deq.front().second;
                      deq.pop_front();
             }
             deq.push_front(make_pair(elem, cost));
             for(k=j-1; k>=0; k--) {
                        deq.push_front(make_pair(vecs[k], vecf[k]));
             }
    }
    f1.close();
    //deq.erase (deq.begin()+5) -> sterge al 5-lea element
    p=0; ok=0;
    while(!ok) {
         j=0; ok=1;
         for(deque<pair<long long int, long long int> >::iterator it=deq.begin(); it!=deq.end(); it++) {
                        if((*it).first+p+l<=x) {
                                              j++;
                        }
                        else {
                             if((*it).first+p<=x) {
                                  ok=0;
                                  p+=l;
                                  suma+=(*it).second;
                                  deq.erase(deq.begin()+j);
                                  break;
                             }
                        }
         }
    }                                         
    f2.open("lupu.out", ios::out);
    f2<<suma<<endl;
    f2.close();
    return 0;
}