Cod sursa(job #1940885)

Utilizator RaduXD1Nicolae Radu RaduXD1 Data 26 martie 2017 21:00:51
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.59 kb
#include<vector>
#include<fstream>

using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
int c[100002],p[100002],d[100002];
int n,s,t,i,st,dr;
long long b;

int main()
{
    fin>>n>>s>>t;
    for(i=1;i<=n;i++)
        fin>>c[i]>>p[i];
    st=1;
    dr=1;d[1]=1;
    b+=c[1]*p[1];
    for(i=2;i<=n;i++)
    {
        while(st<=dr&&c[i]<=(i-d[dr])*s+c[d[dr]])
            dr--;
        d[++dr]=i;
        if(i-d[st]==t+1)
            st++;
        b+=(c[d[st]]+s*(i-d[st]))*p[i];
    }
    fout<<b;
    fin.close();
    fout.close();
    return 0;
}