Cod sursa(job #1336395)
| Utilizator | Data | 7 februarie 2015 17:48:47 | |
|---|---|---|---|
| Problema | Branza | Scor | 0 |
| Compilator | cpp | Status | done |
| Runda | Arhiva de probleme | Marime | 0.53 kb |
#include<fstream>
using namespace std;
#define NMAX 100005
ifstream fin("branza.in");
ofstream fout("branza.out");
int n,s,t,p,u,C[NMAX],P[NMAX],D[NMAX];
long long sol;
int main()
{
int i;
fin>>n>>s>>t;
for (i=1;i<=n;++i)
{
fin>>C[i]>>P[i];
C[i]-=s*(i-1);
}
p=1, u=0;
for (i=1;i<=n;++i)
{
while (p<=u && C[i]<C[D[u]])
--u;
D[++u]=i;
sol+=(C[D[p]]+s*(i-1))*P[i];
if (i-D[p]>=t) ++p;
}
fout<<sol<<"\n";
return 0;
}
