Submission #566683

#	Time	Username	Problem	Language	Result	Execution time	Memory
566683		Rifal	Bootfall (IZhO17_bootfall)	C++14	100 / 100	855 ms	5508 KiB

bootfall

#include <bits/stdc++.h>
#include <fstream>
#define endl '\n'
#define mod 1668223877717
#define INF -100000000000000000
//#define ll long long
//#define cin fin
//#define cout fout
using namespace std;
//ofstream fout("convention.out");
//ifstream fin("convention.in");
const int M = 250005;
long long dp[M];
long long cnt[M];
void add(long long x)
{
    for(int i = M-1; i >= x; i--)
    {
        dp[i] += dp[i-x]%mod;
        dp[i] %= mod;
    }
}
void remo(long long x)
{
    for(int i = x; i < M; i++)
    {
        dp[i] = ((dp[i]-dp[i-x])+mod)%mod;
        dp[i] %= mod;
    }
}
int main()
{
    ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
    int n;
    cin >> n;
    long long arr[n];
    long long sum = 0;
    dp[0] = 1;
    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
        add(arr[i]);
        sum += arr[i];
    }
    if(sum%2 == 1 || dp[sum/2] == 0)
    {
        cout << 0 << endl;
        return 0;
    }
    for(int i = 0; i < n; i++)
    {
        remo(arr[i]);
        sum -= arr[i];
        for(long long j = 0; j <= sum/2; j++)
        {
            if(dp[j] >= 1)
            {
                if(sum-(j*2) != 0)
                    cnt[sum-(j*2)]++;
            }
        }

        add(arr[i]);
        sum += arr[i];
    }
    vector<int> ans;
    for(int i = 0; i < M; i++)
    {
        if(cnt[i] == n)
            ans.push_back(i);
    }
    cout << ans.size() << endl;
    for(int i = 0; i < ans.size(); i++)
        cout << ans[i] << ' ';
    return 0;
}

Compilation message (stderr)

bootfall.cpp: In function 'int main()':
bootfall.cpp:73:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int i = 0; i < ans.size(); i++)
      |                    ~~^~~~~~~~~~~~

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