Pagini recente » Cod sursa (job #2798888) | Cod sursa (job #2554207) | Cod sursa (job #3273504) | Cod sursa (job #369505) | Cod sursa (job #2727190)
#include <fstream>
#define NMax 100001
int main()
{
std::ifstream f("branza.in");
int N, S, T, P;
long long Cost;
int Deq[NMax], Costuri[NMax];
int Front = 0, Back = 0;
f >> N >> S >> T;
f >> Costuri[0] >> P;
Cost = 1LL * Costuri[0] * P;
Deq[0] = 0;
for(int i = 1; i < N; ++i)
{
f >> Costuri[i] >> P;
while(Front <= Back && Costuri[i] <= 1LL * Costuri[Deq[Back]] + 1LL * (i - Deq[Back]) * S)
--Back;
Deq[++Back] = i;
if(i - Deq[Front] > T)
++Front;
Cost += 1LL * Costuri[Deq[Front]] * P + 1LL * (i - Deq[Front]) * S * P;
}
std::ofstream g("branza.out");
g << Cost;
return 0;
}