1 条题解

  • 0
    @ 2024-2-7 12:59:12
    #include<bits/stdc++.h>
    using namespace std;
    const int MAXN=1e5+1;
    int dp[MAXN];
    inline int read(){
    	int ans=0;char c=getchar();
    	while(c<'0'||c>'9')c=getchar();
    	while(c>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+(c^'0'),c=getchar();
    	return ans;
    }
    int cnt[11][11],n,m;
    inline void solve(int t,int v){
    	for(int i=m;i>=t;i--)
    		dp[i]=max(dp[i],dp[i-t]+v);	
    }
    int main(){
    	n=read(),m=read();
    	for(int i=0;i<n;i++){
    		int a=read(),b=read();
    		cnt[a][b]++;
    	}
    	for(int t=1;t<=10;t++){
    		for(int v=1;v<=10;v++){
    			int k;
    			for(k=1;(k<<1)<=cnt[t][v];k<<=1)
    				solve(k*t,k*v);
    			k=cnt[t][v]-k+1;
    			for(int l=1;l<=k;l<<=1)
    				if(l&k)
    					solve(l*t,l*v);
    		}
    	}
    	cout<<dp[m];
    	return 0;
    }
    

    信息

    ID
    1530
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    255
    已通过
    1
    上传者