Cod sursa(job #2089506)

Utilizator mihai.alphamihai craciun mihai.alpha Data 16 decembrie 2017 17:33:52
Problema Branza Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.12 kb
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define VI vector<int>
#define PII pair<int,int>
#define PDD pair<double,double>
#define ll long long
#define lf double
#define pb push_back
#define For(i, j, n)for(int i = j;i <= n;i++)
#define R scanf
#define S scanf
#define P printf

#define DBG 1

int n, s, t;

const int maxn = 1e5;
int c, p[maxn + 1];
ll d[maxn + 1];
deque <pair <ll, int> > dq;

int main()  {
	if(DBG)  {
		freopen("branza.in", "r", stdin);
		freopen("branza.out", "w", stdout);
	}
	S("%d%d%d", &n, &s, &t);
	For(i, 1, n)  {
        S("%d%d", &c, &p[i]);
        long long aa = 1LL * c + 1LL * (n - i) * s;
        while(dq.size() && i - dq.front().se >= t)
            dq.pop_front();
        while(dq.size() && aa <= dq.back().fi)
            dq.pop_back();
        if(dq.size() == 0)
            d[i] = 1LL * c;
        else
            d[i] = 1LL * d[dq.front().se] + 1LL * (i - dq.front().se) * s;
        dq.push_back({aa, i});
	}
	long long ans = 0LL;
	For(i, 1, n)
        ans += 1LL * d[i] * p[i];
    P("%lld", ans);
	return 0;
}