Cod sursa(job #2046224)

Utilizator sabinantonSabin Anton sabinanton Data 23 octombrie 2017 16:29:08
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include <bits/stdc++.h>

using namespace std;

const int N = 5000001;

ifstream fin("branza.in");
ofstream fout("branza.out");

long long n,m,i,j,st,s,t,dr = -1,s1,d[1000001];
pair <int,int> v[1000001];

int main()
{
    fin>>n>>s>>t;
    for(i=1;i<=n;i++)
    {
        fin>>v[i].second>>v[i].first;
        if(st<=dr && d[st]==i-t)
            st++;
        while(st <= dr && v[i].second <= v[d[dr]].second + s*(i-d[dr]))
        {
            dr--;
        }
       // cout << d[st] << " ";
        d[++dr]=i;
        s1 += v[i].first*(v[d[st]].second+s*(i-d[st]));
    }
    fout<<s1;
    return 0;
}