fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5. #define print(a)         for(auto x : a) cout << x << " "; cout << endl
  6.  
  7.  
  8.  
  9.  
  10.  
  11.  
  12.  
  13. //_ ***************************** START Below *******************************
  14.  
  15. // n = 1  10000
  16. // -10000   <=   <=  10000
  17. // a[0] = 0
  18.  
  19.  
  20. const int M = 1000000007;
  21. const int N = 10010;
  22. const int INF = 2e9+1;
  23. const int LINF = 2000000000000000001;
  24.  
  25. vector<int> isPrime;
  26. vector<int> primes;
  27.  
  28. void seive(){
  29.     isPrime.assign(N+1, 1);
  30.     isPrime[0] = isPrime[1] = 0;
  31.  
  32.     for(int i = 2; i<=N; i++){
  33.         if(isPrime[i] == 0) continue;
  34.  
  35.         for(int j=2*i; j<=N; j+=i){
  36.             isPrime[j] = 0;
  37.         }
  38.     }
  39.  
  40.     for(int i=3; i<=N; i++){
  41.     	if(isPrime[i] && i%10 == 3){
  42.     		primes.push_back(i);
  43.     	}
  44.     }
  45. }
  46.  
  47.  
  48.  
  49. int maxGameScore(vector<int> a){
  50. 	static int _ = (seive(), 0);
  51.  
  52.  
  53. 	int n = a.size();
  54.  
  55. 	vector<int> dp(n, -INF);
  56.  
  57. 	dp[0] = 0;
  58.  
  59.  
  60. 	for(int i=1; i<n; i++){
  61.  
  62. 		if(dp[i-1] != -INF)	dp[i] = dp[i-1] + a[i];
  63.  
  64. 		for(auto p : primes){
  65. 			if(i-p >= 0){
  66. 				if(dp[i-p] != -INF)
  67. 					dp[i] = max( dp[i] , dp[i-p] + a[i] );
  68. 			}
  69. 			else break;
  70. 		}
  71.  
  72. 	}
  73.  
  74. 	cout << "a : ";
  75. 	print(a);
  76.  
  77. 	cout << " dp : ";
  78. 	print(dp);
  79.  
  80. 	return dp[n-1];
  81. }
  82.  
  83.  
  84.  
  85.  
  86.  
  87.  
  88.  
  89.  
  90.  
  91. void solve() {
  92.  
  93.  
  94. 	int n;
  95. 	cin >> n;
  96.  
  97. 	vector<int> a(n);
  98. 	for(int i=0; i<n; i++) cin >> a[i];
  99.  
  100. 	cout << maxGameScore(a) << endl;
  101.  
  102. }
  103.  
  104.  
  105.  
  106.  
  107.  
  108. int32_t main() {
  109.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  110.  
  111.     int t = 1;
  112.     while (t--) {
  113.         solve();
  114.     }
  115.  
  116.     return 0;
  117. }
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
5
0 -10 -20 -30 50
stdout
copy 
a : 0 -10 -20 -30 50 
 dp : 0 -10 -30 -30 40 
40
https://ideone.com/2AKD9i
language:
C++14 (gcc 8.3)
created:
8 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!