Pagini recente » Cod sursa (job #1164058) | Cod sursa (job #956923) | Cod sursa (job #261265) | Cod sursa (job #2593310) | Cod sursa (job #68523)
Cod sursa(job #68523)
#include <cstdio>
#include <set>
#define MAX_N 100001
using namespace std;
long long N, S, T;
long long C[MAX_N], P[MAX_N], SUM[MAX_N], CM[MAX_N];
void Read();
void Dynamics();
void Print();
multiset <long long> Q;
int main()
{
Read();
Dynamics();
Print();
return 0;
}
void Read()
{
FILE *f = fopen("branza.in", "rt");
long long i;
for(fscanf(f, "%lld %lld %lld", &N, &S, &T), i=1; i<=N; ++i)
{
fscanf(f, "%lld %lld", C+i, P+i);
SUM[i] = SUM[i-1] + P[i];
}
fclose(f);
}
void Dynamics()
{
long long i, j, c, d;
CM[1] = C[1] * P[1];
for(i=2; i<=N; ++i)
{
Q.insert(C[i]);
if(i > T + 1) Q.erase(C[i-T]);
CM[i] = CM[i-1] + (C[i] * P[i]);
d = 0;
for(j=i-1; j>=((i-T)>=1?(i-T):1); --j)
{
d += SUM[i] - SUM[j];
c = C[j] * (SUM[i] - SUM[j-1]) + d * S;
if(CM[i] > c + CM[j-1])
CM[i] = c + CM[j-1];
if(C[j] == *Q.begin())
break;
}
}
}
void Print()
{
FILE *g = fopen("branza.out", "wt");
fprintf(g, "%lld", CM[N]);
fclose(g);
}