oj.uz

Submission #1037180

# Submission time Handle Problem Language Result Execution time Memory
1037180 2024-07-28T10:01:06 Z Phuoc Split the sequence (APIO14_sequence) C++14
22 / 100
 48 ms 8284 KB 
#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <iomanip>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set> 

using namespace std;
 
#define ll long long
#define pb push_back
#define el '\n'
#define mpair make_pair
#define MASK(i) (1LL << (i))
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define fi first
#define se second
 
/* Author: Pham Gia Phuoc */
 
const ll MOD = 998244353;
 
template <class T1, class T2>
    void add(T1 &a, T2 b){
        a += b;
        if(a >= MOD) a -= MOD;
    }
 
template <class T1, class T2>
    void sub(T1 &a, T2 b){
        a -= b;
        if(a < 0) a += MOD;
    }
 
template <class T1, class T2>
    bool minimize(T1 &a, T2 b){
        if(a > b){a = b; return true;} return false;
    }
 
template <class T1, class T2>
    bool maximize(T1 &a, T2 b){
        if(a < b){a = b; return true;} return false;
    }
 
/** END OF TEMPLATE. DRINK A CUP OF COFFEE BEFORE READING MY CODE **/
 
const int MAX = 100010;
const ll INF = (ll) 1e18 + 67LL;
const int oo = (int)(1e9 + 7);
const int NUM_BIT = 62;

#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)

int n, k;
long long a[MAX], sum[MAX];

void init(){
    cin >> n >> k;
    FOR(i, 1, n){
        cin >> a[i];
        sum[i] = sum[i - 1] + a[i];
    }
}

pair <int, int> trace[55][55][55];
long long dp[55][55][55];

long long Try(int L, int R, int K){
    if(K == 0) return 0;
    if(L == R) return 0;
    if(dp[L][R][K] != -1) return dp[L][R][K];
    
    long long res = -INF;
    long long sumTotal = sum[R] - sum[L - 1], sumLeft = 0;
    FOR(i, L, R - 1){
        sumLeft += a[i];
        FOR(k1, 0, K - 1){
            int k2 = K - k1 - 1;
            if(k2 < 0) return 0;
            long long splitCost = sumLeft * (sumTotal - sumLeft);
            long long left = Try(L, i, k1);
            long long right = Try(i + 1, R, k2);
            long long cur = left + right + splitCost;
            if(maximize(res, cur)) trace[L][R][K] = make_pair(i, k1);
        } 
    }

    return dp[L][R][K] = res;
}

vector <int> path;

void backTrack(int L, int R, int K){
    if(K == 0) return;
    if(L >= R) return;

    int t = trace[L][R][K].fi;
    int k1 = trace[L][R][K].se;
    int k2 = K - k1 - 1;

    path.push_back(t);
    backTrack(L, t, k1);
    backTrack(t + 1, R, k2);
}

void solve(){
    memset(dp, -1, sizeof dp);
    cout << Try(1, n, k) << el;
    backTrack(1, n, k);
    sort(path.begin(), path.end());
    for(int x:path) cout << x << ' ';
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define test "test"
    // freopen(test".inp", "r", stdin);
    // freopen(test".out", "w", stdout);
    srand(time(0));
    int t = 1;
    while(t--){
        init();
        solve();
    }
    
    return 0;
}


 
/*** ROAD TO VOI 2025 ***/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB contestant found the optimal answer: 108 == 108
2 Correct 0 ms 2652 KB contestant found the optimal answer: 999 == 999
3 Correct 1 ms 2652 KB contestant found the optimal answer: 0 == 0
4 Correct 0 ms 2652 KB contestant found the optimal answer: 1542524 == 1542524
5 Correct 0 ms 2652 KB contestant found the optimal answer: 4500000000 == 4500000000
6 Correct 0 ms 2652 KB contestant found the optimal answer: 1 == 1
7 Correct 0 ms 2652 KB contestant found the optimal answer: 1 == 1
8 Correct 0 ms 2652 KB contestant found the optimal answer: 1 == 1
9 Correct 1 ms 2652 KB contestant found the optimal answer: 100400096 == 100400096
10 Correct 1 ms 2652 KB contestant found the optimal answer: 900320000 == 900320000
11 Correct 1 ms 2652 KB contestant found the optimal answer: 3698080248 == 3698080248
12 Correct 1 ms 2652 KB contestant found the optimal answer: 3200320000 == 3200320000
13 Correct 1 ms 2652 KB contestant found the optimal answer: 140072 == 140072
14 Correct 0 ms 2652 KB contestant found the optimal answer: 376041456 == 376041456
15 Correct 1 ms 2652 KB contestant found the optimal answer: 805 == 805
16 Correct 0 ms 2652 KB contestant found the optimal answer: 900189994 == 900189994
17 Correct 1 ms 2652 KB contestant found the optimal answer: 999919994 == 999919994

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 1 ms 2652 KB contestant found the optimal answer: 302460000 == 302460000
3 Correct 48 ms 2652 KB contestant found the optimal answer: 122453454361 == 122453454361
4 Correct 1 ms 2648 KB contestant found the optimal answer: 93663683509 == 93663683509
5 Correct 2 ms 2652 KB contestant found the optimal answer: 1005304678 == 1005304678
6 Correct 2 ms 2652 KB contestant found the optimal answer: 933702 == 933702
7 Correct 12 ms 2760 KB contestant found the optimal answer: 25082842857 == 25082842857
8 Correct 3 ms 2652 KB contestant found the optimal answer: 687136 == 687136
9 Correct 1 ms 2748 KB contestant found the optimal answer: 27295930079 == 27295930079
10 Correct 5 ms 2652 KB contestant found the optimal answer: 29000419931 == 29000419931

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 5208 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 5212 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 5344 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 8284 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -