oj.uz

Submission #199927

# Submission time Handle Problem Language Result Execution time Memory
199927 2020-02-04T06:17:10 Z quocnguyen1012 Bootfall (IZhO17_bootfall) C++14
0 / 100
 7 ms 1524 KB 
#include <bits/stdc++.h>

#define fi first
#define se second
#define mp make_pair
#define pb push_back

using namespace std;
typedef long long ll;

const int maxn = 505, mod = 1e9 + 7;

int N, a[maxn];
int f[maxn * maxn];
vector<int> ret;

signed main(void)
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  if (fopen("A.INP", "r")){
    freopen("A.INP", "r", stdin);
    freopen("A.OUT", "w", stdout);
  }
  cin >> N;
  int sum = 0;
  f[0] = 1;
  for (int i = 1; i <= N; ++i){
    cin >> a[i];
    sum += a[i];
    for (int j = sum; j >= a[i]; --j){
      f[j] += f[j - a[i]];
      f[j] %= mod;
    }
  }
  if (sum & 1 || f[sum / 2] == 0){
    cout << "NO";
    return 0;
  }
  for (int i = 1; i < maxn * maxn; ++i){
    ret.pb(i);
  }
  for (int i = 1; i <= N; ++i){
    for (int j = a[i]; j <= sum; ++j){
      f[j] -= f[j - a[i]];
      if (f[j] < 0) f[j] += mod;
    }
    vector<int> vi;
    for (auto & all : ret){
      int val = sum - a[i] + all;
      if (val < 0 || val % 2 == 1 || f[val / 2] == 0){
        continue;
      }
      vi.pb(all);
    }
    swap(vi, ret);
    for (int j = sum; j >= a[i]; --j){
      f[j] += f[j - a[i]];
      f[j] %= mod;
    }
  }
  cout << ret.size() << '\n';
  for (auto & it : ret) cout << it << ' ' ;
}

Compilation message

bootfall.cpp: In function 'int main()':
bootfall.cpp:21:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.INP", "r", stdin);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
bootfall.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     freopen("A.OUT", "w", stdout);
     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1524 KB Output is correct
2 Correct 7 ms 1524 KB Output is correct
3 Incorrect 5 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1524 KB Output is correct
2 Correct 7 ms 1524 KB Output is correct
3 Incorrect 5 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1524 KB Output is correct
2 Correct 7 ms 1524 KB Output is correct
3 Incorrect 5 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1524 KB Output is correct
2 Correct 7 ms 1524 KB Output is correct
3 Incorrect 5 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1524 KB Output is correct
2 Correct 7 ms 1524 KB Output is correct
3 Incorrect 5 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1524 KB Output is correct
2 Correct 7 ms 1524 KB Output is correct
3 Incorrect 5 ms 376 KB Output isn't correct
4 Halted 0 ms 0 KB -