Pagini recente » Cod sursa (job #1841607) | Cod sursa (job #2450096) | Cod sursa (job #8326) | Cod sursa (job #913572) | Cod sursa (job #793748)
Cod sursa(job #793748)
#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;
void citeste(){
f >> n >> S >> T;
for(int i=1; i<=n; ++i){
f >> C[i] >> P[i];
}
}
void rezolva(){
//ideea ar fi : dp[i] = costul minim pentru a acoperi primele i cerinte
for(int i=1; i<=n; ++i){
//initial presupun ca fac la pasul i de cat am nevoie
dp[i] = C[i] * P[i];
ll Min = C[i];
int poz = i;
for(int j=i-1; j>=i-T; --j){
if (j<=0) break;//altfel intra in balarii
dp[i] = min(dp[i], P[i]*C[j] + S * P[i] * (i-j));
if ( Min > C[j] + C[j] * S*1LL*(i-j)) {
Min = C[j] + C[j] * S*1LL*(i-j);
poz = j;
}
}
dp[i] = min(dp[i], P[i] * C[poz] + S * P[i] * 1LL*(i-poz) );
dp[i] += dp[i-1];
}
g << dp[n] << "\n";
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}