YEZAELP

SMMR-123: The Grand Finale of Impazia

Jul 27th, 2021
783
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int N = 1e2 + 10;
  5. const int S = 5e2 + 10;
  6. int ar[N];
  7. int n, sum;
  8.  
  9. int main(){
  10.  
  11.     scanf("%d", &n);
  12.  
  13.     for(int i=1;i<=n;i++){
  14.         scanf("%d", &ar[i]);
  15.         sum += ar[i];
  16.     }
  17.  
  18.     if(sum % 3 != 0){
  19.         printf("noob");
  20.         return 0;
  21.     }
  22.  
  23.     sum /= 3;
  24.  
  25.     int dp[2][sum + 10][sum + 10];
  26.  
  27.     for(int a = 0; a <= sum; a ++){
  28.         for(int b = 0; b <= sum; b ++){
  29.             dp[0][a][b] = false;
  30.         }
  31.     }
  32.     dp[0][0][0] = true;
  33.  
  34.     for(int i = 1; i <= n; i ++){
  35.         int prev = (i - 1) % 2;
  36.         int cur = i % 2;
  37.         for(int a = 0; a <= sum; a ++){
  38.             for(int b = 0; b <= sum; b ++){
  39.                 bool tf = false;
  40.                 tf = dp[prev][a][b];
  41.                 if(a >= ar[i]) tf |= dp[prev][a - ar[i]][b];
  42.                 if(b >= ar[i]) tf |= dp[prev][a][b - ar[i]];
  43.                 dp[cur][a][b] = tf;
  44.             }
  45.         }
  46.     }
  47.  
  48.     bool ans = false;
  49.     int cur = n % 2;
  50.     if(dp[cur][sum][sum]) printf("mission complete");
  51.     else printf("noob");
  52.  
  53.     return 0;
  54. }
RAW Paste Data