# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
498153 | 2021-12-24T12:52:40 Z | EliteCallsYou | Split the sequence (APIO14_sequence) | C++17 | 2000 ms | 2508 KB |
# include <bits/stdc++.h> using namespace std ; //############################################################################ # define read(a)/**/for(int i=0;i<int(sizeof(a)/sizeof(a[0]));i++){cin>>a[i];} # define print(x)/**/for(auto zx:x){cout<<zx<<' ';} const char* tochar(string a){return a.c_str();} void files(){freopen("hopscotch.in","r",stdin);freopen("hopscotch.out","w",stdout);} void speed(){ios_base::sync_with_stdio(false);cin.tie(0);} long long gcd(long long a,long long b){if(!b){return a;}a%=b;return gcd(b,a);} long long lcm(long long a,long long b){return a /gcd(a,b) * b;} //########################################################################### const int N = 1e5 + 5 ; const long long MOD = 1e9+7 ; //########################################################################### void hack(){} //########################################################################### long long n, m, ar[N], pref[N], suff[N], mx, ans ; vector < long long > cur, vc ; void rec ( int cuts, int pos ){ if ( cuts == m ){ if ( ans >= mx ){ vc = cur ; mx = ans ; } return ; } if ( pos == n ){return;} for ( int i = pos ; i < n ; i ++ ){ cur.push_back(i) ; ans += (pref[i]-pref[pos-1])*suff[i+1] ; ///////////////// rec(cuts+1,i+1) ; ///////////////// cur.pop_back() ; ans -= (pref[i]-pref[pos-1])*suff[i+1] ; } } int main(){ cin >> n >> m ; for ( int i = 1 ; i <= n ; i ++ ){ cin >> ar[i] ; pref[i] = pref[i-1]+ar[i] ; } for ( int i = n ; i >= 1 ; i -- ){ suff[i] = suff[i+1]+ar[i] ; } if ( !m ){ cout << 0 << '\n' ; return 0 ; } /////////////////////////////////// for ( int i = 1 ; i < n ; i ++ ){ cur.push_back(i) ; ans += pref[i] * suff[i+1] ; //////////////// rec(1,i+1) ; //////////////// cur.pop_back() ; ans -= pref[i] * suff[i+1] ; } cout << mx << '\n' ; for ( int i : vc ){cout<<i<<' ';} }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 204 KB | contestant found the optimal answer: 108 == 108 |
2 | Correct | 0 ms | 204 KB | contestant found the optimal answer: 999 == 999 |
3 | Correct | 1 ms | 204 KB | contestant found the optimal answer: 0 == 0 |
4 | Correct | 1 ms | 204 KB | contestant found the optimal answer: 1542524 == 1542524 |
5 | Correct | 0 ms | 204 KB | contestant found the optimal answer: 4500000000 == 4500000000 |
6 | Correct | 1 ms | 204 KB | contestant found the optimal answer: 1 == 1 |
7 | Correct | 0 ms | 304 KB | contestant found the optimal answer: 1 == 1 |
8 | Correct | 0 ms | 204 KB | contestant found the optimal answer: 1 == 1 |
9 | Correct | 0 ms | 204 KB | contestant found the optimal answer: 100400096 == 100400096 |
10 | Correct | 0 ms | 204 KB | contestant found the optimal answer: 900320000 == 900320000 |
11 | Correct | 0 ms | 204 KB | contestant found the optimal answer: 3698080248 == 3698080248 |
12 | Correct | 0 ms | 204 KB | contestant found the optimal answer: 3200320000 == 3200320000 |
13 | Correct | 0 ms | 204 KB | contestant found the optimal answer: 140072 == 140072 |
14 | Correct | 0 ms | 204 KB | contestant found the optimal answer: 376041456 == 376041456 |
15 | Correct | 1 ms | 332 KB | contestant found the optimal answer: 805 == 805 |
16 | Correct | 0 ms | 332 KB | contestant found the optimal answer: 900189994 == 900189994 |
17 | Correct | 0 ms | 204 KB | contestant found the optimal answer: 999919994 == 999919994 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 204 KB | contestant found the optimal answer: 1093956 == 1093956 |
2 | Correct | 0 ms | 204 KB | contestant found the optimal answer: 302460000 == 302460000 |
3 | Execution timed out | 2069 ms | 204 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 9 ms | 204 KB | contestant found the optimal answer: 610590000 == 610590000 |
2 | Correct | 8 ms | 312 KB | contestant found the optimal answer: 311760000 == 311760000 |
3 | Execution timed out | 2069 ms | 204 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1044 ms | 304 KB | contestant found the optimal answer: 21503404 == 21503404 |
2 | Correct | 1048 ms | 312 KB | contestant found the optimal answer: 140412195 == 140412195 |
3 | Execution timed out | 2075 ms | 332 KB | Time limit exceeded |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2083 ms | 460 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2072 ms | 2508 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |