Pagini recente » Cod sursa (job #1269026) | Cod sursa (job #216128) | Cod sursa (job #2821995) | Cod sursa (job #2821973) | Cod sursa (job #1290323)
#include <fstream>
using namespace std;
ifstream in("branza.in");
ofstream out("branza.out");
int n, s, t, dq[100001], st, dr;
long long a[100001], c[100001], nr;
void stanga( int i )
{
if ( i - dq[st] >= t )
st++;
}
void dreapta( int i )
{
while ( st <= dr && a[i] < a[ dq[dr] ] + s * ( i - dq[dr] ) )
dr--;
dq[++dr] = i;
}
int main()
{
int i;
in >> n >> s >> t;
for ( i = 1; i <= n; i++ )
in >> a[i] >> c[i];
dq[++st] = 1;
dq[++dr] = 1;
nr = a[1] * c[1];
for ( i = 2; i <= n; i++ )
{
stanga(i);
dreapta(i);
nr+= ( a[ dq[st] ] + s * ( i - dq[st] ) ) * c[ i ];
}
out << nr;
return 0;
}