Pagini recente » Cod sursa (job #2555048) | Cod sursa (job #448208) | Cod sursa (job #1467739) | Cod sursa (job #2662771) | Cod sursa (job #1980484)
#include <cstdio>
#include <algorithm>
#include <deque>
struct saptamana
{
int cerere,pret;
};
const int NMAX=100001,INF=(1ll<<31)-1;
saptamana v[NMAX];
std::deque<int> dcoada;
void Adauga(int pos,int s)
{
if(dcoada.empty())
{
dcoada.push_back(pos);
return;
}
while(!dcoada.empty() && v[dcoada.back()].pret+(pos-dcoada.back())*s>v[pos].pret)
{
dcoada.pop_back();
}
dcoada.push_back(pos);
}
void Sterge(int pos,int t)
{
while(!dcoada.empty() && dcoada.front()<=pos-t)
dcoada.pop_front();
}
int main()
{
FILE *in=fopen("branza.in","r");
int n,s,t;
fscanf(in,"%d %d %d ",&n,&s,&t);
for(int i=1;i<=n;i++)
{
fscanf(in,"%d %d ",&v[i].pret,&v[i].cerere);
}
fclose(in);
int rasp=0;
for(int i=1;i<=n;i++)
{
Adauga(i,s);
Sterge(i,t);
int pret=v[dcoada.front()].pret+(i-dcoada.front())*s;
rasp+=v[i].cerere*pret;
}
FILE *out=fopen("branza.out","w");
fprintf(out,"%d\n",rasp);
fclose(out);
return 0;
}