Pagini recente » Cod sursa (job #237624) | Cod sursa (job #1716168) | Cod sursa (job #782571) | Betasah | Cod sursa (job #2887675)
#include<fstream>
#include<deque>
using namespace std;
int costuri[100005];
int cantitate[100005];
int n,s,t;
deque<int> profitabil;
int main() {
ifstream fin("branza.in");
ofstream fout("branza.out");
fin>>n>>s>>t;
long long cost=0;
for(int i=0;i<n;i++){
fin>>costuri[i]>>cantitate[i];
while(!profitabil.empty() && i-profitabil.front()>t){
profitabil.pop_front();
}
while(!profitabil.empty() && costuri[profitabil.back()]*cantitate[i] + s*(i-profitabil.back())*cantitate[i] > costuri[i]*cantitate[i]){
profitabil.pop_back();
}
profitabil.push_back(i);
cost+=costuri[profitabil.front()]*cantitate[i]+s*(i-profitabil.front())*cantitate[i];
}
fout<<cost;
fout.close();
fin.close();
return 0;
}