Cod sursa(job #2638170)
| Utilizator | Data | 27 iulie 2020 13:31:32 | |
|---|---|---|---|
| Problema | Branza | Scor | 30 |
| Compilator | cpp-64 | Status | done |
| Runda | Arhiva de probleme | Marime | 0.57 kb |
#include <fstream>
#define dim 10001
using namespace std;
ifstream f("branza.in");
ofstream g("branza.out");
long long a[dim],b[dim],n,s,t,sol,v[dim],p,u;
int main()
{
f>>n>>s>>t;
for(int i=1;i<=n;i++)
{
f>>a[i]>>b[i];
a[i]+=s*(n-i);
}
p=1;
u=0;
for(int i=1;i<=n;i++)
{
while(a[i]<=a[v[u]] && p<=u)
{
u--;
}
v[++u]=i;
if(v[u]-v[p]==t+1)
{
p++;
}
sol+=b[i]*(a[v[p]]-s*(n-i));
}
g<<sol<<'\n';
return 0;
}
