| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 905152 |
2024-01-12T16:26:24 Z |
penguin133 |
Kpart (eJOI21_kpart) |
C++17 |
|
135 ms |
201556 KB |
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
pair <bool, int> dp[1005][100005];
int n, A[1005], P[1005];
void solve(){
cin >> n;
int sm = 0;
for(int i=1;i<=n;i++)cin >> A[i], P[i] = P[i-1] + A[i], sm += A[i];
dp[0][0] = {1, n + 1};
for(int i=1;i<=n;i++){
for(int j=0;j<=P[i];j++){
dp[i][j] = dp[i-1][j];
if(j >= A[i]){
if(dp[i - 1][j - A[i]].fi){
int mn = min(dp[i - 1][j - A[i]].se, i);
if(dp[i][j].fi)dp[i][j].se = max(dp[i][j].se, mn);
else dp[i][j].se = mn;
dp[i][j].fi = 1;
}
}
}
}
vector <int> pos;
for(int i=1;i<=n;i++){
bool f = 1;
sm = 0;
//cerr << i << '\n';
for(int j=1;j<i;j++)sm += A[j];
for(int j=i;j<=n;j++){
sm += A[j] - A[j - i];
//cerr << j << ' ' << '\n';
if(sm%2 == 0 && dp[j][sm / 2].fi && dp[j][sm / 2].se >= j - i + 1){}
else f = 0;
}
if(f)pos.push_back(i);
}
cout << (int)pos.size() << ' ';
for(auto i : pos)cout << i << ' ';
cout << '\n';
}
main(){
ios::sync_with_stdio(0);cin.tie(0);
int tc = 1;
cin >> tc;
for(int tc1=1;tc1<=tc;tc1++){
// cout << "Case #" << tc1 << ": ";
solve();
}
}
Compilation message
Main.cpp:53:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
53 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
24924 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
16 ms |
53596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
135 ms |
201556 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
