Cod sursa(job #2052889)

Utilizator DovlecelBostan Andrei Dovlecel Data 31 octombrie 2017 10:06:13
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include <fstream>
#include <iostream>
using namespace std;
long long p[100001],c[100001],d[100001],sum;
int main()
{
    int n,s,k,dr,st,i;
    ifstream f("branza.in");
    f>>n>>s>>k;
    k++;
    for(i=0;i<n;i++)
        f>>c[i]>>p[i];
    f.close();
    st=0;
    dr=-1;
    for(i=0;i<n;i++)
    {
        if(st<=dr && d[st]==i-k)
            st++;
        while(st<=dr && c[i]<=c[d[dr]]+s*(i-d[dr]))
            dr--;
        d[++dr]=i;
        sum=sum+c[d[st]]*p[i]+s*(i-d[st])*p[i];
    }
    ofstream g("branza.out");
    g<<sum;
    g.close();
    return 0;
}