Cod sursa(job #2063827)

Utilizator Argint_TheodoraArgint Maria Theodora Argint_Theodora Data 11 noiembrie 2017 15:23:37
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <fstream>

using namespace std;

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

int v[100000],d[100000],C[100000];

int main()
{
    long long sum=0,s;
    int st=0,dr=-1,n,k;
    in>>n>>s>>k;
    k++;
    for(int i=0; i<n; i++)
    {
        in>>C[i]>>v[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;
        //out << d[st] << " " << C[d[st]] << "\n";
        sum += v[i]*(C[d[st]] + (long long)s*(i-d[st]));

    }
    out<<sum;
    return 0;
}