oj.uz

Submission #38242

# Submission time Handle Problem Language Result Execution time Memory
38242 2018-01-03T06:50:08 Z Talant Bootfall (IZhO17_bootfall) C++14
6 / 100
 86 ms 262144 KB 
#include <bits/stdc++.h>

#define fr first
#define sc second
#define OK puts("OK");
#define pb push_back
#define mk make_pair

using namespace std;

typedef long long ll;

const ll inf = (ll)1e9 + 7;
const int N = (int)1e6 + 1;
const int M = (int)72901;

int n;
int dp[271][72901];
int a[N],sum;
vector <int> ans;

int main () {
        cin >> n;

        for (int i = 1; i <= n; i ++)
                cin >> a[i],sum += a[i];

        for (int i = 0; i <= n; i ++)
                memset(dp[i],-1,sizeof(dp[i]));

        for (int i = 0; i <= n; i ++) {
                dp[i][0] = 1;
                vector <int> v;
                v.pb(0);
                for (int j = 1; j <= n; j ++) {
                        if (j == i)
                                continue;
                        int o = v.size();
                        for (int k = 0; k < o; k ++) {
                                if (sum >= v[k] + a[j]) {
                                        dp[i][v[k] + a[j]] = 1;
                                        v.pb(v[k] + a[j]);
                                }
                        }

                }
        }

        for (int i = 1; i <= sum; i ++) {
                int f = 0;
                if (sum % 2 != 0 || dp[0][sum / 2] == -1)
                        continue;

                for (int j = 1; j <= n; j ++) {
                        if ((sum - a[j] + i) % 2 != 0 || (sum - a[j] + i) / 2 - i < 0 || dp[j][(sum - a[j] + i) / 2 - i] == -1 || dp[j][(sum - a[j] + i) / 2] == -1) {
                                f = 1;
                                break;
                        }
                }
                if (!f)
                        ans.pb(i);
        }
        cout << ans.size() << endl;

        for (int i = 0; i < ans.size(); i ++)
                cout << ans[i] << " ";
}

Compilation message

bootfall.cpp: In function 'int main()':
bootfall.cpp:65:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < ans.size(); i ++)
                           ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 83092 KB Output is correct
2 Correct 0 ms 83092 KB Output is correct
3 Correct 0 ms 83092 KB Output is correct
4 Correct 0 ms 83092 KB Output is correct
5 Correct 0 ms 83092 KB Output is correct
6 Correct 0 ms 83092 KB Output is correct
7 Correct 0 ms 83092 KB Output is correct
8 Correct 3 ms 83092 KB Output is correct
9 Correct 0 ms 83092 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 83092 KB Output is correct
2 Correct 0 ms 83092 KB Output is correct
3 Correct 0 ms 83092 KB Output is correct
4 Correct 0 ms 83092 KB Output is correct
5 Correct 0 ms 83092 KB Output is correct
6 Correct 0 ms 83092 KB Output is correct
7 Correct 0 ms 83092 KB Output is correct
8 Correct 3 ms 83092 KB Output is correct
9 Correct 0 ms 83092 KB Output is correct
10 Memory limit exceeded 86 ms 262144 KB Memory limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 83092 KB Output is correct
2 Correct 0 ms 83092 KB Output is correct
3 Correct 0 ms 83092 KB Output is correct
4 Correct 0 ms 83092 KB Output is correct
5 Correct 0 ms 83092 KB Output is correct
6 Correct 0 ms 83092 KB Output is correct
7 Correct 0 ms 83092 KB Output is correct
8 Correct 3 ms 83092 KB Output is correct
9 Correct 0 ms 83092 KB Output is correct
10 Memory limit exceeded 86 ms 262144 KB Memory limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 83092 KB Output is correct
2 Correct 0 ms 83092 KB Output is correct
3 Correct 0 ms 83092 KB Output is correct
4 Correct 0 ms 83092 KB Output is correct
5 Correct 0 ms 83092 KB Output is correct
6 Correct 0 ms 83092 KB Output is correct
7 Correct 0 ms 83092 KB Output is correct
8 Correct 3 ms 83092 KB Output is correct
9 Correct 0 ms 83092 KB Output is correct
10 Memory limit exceeded 86 ms 262144 KB Memory limit exceeded
11 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 83092 KB Output is correct
2 Correct 0 ms 83092 KB Output is correct
3 Correct 0 ms 83092 KB Output is correct
4 Correct 0 ms 83092 KB Output is correct
5 Correct 0 ms 83092 KB Output is correct
6 Correct 0 ms 83092 KB Output is correct
7 Correct 0 ms 83092 KB Output is correct
8 Correct 3 ms 83092 KB Output is correct
9 Correct 0 ms 83092 KB Output is correct
10 Memory limit exceeded 86 ms 262144 KB Memory limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 83092 KB Output is correct
2 Correct 0 ms 83092 KB Output is correct
3 Correct 0 ms 83092 KB Output is correct
4 Correct 0 ms 83092 KB Output is correct
5 Correct 0 ms 83092 KB Output is correct
6 Correct 0 ms 83092 KB Output is correct
7 Correct 0 ms 83092 KB Output is correct
8 Correct 3 ms 83092 KB Output is correct
9 Correct 0 ms 83092 KB Output is correct
10 Memory limit exceeded 86 ms 262144 KB Memory limit exceeded
11 Halted 0 ms 0 KB -