Cod sursa(job #1970560)

Utilizator danstefanDamian Dan Stefan danstefan Data 19 aprilie 2017 14:06:21
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.67 kb
#include <bits/stdc++.h>
using namespace std;
long long n,s,t,i,ans,j;
deque<long long>dq;
pair<long long,long long>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;
}