fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define ld long double
  5. #define all(x) x.begin(), x.end()
  6. const int N = 5e4 + 5;
  7.  
  8. int n, m;
  9. vector<array<int, 2>> a;
  10. array<int, 2> dp1[1005][N], dp2[1005][N];
  11.  
  12. array<int, 2> suf(int pos, int rem){
  13.     if(rem < 0 || pos == n) return {0, 1};
  14.     if(dp1[pos][rem][0] != -1) return dp1[pos][rem];
  15.     auto ans = suf(pos + 1, rem);
  16.     if(rem >= a[pos][0]){
  17.         auto res = suf(pos + 1, rem - a[pos][0]);
  18.         if(res[0] + a[pos][1] > ans[0]){
  19.             ans = {res[0] + a[pos][1], res[1]};
  20.         }else if(res[0] + a[pos][1] == ans[0]){
  21.             ans[1] += res[1];
  22.         }
  23.     }
  24.     return dp1[pos][rem] = ans;
  25. }
  26.  
  27. array<int, 2> pre(int pos, int rem){
  28.     if(rem < 0 || pos == -1) return {0, 1};
  29.     if(dp2[pos][rem][0] != -1) return dp2[pos][rem];
  30.     auto ans = pre(pos - 1, rem);
  31.     if(rem >= a[pos][0]){
  32.         auto res = pre(pos - 1, rem - a[pos][0]);
  33.         if(res[0] + a[pos][1] > ans[0]){
  34.             ans = {res[0] + a[pos][1], res[1]};
  35.         }else if(res[0] + a[pos][1] == ans[0]){
  36.             ans[1] += res[1];
  37.         }
  38.     }
  39.     return dp2[pos][rem] = ans;
  40. }
  41.  
  42. void solve(int tc){
  43.     cin >> n >> m;
  44.     a.resize(n);
  45.     for(auto &[x, y] : a) cin >> x >> y;
  46.     memset(dp1, -1, sizeof(dp1));
  47.     memset(dp2, -1, sizeof(dp2));
  48.     auto mx = suf(0, m);
  49.  
  50.     string ans;
  51.     for(int i = 0; i < n; i++){
  52.         array<int, 2> exclude = {0, 0};
  53.         for(int j = 0; j <= m; j++){
  54.             auto p = pre(i - 1, j), s = suf(i + 1, m - j);
  55.             if(p[0] + s[0] >= exclude[0]){
  56.                 exclude[0] = p[0] + s[0];
  57.                 exclude[1] = p[1] * s[1];
  58.             }
  59.         }
  60.  
  61.         array<int, 2> include = {0, 0};
  62.         int rem = m - a[i][0];
  63.         for(int j = 0; j <= rem; j++){
  64.             auto p = pre(i - 1, j), s = suf(i + 1, rem - j);
  65.             if(p[0] + s[0] >= include[0]){
  66.                 include[0] = p[0] + s[0];
  67.                 include[1] = p[1] * s[1];
  68.             }
  69.         }
  70.         include[0] += a[i][1];
  71.  
  72.         if(include[0] == mx[0] && include[1] == mx[1]) ans += 'A';
  73.         else if(include[0] < mx[0]) ans += 'C';
  74.         else ans += 'B';
  75.     }
  76.     cout << ans << '\n';
  77. }
  78.  
  79. signed main() {
  80.     ios::sync_with_stdio(false);
  81.     cin.tie(NULL);
  82.     int t = 1;
  83.     // cin >> t;
  84.     for(int i = 1; i <= t; i++){
  85.         // cout << "TC - " << i << ":\n";
  86.         solve(i);
  87.     }
  88.     return 0;
  89. }
Success #stdin #stdout 0.61s 1574068KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/azJ7Sw
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
1 hour ago

					

					

						
visibility:

						

							 public																												
							
							

								
							

						

					

										
										

					
					 Share or Embed source code
					
					
					
					

						
						
						
						
						
						
						
					

					
						
	
	
	
	
					
					
					
					
					 
					
					
					
					 
					
					
					
					
					
					

					

					

					
						
					

					


	
Discover > Sphere Engine API

	
The brand new service which powers Ideone!

	
	
Discover > IDE Widget

    
Widget for compiling and running the source code in a web browser!