oj.uz

Submission #38261

# Submission time Handle Problem Language Result Execution time Memory
38261 2018-01-03T08:53:14 Z antimirage Bootfall (IZhO17_bootfall) C++14
0 / 100
 0 ms 22328 KB 
#include <iostream>
#include <vector>
#include <deque>
#include <math.h>
#include <set>
#include <iomanip>
#include <time.h>
#include <list>
#include <stdio.h>
#include <queue>
#include <map>
#include <algorithm>
#include <assert.h>
#include <memory.h>

#define mk make_pair
#define sc second
#define fr first
#define pb emplace_back
#define all(s) s.begin(), s.end()
#define sz(s) ( (int)s.size() )

using namespace std;

const int N = 275;

bool dp[N][N * N], u[N];

int n, ar[N], sum;

vector <int> ans, q;

main ()
{
    cin >> n;

    for (int i = 1; i <= n; i++)
        scanf("%d", &ar[i]), sum += ar[i];

    for (int i = 0; i <= n; i++)
    {
        memset(u, 0, sizeof(u) );

        q.clear();
        dp[i][0] = 1;
        q.emplace_back(0);

        u[0] = 1;

        for (int j = 1; j <= n; j++)
        {
            if (i == j) continue;

            for (int k = q.size() - 1; k >= 0; k--)
            {
                if (!u[ q[k] + ar[j] ])
                    q.emplace_back( q[k] + ar[j] ), u[ q[k] + ar[j] ] = 1;

                dp[i][ q[k] + ar[j]] = 1;
            }
            sort( all(q) );
        }
    }
    if ( sum & 1 || !dp[0][sum / 2] )
    {
        puts("0");
        return 0;
    }
    for (int i = 0; i <= sum; i++)
    {
        bool fl = true;
        for (int j = 1; j <= n; j++)
        {
            if ( ( (sum - ar[j] + i) & 1 ) || !dp[j][ (sum - ar[j] + i) / 2 - i ] ) {
                fl = false;
            break;
            }
        }
        if (fl)
            ans.pb(i);
    }
    cout << sz(ans) << endl;
    for (auto x : ans)
        printf("%d ", x);
}

Compilation message

bootfall.cpp:33:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main ()
       ^
bootfall.cpp: In function 'int main()':
bootfall.cpp:38:42: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &ar[i]), sum += ar[i];
                                          ^

Subtask #1
0 / 6.0

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

Subtask #2
0 / 7.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 16.0

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

Subtask #5
0 / 21.0

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

Subtask #6
0 / 35.0

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