Cod sursa(job #2388840)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 26 martie 2019 16:12:42
Problema Branza Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.69 kb
#include<bits/stdc++.h>
#define pret first
#define zi second
using namespace std ;
const int NR =  100005 ;
ifstream in ("branza.in") ;
ofstream out ("branza.out") ;
deque < pair < int64_t , int64_t > > dq ;
int64_t  n , cost , kg , t , i , s , ans ;
int main () {
    in >> n >> s >> t ;
    for ( i = 1 ; i <= n ; ++ i )   {
        in >> cost >> kg ;
        if ( !dq.empty() && t + 1 == i - dq.front().zi  ) dq.pop_front() ;
        while ( !dq.empty() && dq.back().pret + s * (  i - dq.back().zi ) > cost )
            dq.pop_back() ;
        dq.push_back( { cost , i } ) ;
        ans += ( dq.front().pret + s * ( i - dq.front().zi ) ) * kg ;
    }
     out << ans << ' ' ;
}