Pagini recente » Cod sursa (job #593924) | Cod sursa (job #2337368) | Cod sursa (job #716502) | Cod sursa (job #1750817) | Cod sursa (job #2884898)
#include<bits/stdc++.h>
using namespace std;
ifstream f("branza.in"); ofstream g("branza.out");
const long long MAX_N = 100000;
struct Index
{ long long val,index; };
long long n,s,t,c[1 + MAX_N],p[1 + MAX_N];
deque<Index> dq;
long long back_cost(long long i)
{ return 1LL * p[i + 1] * (dq.back().val + (i + 1 - dq.back().index) * s); }
int main()
{ f>>n>>s>>t;
for (long long i = 1; i <= n; i++) f>>c[i]>>p[i];
long long ans;
ans = 1LL * p[1] * c[1];
dq.push_back({c[1], 1});
for (long long i = 2; i <= n; i++)
{ ans += min(1LL * p[i] * c[i], 1LL * p[i] * (dq.front().val + (i - dq.front().index) * s));
if (i < n)
{ long long iCost = 1LL * p[i + 1] * (c[i] + s);
while (dq.size() > 0 && iCost <= back_cost(i)) dq.pop_back();
dq.push_back({c[i], i});
while (i - dq.front().index + 1 > t) dq.pop_front();
}
}
g<<ans;
return 0;
}