oj.uz

Submission #537425

# Submission time Handle Problem Language Result Execution time Memory
537425 2022-03-15T05:35:49 Z maomao90 Kpart (eJOI21_kpart) C++17
100 / 100
 1838 ms 1872 KB 
// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
using namespace std;

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

#define INF 1000000005
#define LINF 1000000000000000005ll
#define MAXN 1005
#define MAXA 100005

int t;
int n;
int a[MAXN];
int dp[MAXA];
bool pos[MAXN][MAXN];

int main() {
#ifndef DEBUG
    ios::sync_with_stdio(0), cin.tie(0);
#endif
    cin >> t;
    while (t--) {
        cin >> n;
        REP (i, 0, n) {
            cin >> a[i];
        }
        memset(dp, -1, sizeof dp);
        REP (i, 0, n) {
            RREP (j, MAXA - 1, a[i]) {
                if (j == a[i]) continue;
                mxto(dp[j], dp[j - a[i]]);
            }
            dp[a[i]] = i;
            int sm = 0;
            RREP (j, i, 0) {
                sm += a[j];
                pos[j][i] = 0;
                if (sm % 2 == 1) continue;
                if (dp[sm / 2] >= j) {
                    pos[j][i] = 1;
                }
            }
        }
        vi ans;
        REP (k, 1, n + 1) {
            bool can = 1;
            REP (i, 0, n - k + 1) {
                if (!pos[i][i + k - 1]) {
                    can = 0;
                    break;
                }
            }
            if (can) {
                ans.pb(k);
            }
        }
        cout << ans.size();
        for (int i : ans) {
            cout << ' ' << i;
        }
        cout << '\n';
    }
    return 0;
}

/*
2
7
7 3 5 1 3 3 5
6
1 2 3 5 8 3
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 748 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 768 KB Output is correct
2 Correct 180 ms 816 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 1100 KB Output is correct
2 Correct 612 ms 1244 KB Output is correct
3 Correct 635 ms 1316 KB Output is correct
4 Correct 926 ms 1492 KB Output is correct
5 Correct 1440 ms 1872 KB Output is correct
6 Correct 1838 ms 1860 KB Output is correct
7 Correct 1718 ms 1772 KB Output is correct