Cod sursa(job #1821841)

Utilizator AndreidgDragomir Andrei Valentin Andreidg Data 3 decembrie 2016 18:54:54
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1 kb
#include <fstream>
#include <deque>
const int N=100005;
using namespace std;
ofstream g("branza.out");
deque <long long> q;
int n,s,t;
int cost_Min=0;
long long c[N],p[N];

void citire(){

    ifstream f("branza.in");
    f>>n>>s>>t;
    for(int i=1;i<=n;i++){

        f>>c[i]>>p[i];

    }
    f.close();
}

bool verif(int j,int i){

    if(((i-j)*s+c[j])<c[i]){
        return false;
    }
    else{
        return true;
    }
}
void rezolvare(){

    q.push_back(1);
    //ofstream g("branza.out");
    for(int i=1; i<=n;i++){

        while(!q.empty()&&verif(q.back(),i)){
            q.pop_back();
        }
        q.push_back(i);

        while(!q.empty()&&(i-q.front()>t)){
            q.pop_front();
        }
         int j=q.front();
         //int v=((i-j)*s+c[j])*p[i];g<<v<<" ";
         cost_Min+=((i-j)*s+c[j])*p[i];
    }
    ofstream g("branza.out");
    g<<cost_Min;g.close();
}

int main()
{
    citire();
    rezolvare();
    return 0;
}