Cod sursa(job #1464705)

Utilizator borcanirobertBorcani Robert borcanirobert Data 24 iulie 2015 12:14:21
Problema Branza Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include <cstdio>
#include <deque>
#include <vector>
#include <iostream>
using namespace std;

const int MAXREAD = 100000;
vector< pair<int, int> > a;
int N, S, T;
deque<int> Q;
long long cost;
char r[MAXREAD];
int p = MAXREAD - 1;
int x, y, best;

void Read();
void DetCost();
void Get( int& x );
void Next();

int main()
{
    freopen( "branza.in", "r", stdin );
    freopen( "branza.out", "w", stdout );
    Read();
    DetCost();
    printf( "%lld\n", cost );
    fclose(stdin);
    fclose(stdout);
    return 0;
}

void Read()
{
    int i;
    Get(N);
    Get(S);
    Get(T);
    a.push_back( make_pair(0, 0) );
    for ( i = 1; i <= N; i++ )
    {
        Get(x);
        Get(y);
        a.push_back( make_pair(x, y) );
    }
    a.resize(N + 1);
}

void DetCost()
{
    int i;
    for ( i = 1; i <= N; i++ )
    {
        while ( !Q.empty() && i - Q.front() > T )
            Q.pop_front();

        while ( !Q.empty() && a[i].first < a[Q.back()].first + ( ( i - Q.back() ) * S ) )
            Q.pop_back();
        Q.push_back(i);

        best = ( ( i - Q.front() ) * S ) + a[Q.front()].first;
        cost = cost + ( 1LL * best * a[i].second );
    }
}

void Get( int& x )
{
    for ( ; r[p] < '0' || r[p] > '9'; Next() );
    for ( x = 0; r[p] >= '0' && r[p] <= '9'; Next() )
        x = ( x * 10 ) + ( r[p] - '0' );
}

void Next()
{
    if ( ++p == MAXREAD )
        std::fread( r, 1, MAXREAD, stdin ), p = 0;
}