Pagini recente » Cod sursa (job #1672047) | Cod sursa (job #882234) | Cod sursa (job #2217556) | Cod sursa (job #39650) | Cod sursa (job #1392848)
#include <fstream>
#define NMax 100010
#define INF (1<<31)-1;
using namespace std;
ifstream f("branza.in");
ofstream g("branza.out");
int n, s, t, p, u;
long long d[NMax];
struct mdeque
{
int pos;
int val;
}deq[NMax];
struct branza
{
int c;
int p;
}b[NMax];
int getmin(int a, int b)
{
if (a < b)
return a;
return b;
}
int getmax(int a, int b)
{
if (a > b)
return a;
return b;
}
int main()
{
f >> n >> s >> t;
for (int i = 1; i <= n; i++)
f >> b[i].c >> b[i].p;
/*for (int i = 1; i <= n; i++) {
d[i] = d[i - 1];
long long cmin = INF;
for (int sapt = i; sapt >= getmax(1, i - t); sapt--)
cmin = getmin(cmin, 1LL * b[sapt].c + (i - sapt) * s);
d[i] += cmin * b[i].p;
}*/
deq[p].val = b[1].c - s;
for (int i = 1; i <= n; i++) {
while (i - deq[p].pos > t && p <= u)
p++;
d[i] = getmin(b[i].c, deq[p].val + i * s);
d[i] *= b[i].p;
d[i] += d[i - 1];
long long cost = b[i].c - i * s;
while (deq[u].val >= cost && p <= u)
u--;
deq[++u].pos = i;
deq[u].val = cost;
}
g << d[n];
}