Submission #1089460

#TimeUsernameProblemLanguageResultExecution timeMemory
1089460vjudge1Kpart (eJOI21_kpart)C++17
100 / 100
1414 ms1372 KiB
#include <bits/stdc++.h> #define int long long #define all(x) x.begin(), x.end() #define allr(x) x.rbegin(), x.rend() #define sz size() #define yes "YES" #define no "NO" #define IOI ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define pf push_front #define pb push_back #define S second #define F first using namespace std; const int N = 1e5 + 29; const int NN = 1e5; const int mod = (1e9 + 7); const int inf = 1e18; int a[N], pref[N], dp[N]; void legenda_ne_umret() { int n; cin >> n; for (int i = 0; i < N; i++) dp[i] = 0; set<int> st; for (int i = 1; i <= n; i++) { cin >> a[i]; pref[i] = pref[i - 1] + a[i]; if (i > 1) st.insert(i); } for (int i = 1; i <= n; i++) { for (int j = N - 9; j > a[i]; j--) { dp[j] = max(dp[j], dp[j - a[i]]); } dp[a[i]] = i; for (int j = 2; j <= i; j++) { int sum = pref[i] - pref[i - j]; if (sum % 2 || dp[sum / 2] < i - j + 1) { st.erase(j); } } } cout << st.sz << ' '; for (auto i : st) cout << i << ' '; } signed main() { IOI; // freopen("maze.in", "r", stdin); // freopen("maze.out", "w", stdout); ///////////////////////////////////////////// int t = 1; cin >> t; for (int i = 1; i <= t; i++) { // cout << "Case " << i << ":\n"; legenda_ne_umret(); cout << '\n'; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...