Pagini recente » Cod sursa (job #1685412) | Cod sursa (job #1299845) | Cod sursa (job #333379) | Cod sursa (job #2955714) | Cod sursa (job #547110)
Cod sursa(job #547110)
#include <fstream>
#include <deque>
using namespace std;
const int N = 100105;
ifstream fin("branza.in");
ofstream fout("branza.out");
struct week{
long long cost, req;
} w[N];
long long n,t,s,best;
deque<long long> deq;
void read(){
long long i;
fin>>n>>s>>t;
for (i=1; i<=n; i++)
fin>>w[i].cost>>w[i].req;
}
void solve(){
long long i;
best = 0;
for (i=1; i<=n; i++){
while (!deq.empty() && w[deq.back()].cost + s*(n - deq.back()) >= w[i].cost + s*(n-i) ) deq.pop_back();
deq.push_back(i);
if (w[i].cost * w[i].req > w[i].req * ( w[deq.front()].cost + s*(i-deq.front()) ))
best += w[i].req * ( w[deq.front()].cost + s*(i-deq.front()) );
else
best += w[i].cost * w[i].req;
while (!deq.empty() && deq.front() <= i-t ) deq.pop_front();
}
}
void printRez(){
fout<<best;
}
int main(){
read();
solve();
printRez();
return 0;
}