Cod sursa(job #2546495)

Utilizator mihnea03Ciocioiu Mihnea mihnea03 Data 14 februarie 2020 11:08:30
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <fstream>
#define dim 100010
using namespace std;
pair <long long,long long> a[dim];///a[i].first=costul in ziua i
long long d[dim];           ///a[i].second=cantitatea din ziua i
long long i,n,m,p,u,s,t,sol;

long long cost (long long i,long long j) {
    return a[j].first+(i-j)*s;
}

int main() {
    ifstream fin("branza.in");
    ofstream fout("branza.out");
    fin>>n>>s>>t;       ///fac un deque de lungime t
                        ///fiecarui element ii creste costul cu (i-d[u])*s
    for (i=1;i<=n;i++) {
        fin>>a[i].first>>a[i].second;
    }
    p=1;
    for (i=1;i<=n;i++) {
        while (p<=u&&a[i].first<=cost(i,d[u])) u--;
        d[++u]=i;
        if (i-d[p]==t+1) p++;
        long long costt=cost(i,d[p])*a[i].second;
        sol+=costt;
    }
    fout<<sol;
    return 0;
}