AlbertMourato

Untitled

Feb 29th, 2016
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.08 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <bits/stdc++.h>
  3. //%lld
  4. typedef long long ll;
  5. #define si(a) scanf("%d", &a)
  6. using namespace std;
  7.  
  8. int vetor[25];
  9. int matriz[25][200005];
  10.  
  11. int main(){
  12.     //freopen("in.txt", "r", stdin);
  13.     //freopen("out.txt", "w", stdout);
  14.     int n, t;
  15.     while(si(n)==1){
  16.         memset(matriz, 0, sizeof(matriz));
  17.         si(t);
  18.         for(int i = 0;i<t;i++)si(vetor[i]);
  19.         matriz[0][vetor[0]] = 1;
  20.         for(int i =1;i<t;i++){
  21.             for(int j = 0;j<=n;j++){
  22.                 if(j<vetor[i]){
  23.                     matriz[i][j] = matriz[i-1][j];
  24.                 }else if(vetor[i]==j){
  25.                     matriz[i][j] = 1;
  26.                 }else{
  27.                     matriz[i][j] = max(matriz[i-1][j], matriz[i-1][j-vetor[i]]);
  28.                 }
  29.             }
  30.         }
  31.         bool l = false;
  32.         for(int i = 0;i<25;i++){
  33.             if(matriz[i][n]==1){
  34.                 printf("Forma\n");
  35.                 l = true;
  36.                 break;
  37.             }
  38.         }
  39.         if(!l){
  40.             printf("NaoForma\n");
  41.         }
  42.     }
  43. }
Advertisement
Add Comment
Please, Sign In to add comment