Submission #791466

#	Time	Username	Problem	Language	Result	Execution time	Memory
791466		Polar_Bear_2007	Feast (NOI19_feast)	C++17	41 / 100	158 ms	128056 KiB

feast

// #define MINHDEPTRAI "/Volumes/icebear/source_code/VS_code"
#ifdef MINHDEPTRAI
 
#include "/Library/Developer/CommandLineTools/usr/include/c++/v1/bits/stdc++.h"
#include <chrono>
#define __gcd(a, b) gcd(a, b)
using namespace std ::chrono;
#else
#include <bits/stdc++.h>
#endif
using namespace std;
#define foru(i, a, b) for (int i = a; i <= b; ++i)
#define ford(i, a, b) for (int i = a; i >= b; --i)
#define forr(i, l, r) for (int i = (l); i < (r); ++i)
#define IOS cin.tie(0),cout.tie(0)->sync_with_stdio(0);
#define mp(a, b) make_pair(a, b)
#define int long long
typedef pair<int, int>  pii;
typedef pair<pair<int, int>, int> piii;
#define endl '\n'
using ld = long double;

const string name_minh = "maxcross";
const int maxN = 2e3 + 5;
const int maxK =  2e5 + 5;
const int mod = 1e9 + 7;
const long long inf = 1e18;

int dp[maxN][maxN][2], cnt_negative, arr[maxN];
int n, k;


void k_1(){
    int current = 0, best = -inf;
    foru(i, 1, n){
        current = max(arr[i], current + arr[i]);
        best = max(best, current);
    }
    cout << best;
}
int prefix_sum[maxK];
void solve(){
    cin >> n >> k;
    foru(i, 1, n) {
        cin >> arr[i];

        prefix_sum[i] = prefix_sum[i - 1] + arr[i];
        if(arr[i] < 0) cnt_negative++;
    }

    if(k == 1){
        k_1();
        return;
    } 
    else if(cnt_negative == 0){
        cout << prefix_sum[n] << endl;
    }
    else if(cnt_negative == 1){
        foru(i, 1, n){
            if(arr[i] < 0){
                int beggin = prefix_sum[i - 1];
                int endd = prefix_sum[n] - prefix_sum[i];
                if(k >= 2) cout << beggin + endd << endl;
                else cout << max({beggin, endd, beggin + endd + arr[i]});

                break;
            }
        }
        
    }
    else {
        foru(i, 1, n){
            foru(j, 1, k){
                dp[i][j][0] = max(dp[i - 1][j][1], dp[i - 1][j][0]);
                dp[i][j][1] = max({dp[i - 1][j - 1][1], dp[i - 1][j][1], dp[i - 1][j - 1][0]}) + arr[i];
            }
        }

        cout << max(dp[n][k][0], dp[n][k][1]) << endl;
    }

}

signed  main() {
    IOS

    // #ifndef MINHDEPTRAI 
    // freopen((name_minh + ".in").c_str(), "r", stdin);
    //  freopen((name_minh + ".out").c_str(), "w", stdout);
    // #endif
    int t = 1;
    while(t--){
        solve();
    }
  
}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 0 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 0 / 29