Pagini recente » Cod sursa (job #3323327) | Cod sursa (job #2694886) | Cod sursa (job #1477972) | Cod sursa (job #3336176) | Cod sursa (job #3337378)
#include <bits/stdc++.h>
using namespace std;
ifstream f("branza.in");
ofstream g("branza.out");
const int nmax=1e7+5;
int n,s,t,c[nmax],p[nmax];
int main()
{
f >> n >> s >> t;
for (int i=1; i<=n; i++ )
f >> c[i] >> p[i];
// intrebarea fiecarei saptamani este:
// daca vindem un produs mai tarziu decat trebuia (initial sapt era i, dar vindem in sapt j
// costul per kg devine: c[i]+s*(j-i)=c[i]+s*j+s*i //costul lui + cost de depozistare
// pt o sapt fixa j, tb sa alegem i din (j-t,j), astfel incat sa minimizam costul per kg
deque <int> dq;
int ans=0;
for (int j=1; j<=n; j++ )
{
while ( !dq.empty() && (j-dq.front())>t )
dq.pop_front();
while ( !dq.empty() && c[j]<=c[dq.back()]+s*(j-dq.back()) )
dq.pop_back();
dq.push_back(j);
ans+=p[j]*c[dq.front()]+s*p[j]*(j-dq.front());
}
g << ans;
return 0;
}