oj.uz

Submission #1059868

# Submission time Handle Problem Language Result Execution time Memory
1059868 2024-08-15T08:46:27 Z vjudge1 Split the sequence (APIO14_sequence) C++17
28 / 100
 2000 ms 131072 KB 
/**
 *                       \`*-.
 *                        )  _`-.
 *                       .  : `. .
 *                       : _   '  \
 *                       ; *` _.   `*-._
 *                       `-.-'          `-.
 *                         ;       `       `.
 *                         :.       .        \
 *                         . \  .   :   .-'   .
 *                         '  `+.;  ;  '      :
 *                         :  '  |    ;       ;-.
 *                         ; '   : :`-:     _.`* ;
 *          [VĐ]        .*' /  .*' ; .*`- +'  `*'
 *                      `*-*   `*-*  `*-*'
**/
/** HELLO WOLRD**/
#include <bits/stdc++.h>

#define NAME "main"
#define data DANG
#define ii pair<int64_t , int64_t>
#define fi first
#define se second

using namespace std;

const int64_t INF64 = 0x3f3f3f3f3f3f3f3f;
const int INF32 = 0x3f3f3f3f;
const int N = 1e5;

int n , m;
int64_t a[N + 2] , pre[N + 2] , dp[N + 2][205];
int64_t ans;
int trace[N + 2][205];

void init(){
    cin >> n >> m;

    for(int i = 1 ; i <= n ; i++)
        cin >> a[i];
}

void solve(){
    for(int i = 1 ; i <= n ; i++)
        pre[i] = pre[i - 1] + a[i];

    for(int i = 0 ; i <= n ; i++)
        for(int j = i + 1 ; j <= n ; j++)
            for(int k = 1 ; k <= m ; k++){
                int64_t tmp = dp[i][k - 1] + (pre[j] - pre[i]) * (pre[n] - pre[j]);
                if(tmp > dp[j][k]){
                    dp[j][k] = tmp;
                    trace[j][k] = i;
                }
            }

    int tr;

    for(int i = 1 ; i <= n ; i++)
        if(dp[i][m] > ans) ans = dp[i][m] , tr = i;

    cout << ans << '\n';
    vector<int> res;

    for(int i = m ; i >= 1 ; i--){
        res.push_back(tr);
        tr = trace[tr][i];
    }

    reverse(res.begin() , res.end());

    for(int x : res) cout << x << " ";
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    init();
    solve();
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB contestant found the optimal answer: 108 == 108
2 Correct 0 ms 348 KB contestant found the optimal answer: 999 == 999
3 Incorrect 0 ms 348 KB Integer 0 violates the range [1, 1]
4 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 0 ms 604 KB contestant found the optimal answer: 302460000 == 302460000
3 Correct 0 ms 604 KB contestant found the optimal answer: 122453454361 == 122453454361
4 Correct 0 ms 604 KB contestant found the optimal answer: 93663683509 == 93663683509
5 Correct 0 ms 604 KB contestant found the optimal answer: 1005304678 == 1005304678
6 Correct 1 ms 604 KB contestant found the optimal answer: 933702 == 933702
7 Correct 0 ms 464 KB contestant found the optimal answer: 25082842857 == 25082842857
8 Correct 0 ms 348 KB contestant found the optimal answer: 687136 == 687136
9 Correct 0 ms 604 KB contestant found the optimal answer: 27295930079 == 27295930079
10 Correct 0 ms 348 KB contestant found the optimal answer: 29000419931 == 29000419931

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 860 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 1 ms 856 KB contestant found the optimal answer: 311760000 == 311760000
3 Correct 4 ms 860 KB contestant found the optimal answer: 1989216017013 == 1989216017013
4 Correct 1 ms 860 KB contestant found the optimal answer: 1499437552673 == 1499437552673
5 Correct 4 ms 860 KB contestant found the optimal answer: 1019625819 == 1019625819
6 Incorrect 4 ms 860 KB Integer 0 violates the range [1, 199]
7 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4184 KB contestant found the optimal answer: 21503404 == 21503404
2 Correct 3 ms 4188 KB contestant found the optimal answer: 140412195 == 140412195
3 Correct 78 ms 4316 KB contestant found the optimal answer: 49729674225461 == 49729674225461
4 Correct 3 ms 4188 KB contestant found the optimal answer: 37485571387523 == 37485571387523
5 Correct 90 ms 4308 KB contestant found the optimal answer: 679388326 == 679388326
6 Correct 72 ms 4184 KB contestant found the optimal answer: 4699030287 == 4699030287
7 Correct 78 ms 4312 KB contestant found the optimal answer: 12418819758185 == 12418819758185
8 Correct 79 ms 4188 KB contestant found the optimal answer: 31093317350 == 31093317350
9 Correct 22 ms 4188 KB contestant found the optimal answer: 12194625429236 == 12194625429236
10 Correct 39 ms 4188 KB contestant found the optimal answer: 12345131038664 == 12345131038664

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 299 ms 25176 KB contestant found the optimal answer: 1818678304 == 1818678304
2 Correct 274 ms 24924 KB contestant found the optimal answer: 1326260195 == 1326260195
3 Execution timed out 2075 ms 24924 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 50 ms 131072 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -