选择客栈

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxn=2e5+7;
 6 const int maxc=57;
 7 int n,k,p,ret=0;
 8 int col[maxn],f[maxn],cst[maxn],minn[maxc],before[maxc],sum[maxc],ans[maxc];
 9 int main(){
10     memset(minn,2147483647,sizeof(minn));
11     cin>>n>>k>>p;
12     for(int i=1;i<=n;i++) cin>>col[i]>>cst[i];
13     for(int i=1;i<=n;i++){
14         for(int j=0;j<k;j++)
15             minn[j]=min(minn[j],cst[i]);
16         if(minn[col[i]]<=p){
17             f[i]=sum[col[i]];
18         }
19         else{
20             f[i]+=before[col[i]];
21         }
22         sum[col[i]]++;
23         before[col[i]]=f[i];minn[col[i]]=cst[i];
24         ans[col[i]]=max(ans[col[i]],f[i]);
25     }
26     for(int i=1;i<=n;i++) ret+=f[i];
27     cout<<ret<<endl;
28     return 0;    
29 }