Pagini recente » Cod sursa (job #622044) | Istoria paginii runda/hard123 | Istoria paginii utilizator/periosoare | Istoria paginii runda/antr7 | Cod sursa (job #1282382)
#include <fstream>
#include<iostream>
using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");
int n,t, s, a[100001], dq[100001], st, dr, p;
void stanga( int i )
{
if ( dq[st] == i - t )
st++;
}
void dreapta( int i )
{
while( st <= dr && a[i] < a[ dq[dr] ] + s * ( i - dq[dr] ) )
dr--;
dq[++dr] = i;
}
int main()
{
in >> n >> s >> t;
int i;
long long nr = 0;
in >> a[1] >> p;
dq[st] = 1;
dq[dr] = 1;
nr = a[1] * p;
for ( i = 2; i <= n; i++ )
{
in >> a[i] >> p;
stanga(i);
dreapta(i);
nr += a[ dq[st] ] * p + s * p * ( i - dq[st] );
}
out << nr;
return 0;
}