Submission #19677264


Source Code Expand

Copy
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  int sum = 0;
  for(int el:a) sum+=el;
  
  vector<vector<bool>> dp(n+1,vector<bool>(sum+1));
  dp[0][0] = true;
  for(int i=1;i<dp[0].size();i++){
    dp[0][i] = false;
  }
  
  for(int i=1;i<dp.size();i++){
    dp[i][0] = true;
  }
  
  for(int row=1;row<dp.size();row++){
    for(int col=1;col<dp[0].size();col++){
      if(a[row-1]>col){
        dp[row][col] = dp[row-1][col];
        continue;
      }
      dp[row][col] = dp[row-1][col] || dp[row-1][col-a[row-1]];
    }
  }
  
  int count = 0;
  for(int i=0;i<dp[0].size();i++){
    if(dp[dp.size()-1][i]) count++;
  }
  
  cout << count << endl;
  return 0;
}

Submission Info

Submission Time
Task A - コンテスト
User imfuxxedup
Language C++ (GCC 9.2.1)
Score 2
Code Size 874 Byte
Status AC
Exec Time 9 ms
Memory 3672 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:17:16: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<bool>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   17 |   for(int i=1;i<dp[0].size();i++){
      |               ~^~~~~~~~~~~~~
./Main.cpp:21:16: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::vector<bool> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   21 |   for(int i=1;i<dp.size();i++){
      |               ~^~~~~~~~~~
./Main.cpp:25:20: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::vector<bool> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   25 |   for(int row=1;row<dp.size();row++){
      |                 ~~~^~~~~~~~~~
./Main.cpp:26:22: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<bool>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   26 |     for(int col=1;col<dp[0].size();col++){
      |                   ~~~^~~~~~~~~~~~~
./Main.cpp:36:16: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<bool>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   36 |   for(int i=0;i<dp[0].size();i++){
      |               ~^~~~~~~~~~~~~

Judge Result

Set Name All
Score / Max Score 2 / 2
Status
AC × 5
Set Name Test Cases
All 00, 01, 02, 90, 91
Case Name Status Exec Time Memory
00 AC 9 ms 3528 KB
01 AC 3 ms 3620 KB
02 AC 9 ms 3672 KB
90 AC 3 ms 3564 KB
91 AC 2 ms 3568 KB