Cod sursa(job #2060755)

Utilizator syndicat3albu alex syndicat3 Data 8 noiembrie 2017 18:06:37
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.58 kb
#include <iostream>
#include <fstream>
using namespace std;

int main()
{
    int i, n, t, s, st, dr, c[100000], p[100000], d[100000];
    long long sum=0;
    ifstream f ("branza.in");
    ofstream g ("branza.out");
    f>>n>>s>>t;
    t++;
    for (i=0; i<n; i++) f>>c[i]>>p[i];
    st=0;
    dr=-1;
    for (i=0; i<n; i++)
    {
        if (st<=dr && d[st]==i-t)
        {
            st++;
        }
        while (st<=dr && c[i]<=c[d[dr]]+s*(i-d[dr]))
        {
            dr--;
        }
        d[++dr]=i;
        sum += p * (c[d[st]] + s*(i - d[st]));
    }

    g<<sum;
    return 0;
}