Cod sursa(job #2340052)

Utilizator AlexiaAndreea16Alexia Paunescu AlexiaAndreea16 Data 9 februarie 2019 18:28:25
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.66 kb
#include <fstream>
#include <deque>
#define DIM 100005
#define ll long long
using namespace std;
ll cnt[DIM],best[DIM],p[DIM];
deque <ll> Min;
int main()
{   ll n,t,s,i,sol=0;
    ifstream f("branza.in");
    ofstream g("branza.out");
    f>>n>>s>>t;
    for (i=1;i<=n;++i)
        f>>p[i]>>cnt[i];

    for (i=1;i<=n;++i) {
        while (!Min.empty() && p[i]+s*(n-i)<p[Min.back()]+s*(n-Min.back()))
            Min.pop_back();
        Min.push_back(i);
        ll j=Min.front();
        best[i]=p[j]+s*(i-j);
        if (i-t==Min.front()) Min.pop_front();
    }

    for (i=1;i<=n;++i)
        sol+=cnt[i]*best[i];
    g<<sol;
    return 0;
}