Pagini recente » Cod sursa (job #838581) | Cod sursa (job #925566) | Cod sursa (job #2036819) | Cod sursa (job #464045) | Cod sursa (job #1208346)
#include<fstream>
using namespace std;
struct cell
{
int cost,cantitate;
int poz;
};
ifstream fin("branza.in");
ofstream fout("branza.out");
const int NMAX=100005;
int n,s,t;
long long dp[NMAX];
cell a[NMAX];
cell deque[NMAX];
long long sum;
int main()
{
int i,j,l,pr,ul,last;
fin>>n>>s>>t;
fin>>a[1].cost>>a[1].cantitate;
a[1].poz=1;
sum+=1LL*a[1].cost*a[1].cantitate;
pr=ul=1;
deque[1]=a[1];
for (i=2;i<=n;i++)
{
fin>>a[i].cost>>a[i].cantitate;
a[i].poz=i;
while (ul>=pr && 1LL*a[i].cost*a[i].cantitate<1LL*deque[ul].cost*a[i].cantitate+1LL*(i-deque[ul].poz)*s*a[i].cantitate)
ul--;
deque[++ul]=a[i];
if (deque[ul].poz-deque[pr].poz>t) pr++;
sum+=1LL*deque[pr].cost*deque[ul].cantitate+1LL*(deque[ul].poz-deque[pr].poz)*s*deque[ul].cantitate;
}
fout<<sum<<"\n";
return 0;
}