1 solutions
-
0
C++ :
#include <cstdio> #include <cstring> #include <cmath> #include <climits> #include <cstdlib> #include <algorithm> #define MAXN 50010 #define LL long long using namespace std; int N=0,S=0,T=0; int C[MAXN]={0},P[MAXN]={0}; int Q[MAXN*10]={0}; int head=1,tail=0; inline int Get(int p){ while(head<=tail && p-Q[head]>T) head++; return Q[head]; } inline void Push(int x){ while(head<=tail && S*(x-Q[tail])+C[Q[tail]] >C[x] ) tail--; Q[++tail]=x; } int main(){ //freopen("pudding.in","r",stdin); //freopen("pudding.out","w",stdout); scanf("%d%d%d",&N,&S,&T); for(int i=1;i<=N;++i) scanf("%d%d",&C[i],&P[i]); /*暴力!!! for(int i=1;i<=N;++i){ for(int j=1;j<=T && i+j<=N;++j){ if(C[i]+S*j < C[i+j]){ C[i+j]=C[i]+S*j; } } } LL Ans=0; for(int i=1;i<=N;++i) Ans+=P[i]*C[i];*/ LL Ans=0; int pos; for(int i=1;i<=N;++i){ Push(i); pos=Get(i); Ans+=P[i]*(S*(i-pos)+C[pos]); } printf("%lld",Ans); fclose(stdin); fclose(stdout); return 0; }
- 1
Information
- ID
- 587
- Time
- 1000ms
- Memory
- 128MiB
- Difficulty
- (None)
- Tags
- # Submissions
- 0
- Accepted
- 0
- Uploaded By