Pagini recente » Cod sursa (job #270272) | Cod sursa (job #2356807) | Cod sursa (job #731594) | Cod sursa (job #36060) | Cod sursa (job #822885)
Cod sursa(job #822885)
#include <fstream>
#include <stdlib.h>
#include <algorithm>
#include <deque>
using namespace std;
ifstream fi ("branza.in");
ofstream fo ("branza.out");
const int dim = 100005;
int N, S, T, P[dim], C[dim];
long long D1, D2;
deque <int> Q;
void cit ()
{
fi >> N >> S >> T;
for (int i = 1; i <= N; i++)
{
fi >> C[i] >> P[i];
}
}
inline int cost (int i ,int j)
{
return C[j] + (i - j) * S;
}
void rez ()
{
int i;
D1 = D2 = 0;
for (i = 1; i <= N; i++)
{
while (!Q.empty() && cost(i, Q.back()) >= C[i])
Q.pop_back ();
Q.push_back (i);
if (i - Q.front() == T + 1)
Q.pop_front ();
D1 = D2 + (long long)P[i] * cost (i, Q.front());
D2 = D1;
}
}
void rezbrut ()
{
int i, j, m;
D1 = D2 = 0;
for (i = 1; i <= N; i++)
{
m = C[i];
for (j = 1; j <= T && i-j > 0; j++)
{
m = min (m, C[i-j] + j*S);
}
D1 = D2 + (long long)P[i] * m;
D2 = D1;
}
}
void afi ()
{
fo << D1 << '\n';
}
int main ()
{
cit ();
rez ();
afi ();
/*
rezbrut ();
afi ();
*/
return 0;
}