Pagini recente » Cod sursa (job #1927163) | Cod sursa (job #3230661) | Cod sursa (job #2850478) | Cod sursa (job #2778513) | Cod sursa (job #67573)
Cod sursa(job #67573)
#include <cstdio>
#include <set>
#define MAX_N 100001
using namespace std;
int N, S, T;
int C[MAX_N], P[MAX_N], SUM[MAX_N];
long long unsigned CM[MAX_N];
void Read();
void Dynamics();
void Print();
multiset <int> Q;
int main()
{
Read();
Dynamics();
Print();
return 0;
}
void Read()
{
FILE *f = fopen("branza.in", "rt");
int i;
for(fscanf(f, "%d %d %d", &N, &S, &T), i=1; i<=N; ++i)
{
fscanf(f, "%d %d", C+i, P+i);
SUM[i] = SUM[i-1] + P[i];
}
fclose(f);
}
void Dynamics()
{
int i, j;
long long unsigned c, d;
CM[1] = C[1] * P[1];
for(i=2; i<=N; ++i)
{
d = 0;
Q.insert(C[i]);
if(i > T + 1)
Q.erase(C[i-T]);
CM[i] = CM[i-1] + (C[i] * P[i]);
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, "%llu", CM[N]);
fclose(g);
}