Pagini recente » Cod sursa (job #1992738) | Cod sursa (job #2617258) | Cod sursa (job #2046131) | Cod sursa (job #2753259) | Cod sursa (job #793755)
Cod sursa(job #793755)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>
using namespace std;
ifstream f("branza.in");
ofstream g("branza.out");
#define nmax 100005
#define inf (1LL<<61)
#define ll long long
ll n, S, T, C[nmax], P[nmax], dp[nmax];
deque<ll> dq;
int poz[nmax];
void citeste(){
f >> n >> S >> T;
for(int i=1; i<=n; ++i){
f >> C[i] >> P[i];
}
}
void preprocesare(){
//imi selectez o constanta X = n+1; astfel : fie j,k cu j < k => j va fi ales daca c[j] + S * (X-j) < c[k] + * S * (X - k)
int X = n+1;
for(int i=1; i<=n; ++i){
while (!dq.empty() && ( C[dq.back()] + S * 1LL*(X-dq.back()) ) >= (C[i] + S * 1LL*(X-i)) )
dq.pop_back();
dq.push_back(i);
if (dq.size() && i - dq.front() > T) dq.pop_front();
poz[i] = dq.front();
}
}
void rezolva(){
//ideea ar fi : dp[i] = costul minim pentru a acoperi primele i cerinte
//imi preprocesez un cost[i] = costul de la pasul i(mai exact in ce saptamana am sa produc branza de care am nevoie la pasul i)
preprocesare();
for(int i=1; i<=n; ++i){
ll X = P[i] * C[ poz[i] ] + S * P[i] * 1LL*(i- poz[i] );
dp[i] = dp[i-1] + X;
}
g << dp[n] << "\n";
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}