1 solutions

  • 0
    @ 2024-12-10 23:10:15

    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