Cod sursa(job #2546493)

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

int cost (int i,int 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++;
        int costt=cost(i,d[p])*a[i].second;
        sol+=costt;
    }
    fout<<sol;
    return 0;
}