fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ldb long double
  4. #define fi first
  5. #define se second
  6. #define sza(a) (int)a.size()
  7. #define pir pair<int,int>
  8. #define pirll pair<ll,ll>
  9. using namespace std;
  10. const int maxn = 5e2 + 9;
  11. const int inf = 2e9;
  12. const int LIM = maxn*maxn;
  13.  
  14. inline void mini(int &x,int y){if (x > y) x = y;}
  15. inline void maxi(int &x,int y){if (x < y) x = y;}
  16.  
  17. int a[maxn],b[maxn],dp[LIM],NP[LIM],pre[LIM],suf[LIM];
  18. bool mark[LIM];
  19.  
  20. void dynamic_programming(int n){
  21. 	int sum = a[1];
  22.  
  23. 	dp[0] = b[1];
  24. 	mark[a[1]] = 1;
  25. 	mark[0] = 1;
  26.  
  27. 	for (int i = 2 ; i <= n ; i++){
  28. 		sum += a[i];
  29.  
  30. 		for (int x = 0 ; x <= sum ; x++)
  31. 		  if (mark[x]) NP[x] = dp[x] + b[i];
  32.  
  33. 		for (int x = sum ; x >= a[i] ; x--)
  34. 		  if (mark[x - a[i]])
  35. 		    mark[x] = 1,maxi(NP[x],dp[x - a[i]]);
  36.  
  37. 		for (int x = 0 ; x <= sum ; x++){
  38. 			dp[x] = NP[x];
  39. 			NP[x] = 0;
  40. 		}
  41. 	}
  42.  
  43.  
  44. 	int lim = LIM - 4;
  45. 	for (int i = lim ; i >= 0 ; i--){
  46. 		suf[i] = suf[i + 1];
  47. 		if (mark[i]) maxi(suf[i],dp[i] + i);
  48. 	}
  49.  
  50. 	for (int i = 0 ; i <= lim ; i++){
  51. 		if (i > 0) pre[i] = pre[i - 1];
  52. 		maxi(pre[i],dp[i]);
  53. 	}
  54. }
  55.  
  56. int getstate(int X,int Y){
  57.     int A,B;
  58. 	//winning state
  59. 	A = Y + 1;
  60. 	if (suf[A] > X + Y) return 0;
  61.  
  62. 	//draw state
  63. 	if (suf[A] == X + Y || pre[Y] >= X) return 1;
  64.  
  65. 	//lost state
  66. 	return 2;
  67. }
  68.  
  69. int main(){
  70. 	ios_base::sync_with_stdio(false);
  71. 	cin.tie(0);cout.tie(0);
  72.  
  73. 	int n;
  74. 	cin >> n;
  75. 	for (int i = 1 ; i <= n ; i++) cin >> a[i] >> b[i];
  76.  
  77. 	dynamic_programming(n);
  78.  
  79. 	int q,R[4];
  80. 	R[0] = R[1] = R[2] = 0;
  81. 	cin >> q;
  82. 	while (q--){
  83. 		int X,Y;
  84. 		cin >> X >> Y;
  85.  
  86. 		R[getstate(X,Y)]++;
  87. 	}
  88.  
  89. 	cout << R[0] << " " << R[1] << " " << R[2] << "\n";
  90.  
  91. 	return 0;
  92. }
  93.  
Success #stdin #stdout 0.01s 6720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0 0
https://ideone.com/KzewCc
language:
C++ (gcc 8.3)
created:
5 hours 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!