Pagini recente » Cod sursa (job #2123248) | Cod sursa (job #296823) | Cod sursa (job #2273219) | Cod sursa (job #2458888) | Cod sursa (job #2148069)
#include <fstream>
#define nmax 100005
using namespace std;
fstream f1("branza.in", ios::in);
fstream f2("branza.out", ios::out);
///eficient ori sa produci ori sa iei din depozit
int n, t, coada[nmax], prim=1, ultim;
long long rez, cost[nmax], cant[nmax], s;
void citire()
{
int i;
f1>>n>>s>>t;
for(i=1; i<=n; i++)
f1>>cost[i]>>cant[i];
}
long long minim(long long a, long long b)
{
return (a< b? a: b);
}
void solutie()
{
int i; ///ordinea relativa di deque se pastreaza cu trecerea saptamanilor (toate cresc cu s)
for(i=1; i<=n; i++)
{
if((prim<=ultim)&&(coada[prim]==i-t-1)) prim++;
if(prim<=ultim) rez+=minim(cost[i], cost[coada[prim]]+ s*(i-coada[prim]))*cant[i];
else rez+=cost[i]*cant[i];
while((prim<=ultim)&&(cost[coada[ultim]]+ s*(i-coada[ultim]) > cost[i])) ultim--;
ultim++;coada[ultim]=i;
}
f2<<rez;
}
int main()
{
citire();
solutie();
return 0;
}