CODE FESTIVAL 2015 チーム対抗 I-Platoon Match

COFES2015team_I.cpp

#include<iostream>
#include<algorithm>
 
using namespace std;
int dp[200*200*2];
 
int main(){
 
   int N;
   cin>> N;
   int k[N], d[N];
   for(int i=0; i<N; i++){
      cin>> k[i]>> d[i];
   }
 
   int sk=accumulate(k, k+N, 0);
   if(sk!=accumulate(d, d+N, 0)){
      cout<< "invalid"<< endl;
      return 0;
   }
   dp[0]=1;
   for(int i=0; i<N; i++){
      for(int sB=sk; sB>=0; sB--){
         dp[d[i]+k[i]+sB]|=dp[sB];
      }
   }
 
   cout<< (dp[sk]?"valid":"invalid")<< endl;
 
   return 0;
}