Cod sursa(job #2731684)

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

int main(){

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