Cod sursa(job #2034736)

Utilizator Garen456Paun Tudor Garen456 Data 8 octombrie 2017 13:21:37
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.62 kb
#include <fstream>

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

int main()
{  long long i,fr,bc;
    fin>>n>>s>>t;
  ++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++;
        // fout<<P[i]*C[d[fr]]+P[i]*(i-d[fr])*s<<"\n";
        sum+=P[i]*C[d[fr]]+P[i]*(i-d[fr])*s;
    }

    fout<<sum;
    return 0;
}