Pagini recente » Cod sursa (job #2826509) | Cod sursa (job #1896045) | Cod sursa (job #1440134) | Cod sursa (job #2394839) | Cod sursa (job #2544095)
#include <fstream>
#define K 100005
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
long long n,s,t,i,pret[K],nr,deq[K],p,u,sol,cantitate;
int main(){
fin>>n>>s>>t;
p=1; u=0;
for(i=1;i<=n;i++){
fin>>pret[i]>>cantitate;
while(p<=u && pret[i]<=pret[deq[u]]+s*(i-deq[u]))
u--;
deq[++u]=i;
if(i-deq[p]==t+1)
p++;
sol+=(pret[deq[p]]+s*(i-deq[p]))*cantitate;
}
fout<<sol;
return 0;
}
/**in ziua i pot sa vand branza produsa in ziua i, sau depozitata din zilele i-1,i-2,..,i-t+1
calculez cu un deque in care tin max t elemente care e costul minim pt un kg:
pret[ziua i], pret[ziua i-1] + s, pret[ziua i-2] + 2*s,...,pret[ziua i-k+1] + (k-1)*s */