Cod sursa(job #2167592)

Utilizator mihai.alphamihai craciun mihai.alpha Data 13 martie 2018 22:24:18
Problema Branza Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.1 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 iFor(i, j, n)for(int i = n;i >= j;i--)
#define R scanf
#define S scanf
#define P printf
#define fin stdin
#define fout stdout

#define DBG 1

const int maxn = 1e5;

int n, s, t;
deque <int> dq, dq1;
int c[maxn + 5], m[maxn + 5];

int main()  {
	if(DBG)  {
		freopen("branza.in", "r", stdin);
		freopen("branza.out", "w", stdout);
	}
	ll ans = 0LL;
	cin >> n >> s >> t;
	for(int i = 1;i <= n;i++)  {
        cin >> c[i] >> m[i];
        ll sumkg = c[i] - s * i;
        while(!dq.empty() && i - dq.front() > t)
            dq.pop_front(), dq1.pop_front();
        while(!dq.empty() && sumkg <= dq1.back())
            dq.pop_back(), dq1.pop_back();
        dq.push_back(i);
        dq1.push_back(sumkg);
        ans += m[i] * (c[dq.front()] + (i - dq.front()) * s);
	}
	cout << ans;
	return 0;
}