Cod sursa(job #1970556)

Utilizator danstefanDamian Dan Stefan danstefan Data 19 aprilie 2017 14:03:36
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <bits/stdc++.h>
using namespace std;
int n,s,t,i,ans,j;
deque<int>dq;
pair<int,int>v[100010];
int main()
{
    ifstream f ("branza.in");
    ofstream g ("branza.out");
    f>>n>>s>>t;
    dq.push_back(1);
    for(i=1; i<=n; ++i)
        f>>v[i].first>>v[i].second;
    ans=v[1].first*v[1].second;
    for(i=2; i<=n; ++i)
    {
        while(!dq.empty()&&(i-dq.back())*s+v[dq.back()].first>v[i].first)dq.pop_back();
        dq.push_back(i);
        while(!dq.empty()&&(i-dq.front())>t)dq.pop_front();
        j=dq.front();
        ans+=((i-dq.front())*s+v[dq.front()].first)*v[i].second;
    }
    g<<ans<<'\n';
    return 0;
}