oj.uz

Submission #5646

# Submission time Handle Problem Language Result Execution time Memory
5646 2014-05-10T02:38:43 Z tncks0121 Split the sequence (APIO14_sequence) C++
0 / 100
 0 ms 84904 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#include <bits/stdc++.h>
#include <memory.h>

typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef long double llf;
typedef unsigned int uint;

using namespace std;

const int N_ = 100500, K_ = 205;
int N, K, A[N_];
ll Table[2][N_], S[N_];
int opt[K_][N_];

void solve (int k, int i) {
    if(k == 1) return;
    solve(k - 1, opt[k][i] - 1);
    printf("%d ", opt[k][i] - 1);
}

int main() {
    scanf("%d%d", &N, &K);
    for(int i = 1; i <= N; i++) scanf("%d", A+i), S[i] = S[i-1] + A[i];

    for(int i = 1; i <= N; i++) Table[1][i] = S[i] * (S[N] - S[i]);
    for(int k = 2; k <= K+1; k++) {
        ll *now = Table[k&1], *prev = Table[~k&1];
        for(int i = 1; i <= N; i++) {
            ll vp = 0; now[i] = -1; opt[k][i] = -1;
            for(int j = 1; j <= i; j++) {
                ll v = prev[j-1] + (S[i] - S[j-1]) * (S[N] - S[i]);
                if(v > now[i]) now[i] = v, opt[k][i] = j;
                if(v < vp) break;
                vp = v;
            }
        }
    }

    printf("%lld\n", Table[~K&1][N]);
    solve(K+1, N);

    return 0;
}

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 84904 KB Output is correct - contestant found the optimal answer: 108 == 108
2 Correct 0 ms 84904 KB Output is correct - contestant found the optimal answer: 999 == 999
3 Incorrect 0 ms 84904 KB Output isn't correct - Integer 0 violates the range [1, 1]
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #3
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #4
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #5
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -

Subtask #6
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -