Cod sursa(job #1113765)
Utilizator | Iordache Ioan-Bogdan iordache.bogdan | Data | 20 februarie 2014 21:29:44 |
---|---|---|---|
Problema | Branza | Scor | 40 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 0.57 kb |
#include <fstream>
#include <iomanip>
using namespace std;
typedef long long i64;
long long deq[100005], c[100005], pr;
long long n, i, s, t, p, u;
i64 sol;
int main() {
ifstream f("branza.in");
ofstream g("branza.out");
f>>n>>s>>t;
p=1;u=0;
for(i=1;i<=n;i++) {
f>>c[i]>>pr;
while(u>0 && c[i]<=c[deq[u]]+s*(i-deq[u]))
u--;
u++;
deq[u]=i;
if(deq[p]<i-t)
p++;
sol=(i64)( sol + (i64)( c[deq[p]]+s*(i-deq[p]) )*pr );
}
g<<sol<<"\n";
return 0;
}