Cod sursa(job #2731690)

Utilizator redikusTiganus Alexandru redikus Data 28 martie 2021 01:54:38
Problema Branza Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("branza.in");
ofstream cout("branza.out");

int main(){

    long long n, s, t, i, x, f, y;
    vector<pair<long long, long long>> a;
    queue<long long> q;
    cin>>n>>s>>t;
    long long v=0;
    long long su=0;
    for(i=0;i<n;i++){
        cin>>x>>y;
        a.push_back(pair<long long,long long>(x,y));
        v=a[i].first;
        while(q.empty()==0 && i-q.front()>=t){
            q.pop();
        }
        while(q.empty()==0 && a[i].first<=a[q.front()].first+(i-q.front())*s){
            q.pop();
        }
        if(q.empty()==1){
            su+=v*a[i].second;
        }
        else{
            for(long long j=q.front(); j<i;j++){
                f=a[j].first+(i-j)*s;
                if(v>f){
                    v=f;
                }
            }
            su+=v*a[i].second;
        }
        q.push(i);
//        while(i+j>0 && -j<t){
//            f=a[i+j].first*a[i].second+a[i].second*(-j)*s;
//            if(v>f){
//                v=f;
//            }
//            j--;
//        }
//        su+=v;
    }
    cout<<su;
}