2968 2023. 02. 06 11:59:31 1478 Csoportokba osztás cpp17 Időlimit túllépés 22/100 2.599s 6440 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-l+i; 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 2040 KiB
subtask2 0/5
3 Időlimit túllépés 2.599s 3576 KiB
4 Időlimit túllépés 2.549s 3696 KiB
5 Időlimit túllépés 2.556s 3840 KiB
subtask3 22/22
6 Elfogadva 59ms 4920 KiB
7 Elfogadva 59ms 5156 KiB
8 Elfogadva 59ms 5372 KiB
9 Elfogadva 59ms 5612 KiB
10 Elfogadva 59ms 5792 KiB
11 Elfogadva 59ms 5892 KiB
subtask4 0/34
12 Elfogadva 3ms 4028 KiB
13 Elfogadva 3ms 4184 KiB
14 Elfogadva 3ms 4540 KiB
15 Időlimit túllépés 2.599s 5564 KiB
16 Időlimit túllépés 2.588s 5580 KiB
17 Időlimit túllépés 2.559s 5580 KiB
18 Elfogadva 4ms 5616 KiB
19 Elfogadva 4ms 5732 KiB
20 Elfogadva 4ms 5640 KiB
21 Időlimit túllépés 2.599s 5948 KiB
22 Időlimit túllépés 2.575s 5900 KiB
23 Időlimit túllépés 2.584s 5896 KiB
subtask5 0/29
24 Időlimit túllépés 2.578s 5900 KiB
25 Időlimit túllépés 2.561s 5900 KiB
26 Időlimit túllépés 2.532s 6112 KiB
27 Időlimit túllépés 2.559s 6236 KiB
28 Időlimit túllépés 2.552s 6388 KiB
29 Időlimit túllépés 2.53s 6112 KiB
30 Időlimit túllépés 2.543s 6288 KiB
31 Időlimit túllépés 2.561s 6348 KiB
32 Időlimit túllépés 2.563s 6344 KiB
subtask6 0/10
33 Időlimit túllépés 2.546s 6440 KiB
34 Időlimit túllépés 2.575s 6320 KiB
35 Időlimit túllépés 2.563s 6340 KiB
36 Időlimit túllépés 2.543s 6396 KiB
37 Időlimit túllépés 2.586s 6436 KiB
38 Időlimit túllépés 2.569s 6260 KiB