Mai intai trebuie sa te autentifici.
Cod sursa(job #1068720)
| Utilizator | Data | 28 decembrie 2013 18:12:20 | |
|---|---|---|---|
| Problema | Branza | Scor | 40 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.71 kb |
#include <iostream>
#include <fstream>
#include <deque>
using namespace std;
const int Nmax = 100001;
int N;
deque <int> deck;
long long sol, S, T;
long long cost[Nmax], cant[Nmax], V[Nmax];
int main()
{
ifstream f("branza.in");
ofstream g("branza.out");
f >> N >> S >> T;
for ( long long i = 1; i <= N; ++i )
{
f >> cost[i] >> cant[i];
V[i] = cost[i] - i * S;
while ( deck.size() && V[ deck.back() ] >= V[i] ) deck.pop_back();
while ( deck.size() && deck.front() <= i - T ) deck.pop_front();
deck.push_back( i );
sol += ( V[ deck.front() ] + S * i ) * cant[i];
}
g << sol << "\n";
return 0;
}
