Pagini recente » Cod sursa (job #1962732) | Cod sursa (job #1738112) | Cod sursa (job #593289) | Cod sursa (job #442364) | Cod sursa (job #547072)
Cod sursa(job #547072)
#include <fstream>
#include <deque>
using namespace std;
const int N = 100005;
ifstream fin("branza.in");
ofstream fout("branza.out");
struct week{
int cost, req;
} w[N];
int n,t,s;
long long best;
deque<int> deq;
void read(){
int i;
fin>>n>>s>>t;
for (i=1; i<=n; i++)
fin>>w[i].cost>>w[i].req;
}
void solve(){
int 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);
while (!deq.empty() && deq.front() <= i-t ) deq.pop_front();
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;
}
}
void printRez(){
fout<<best;
}
int main(){
read();
solve();
printRez();
return 0;
}