Cod sursa(job #2167597)

Utilizator mihai.alphamihai craciun mihai.alpha Data 13 martie 2018 22:26:44
Problema Branza Scor 100
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 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 <ll> dq, dq1;
ll c[maxn + 5], m[maxn + 5];

int main()  {
	if(DBG)  {
		freopen("branza.in", "r", stdin);
		freopen("branza.out", "w", stdout);
	}
	ll ans = 0LL;
	R("%d%d%d", &n, &s, &t);
	for(int i = 1;i <= n;i++)  {
        R("%lld%lld", &c[i], &m[i]);
        ll sumkg = c[i] - 1LL * 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 += 1LL * m[i] * (c[dq.front()] + 1LL * (i - dq.front()) * s);
	}
	cout << ans;
	return 0;
}