fork download
copy 
  1. #include <iostream>
  2. #include<bits/stdc++.h>
  3. #include <vector>
  4. #include <stack>
  5. #include <queue>
  6. #include <deque>
  7. #include <utility>
  8. #include <set>
  9. #include <map>
  10. #include <unordered_set>
  11. #include <unordered_map>
  12. #include<algorithm>
  13. #include <ext/pb_ds/assoc_container.hpp>
  14. #include <ext/pb_ds/tree_policy.hpp>
  15. #define IOF ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  16. #define ll long long
  17. #define ld long double
  18. #define cy cout << "YES" << '\n';
  19. #define cn cout << "NO" << '\n';
  20. using namespace std;
  21. using namespace __gnu_pbds;
  22.  
  23. template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
  24. template<typename T>
  25. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  26.  
  27. int dx[] = {1, 0, -1, 0, -1, -1, 1, 1};
  28. int dy[] = {0, -1, 0, 1, -1, 1, -1, 1};
  29. int knightX[] = {-2, -2, 2, 2, 1, 1 , -1, -1};
  30. int knighty[] = {-1, 1, -1, 1, -2, 2, -2, 2};
  31. char di[] = {'D', 'L', 'U', 'R'};
  32. const int N =505 , M = 1e4+5;
  33. const ll MOD =  998244353;
  34. const int LOG = 20;
  35. void FOI() {
  36.       freopen("input.txt", "r", stdin);
  37.       freopen("output.txt", "w", stdout);
  38.   }
  39. bool prime[N + 6];
  40. vector<int> primes;
  41.  
  42. void sieve() {
  43.     fill(prime, prime + N, 1);
  44.     prime[0] = prime[1] = false;
  45.     for (int i = 2; i * i < N; ++i) {
  46.         if (!prime[i]) continue;
  47.         for (int j = i * i; j <= N; j += i) {
  48.             prime[j] = false;
  49.         }
  50.     }
  51.     for (int i = 2; i < N; ++i) {
  52.         if (prime[i]) {
  53.             primes.push_back(i);
  54.         }
  55.     }
  56. }
  57.  
  58. int n;
  59. vector<int> v;
  60.  
  61. void solve(){
  62. cin >> n;
  63. v.clear();
  64. v.resize(n);
  65. int sum = 0;
  66. for(int i = 0 ; i < n ; i++)cin >> v[i] , sum+= v[i];
  67. if(sum < 2 * n){
  68.   cn
  69.   return; 
  70. }
  71. int dp[505] , ndp[505];
  72. int rem = sum - 2*n;
  73. for(int i = 0 ; i < 505 ; i++)dp[i] = i == 0 ? 0 : 1e9;
  74. for(int i = 0 ; i < n ; i++){
  75.   for(int j = 0 ; j <=rem;  j++){
  76.     ndp[j] = 1e9;
  77.   }
  78.   for(int j = 0 ; j<= rem ; j++){
  79.     if(dp[j] == 1e9)continue;
  80.   for (auto &&p : primes)
  81.   {
  82.     int cost = p-2;
  83.     if(j + cost > rem)break;
  84.     int numOfRealOp = dp[j] + max(0 , p-v[i]);
  85.     ndp[j+cost] = min(ndp[j+cost] , numOfRealOp);
  86.   }
  87. }
  88. swap(dp , ndp);
  89. }
  90. if(dp[rem] == 1e9){
  91.   cn 
  92.   return;
  93. }
  94. cy
  95. cout <<dp[rem]<< '\n';
  96.  
  97. } 
  98.  
  99.  
  100. signed main() {
  101.   IOF
  102.   //FOI();
  103.   //freopen("substr.in", "r", stdin);
  104.     sieve();
  105.     ll t = 1;
  106.     cin >> t;
  107.     while (t--) {
  108.  
  109.     solve() ;
  110.  
  111.     }
  112.  
  113.  
  114.     return 0;
  115. }
Success #stdin #stdout 0.01s 5308KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
YES
0
https://ideone.com/W2WPSJ
language:
C++ (gcc 8.3)
created:
2 days 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!