2967 2023. 02. 06 11:55:56 1478 Csoportokba osztás cpp17 Időlimit túllépés 22/100 2.599s 6364 KiB 
#include <bits/stdc++.h>

using namespace std;

long long dp[101][100001];

int main()
{

    //ifstream cin("in.txt");

    int n;
    cin >> n;
    int l;
    cin >> l;

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

    vector<long long> pS(n+1);
    for(int i = 1; i <= n; i++){
        pS[i] = pS[i-1] + a[i];
        //cout << pS[i] << " ";
    }
    //cout << '\n';

    /*for(int i = 1; i <= n; i++){
        dp[1][i] = pS[i] * a[i];
    }*/

    for(int i = 1; i <= l; i++){
        //cout << i <<": ";
        for(int j = i; j <= n; j++){
            long long maxi = 0;
            for(int k = i-1; k <= j-1; k++){
                //cout << dp[i-1][k] + (pS[j] - pS[k]) * abs(a[j]) << " ";
                maxi = max(dp[i-1][k] + (pS[j] - pS[k]) * abs(a[j]), maxi);
            }
            dp[i][j] = maxi;

            //cout << '\n';
        }
        //cout << '\n';
    }


    cout << dp[l][n];



    return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1828 KiB
2 Elfogadva 3ms 2024 KiB
subtask2 0/5
3 Időlimit túllépés 2.599s 3552 KiB
4 Időlimit túllépés 2.575s 3848 KiB
5 Időlimit túllépés 2.578s 3928 KiB
subtask3 22/22
6 Elfogadva 65ms 5052 KiB
7 Elfogadva 65ms 5392 KiB
8 Elfogadva 65ms 5336 KiB
9 Elfogadva 65ms 5660 KiB
10 Elfogadva 65ms 5992 KiB
11 Elfogadva 65ms 6080 KiB
subtask4 0/34
12 Elfogadva 3ms 4216 KiB
13 Elfogadva 3ms 4340 KiB
14 Elfogadva 3ms 4432 KiB
15 Időlimit túllépés 2.599s 5132 KiB
16 Időlimit túllépés 2.565s 5132 KiB
17 Időlimit túllépés 2.548s 5356 KiB
18 Elfogadva 4ms 5168 KiB
19 Elfogadva 4ms 5344 KiB
20 Elfogadva 4ms 5472 KiB
21 Időlimit túllépés 2.599s 5876 KiB
22 Időlimit túllépés 2.568s 5828 KiB
23 Időlimit túllépés 2.586s 5848 KiB
subtask5 0/29
24 Időlimit túllépés 2.575s 5756 KiB
25 Időlimit túllépés 2.581s 5988 KiB
26 Időlimit túllépés 2.545s 5756 KiB
27 Időlimit túllépés 2.569s 5824 KiB
28 Időlimit túllépés 2.563s 5944 KiB
29 Időlimit túllépés 2.549s 6124 KiB
30 Időlimit túllépés 2.536s 6000 KiB
31 Időlimit túllépés 2.563s 6208 KiB
32 Időlimit túllépés 2.572s 6188 KiB
subtask6 0/10
33 Időlimit túllépés 2.568s 6176 KiB
34 Időlimit túllépés 2.562s 6176 KiB
35 Időlimit túllépés 2.568s 6228 KiB
36 Időlimit túllépés 2.572s 6236 KiB
37 Időlimit túllépés 2.575s 6340 KiB
38 Időlimit túllépés 2.568s 6364 KiB