Cod sursa(job #2034732)

Utilizator Garen456Paun Tudor Garen456 Data 8 octombrie 2017 13:18:20
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.54 kb
#include <fstream>

using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
int n,s,t;
int C[100005],P[100005];
int d[100005];

int main()
{  int i,fr,bc;
    fin>>n>>s>>t;

    for(i=1;i<=n;++i)
     fin>>C[i]>>P[i];

    fr=1; bc=0;
    long long sum=0;
    for(i=1;i<=n;++i)
    {
        while(fr<=bc && C[i]*P[i] <=  P[i]*C[d[bc]]+P[i]*(i-d[bc])*s   ) --bc;
       d[++bc]=i;

       if(d[fr]==i-t)
         fr++;
        sum+=P[i]*C[d[fr]]+P[i]*(i-d[fr])*s;
    }

    fout<<sum;
    return 0;
}