Cod sursa(job #2986308)
Utilizator | Staicu Matei Octavian staicumatei | Data | 28 februarie 2023 11:25:23 |
---|---|---|---|
Problema | Branza | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.51 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream f("branza.in");
ofstream g("branza.out");
int n, s, t, c, p[100002];
long long ans;
deque<int> a;
int main()
{
f>>n>>s>>t;
for(int i=1; i<=n; i++)
{
if(!a.empty() && a.front()<=i-t-1) a.pop_front();
f>>p[i]>>c;
while(!a.empty() && p[a.back()]+s*(i-a.back())>=p[i]) a.pop_back();
a.push_back(i);
ans=ans+(long long)c*(p[a.front()]+s*(i-a.front()));
}
g<<ans;
return 0;
}