Cod sursa(job #1534194)
| Utilizator | Data | 23 noiembrie 2015 14:39:25 | |
|---|---|---|---|
| Problema | Branza | Scor | 40 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.62 kb |
#include <fstream>
#include <deque>
#include <iostream>
using namespace std;
ifstream fin("branza.in");
ofstream fout("branza.out");
deque < long long int > d;
long long int i,j,k,n,l,m,v[100010],s,t,x,ans;
int main()
{
fin>>n>>s>>t;
for( i = 1 ; i <= n ; i++ )
{
fin>>v[ i ]>>x;
while( d.size() && v[ d.back() ] + s * ( i - d.back() ) > v[ i ] )
{
d.pop_back();
}
d.push_back( i );
if( d.front() < i - t + 1 )
d.pop_front();
ans += ( v[ d.front() ] + s * ( i - d.front() ) ) * x;
}
fout<<ans;
}
