Pagini recente » Cod sursa (job #2543719) | Cod sursa (job #3220116) | Cod sursa (job #3214673) | Cod sursa (job #2493362) | Cod sursa (job #1980490)
#include <cstdio>
#include <algorithm>
#include <deque>
struct saptamana
{
long long cerere,pret;
};
const long long NMAX=100001,INF=(1ll<<31)-1;
saptamana v[NMAX];
std::deque<long long> dcoada;
void Adauga(long long pos,long long 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(long long pos,long long t)
{
while(!dcoada.empty() && dcoada.front()<pos-t)
dcoada.pop_front();
}
int main()
{
FILE *in=fopen("branza.in","r");
long long n,s,t;
fscanf(in,"%lld %lld %lld ",&n,&s,&t);
//t--;
for(long long i=1;i<=n;i++)
{
fscanf(in,"%lld %lld ",&v[i].pret,&v[i].cerere);
}
fclose(in);
long long rasp=0;
for(long long i=1;i<=n;i++)
{
Adauga(i,s);
Sterge(i,t);
long long pret=v[dcoada.front()].pret+(i-dcoada.front())*s;
rasp+=v[i].cerere*pret;
}
FILE *out=fopen("branza.out","w");
fprintf(out,"%lld\n",rasp);
fclose(out);
return 0;
}