Pagini recente » Istoria paginii runda/speed3 | Cod sursa (job #783389) | Cod sursa (job #397988) | Cod sursa (job #2274408) | Cod sursa (job #2972984)
/// Aceasta sursa este pentru problema
/// https://www.infoarena.ro/problema/branza
/// Punctaj: 100
/// Grupa Medie
#include<fstream>
#include<iostream>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cmath>
#include <vector>
#include <queue>
#include <iomanip>
#define DIM 100000
#define DIM2 10000000
using namespace std;
ifstream f("branza.in");
ofstream g("branza.out");
//ifstream f("in.in");
//ofstream g("out.out");
long long n,s,t,c[DIM2+5],p[DIM2+5],sol=0;
deque <long long> dq;
int main(){
f>>n>>s>>t;
for(int i=1;i<=n;i++){
f>>c[i]>>p[i];
}
for(int i=1;i<=n;i++){
if(!dq.empty() && dq.front() == i-t-1){
dq.pop_front();
}
while(!dq.empty() && (c[dq.back()] + s*(i-dq.back()) > c[i])){
dq.pop_back();
}
dq.push_back(i);
sol += p[i] * (c[dq.front()] + s*(i-dq.front()));
}
g<<sol;
f.close();
g.close();
return 0;
}