Submission #342723

#	Time	Username	Problem	Language	Result	Execution time	Memory
342723		ivan_tudor	Bootfall (IZhO17_bootfall)	C++14	100 / 100	616 ms	2284 KiB

bootfall

#include<bits/stdc++.h>
using namespace std;
const int N = 505;
int dp[N*N];
const int EMPTY = INT_MAX;
int v[N];
bool good[N * N];
int main()
{
  //freopen(".in","r",stdin);
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  int n;
  cin>>n;
  int sum = 0;
  for(int i=1;i<=n;i++){
    cin>>v[i];
    sum += v[i];
  }
  for(int i=0; i< N*N; i++)
    dp[i] = EMPTY, good[i] = true;
  dp[0] = 0;
  for(int i = 1; i<=n;i ++){
    for(int val = N*N - 1 - v[i]; val >=0; val--){
      if(dp[val] != EMPTY){
        dp[val + v[i]] = min(dp[val + v[i]], i);
      }
    }
  }
  if(sum%2 == 1 || (dp[sum/2] == EMPTY)){
    cout<<"0\n";
    return 0;
  }
  for(int i = n; i >=1; i--){
    for(int val = N*N -1; val >=0; val--){
      if(dp[val] == i)
        dp[val] = EMPTY;
    }
    if(i + 1 <= n){
      for(int val = N*N -1 - v[i + 1]; val>=0; val--){
        if(dp[val] != EMPTY){
          dp[val + v[i + 1]] = min(dp[val + v[i + 1]], dp[val]);
        }
      }
    }
    for(int news = 1; news< N*N; news ++){
      if(good[news] == false)
        continue;
      int newsum = sum - v[i] + news;
      if(newsum %2 == 1 || (dp[newsum / 2] == EMPTY))
        good[news] = false;
    }
  }
  int goodval = 0;
  for(int i=1; i<N*N; i++){
    if(good[i] == true)
      goodval++;
  }
  cout<<goodval<<"\n";
  for(int i=1; i< N*N; i++){
    if(good[i] == true){
      cout<<i<<" ";
    }
  }
  return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 15 / 15
• Subtask 4: 16 / 16
• Subtask 5: 21 / 21
• Subtask 6: 35 / 35