Pagini recente » Cod sursa (job #2709943) | Cod sursa (job #1598386) | Cod sursa (job #2453295) | Cod sursa (job #2398175) | Cod sursa (job #2799090)
#include <algorithm>
#include <stdio.h>
#include <deque>
int type[ 100 ];
long long readInt( FILE *fin ) {
long long rez = 0, ch;
while( !type[ ( ch = fgetc( fin ) ) ] );
long long semn = 1;
if( ch == '-' ) {
semn = -1;
ch = fgetc( fin );
}
do
rez = rez * 10 + ch - '0';
while( type[ ( ch = fgetc( fin ) ) ] );
return rez * semn;
}
std::deque<std::pair<long long, long long> > q;
int main()
{
type[ '-' ] = type[ '0' ] = type[ '1' ] = type[ '2' ] = type[ '3' ] = type[ '4' ] = 1;
type[ '5' ] = type[ '6' ] = type[ '7' ] = type[ '8' ] = type[ '9' ] = 1;
FILE *fin = fopen( "branza.in", "r" );
long long n = readInt( fin );
long long s = readInt( fin );
long long k = readInt( fin );
long long rez = 0;
for( int i = 0; i < n; i++ ) {
long long cost = readInt( fin );
long long kg = readInt( fin );
if( !q.empty() && q.front().second + 1 == i - k )
q.pop_front();
while( !q.empty() && q.back().first + ( i - q.back().second ) * s > cost )
q.pop_back();
q.push_back( { cost, i } );
rez += kg * ( q.front().first + ( i - q.front().second ) * s );
}
FILE *fout = fopen( "branza.out", "w" );
fprintf( fout, "%lld\n", rez );
fclose( fout );
return 0;
}