Submission #1110104

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1110104	2024-11-08 17:40:35	sunboi	Split the sequence (APIO14_sequence)	C++17	50 / 100	2041 ms	16488 KiB

sequence

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;
signed main(){
    int n, k; cin >> n >> k;
    vector<int> a(n + 1), suf(n + 2);
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for (int i = n; i >= 0; i--){
        suf[i] = suf[i + 1] + a[i];
    }
    
    vector<vector<int>> dp(n + 10, vector<int> (k + 1, 0));
    
    for (int i = n; i >= 1; i--){
        for (int j = i + 1; j <= n; j++){
            int suma = suf[i] - suf[j];
            int before = suf[j];
            for (int kk = 1; kk <= k; kk++){
                dp[i][kk] = max(dp[i][kk], dp[j][kk - 1] + suma * before);
            }
        }
    }
    set<int> id;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 0 / 21
• Subtask 6: 0 / 29