Advertisement
mickypinata

SMMR-T123: The Grand Finale of Impazia

Jul 28th, 2021
1,611
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.20 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 100;
  5. const int X = 500;
  6.  
  7. int arr[N + 1];
  8. bool dp[N + 1][X + 1][X + 1];
  9.  
  10. int main(){
  11.  
  12.     int nArea;
  13.     scanf("%d", &nArea);
  14.     int sum = 0;
  15.     for(int i = 1; i <= nArea; ++i){
  16.         scanf("%d", &arr[i]);
  17.         sum += arr[i];
  18.     }
  19.     if(sum % 3 != 0){
  20.         cout << "noob";
  21.         return 0;
  22.     }
  23.     int tr = sum / 3;
  24.     for(int i = 0; i <= nArea; ++i){
  25.         dp[i][0][0] = true;
  26.     }
  27.     for(int i = 1; i <= nArea; ++i){
  28.         for(int x = 0; x <= tr; ++x){
  29.             for(int y = 0; y <= tr; ++y){
  30.                 if(x == 0 && y == 0){
  31.                     dp[i][x][y] = true;
  32.                     continue;
  33.                 }
  34.                 bool ans = false;
  35.                 if(x >= arr[i]){
  36.                     ans |= dp[i - 1][x - arr[i]][y];
  37.                 }
  38.                 if(y >= arr[i]){
  39.                     ans |= dp[i - 1][x][y - arr[i]];
  40.                 }
  41.                 ans |= dp[i - 1][x][y];
  42.                 dp[i][x][y] = ans;
  43.             }
  44.         }
  45.     }
  46.     if(dp[nArea][tr][tr]){
  47.         cout << "mission complete";
  48.     } else {
  49.         cout << "noob";
  50.     }
  51.  
  52.     return 0;
  53. }
  54.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement