Submission #848147

#	Time	Username	Problem	Language	Result	Execution time	Memory
848147		hehege	Feast (NOI19_feast)	C++14	30 / 100	28 ms	11796 KiB

feast

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 3e5 + 9;
const int N2 = 5e3 + 9;
const int INF = 1e18 + 9;

int n, k, a[N], ps[N], f[N], pre[N2], dp[N2][N2];

namespace sub1 {
	bool valid (){
		for (int i = 1; i <= n; i++) if (a[i] < 0) return 0;
		return 1;
	}
	
	void solve (){
		int res = 0;
		for (int i = 1; i <= n; i++) res += a[i];
		cout << res;
	}
}

namespace sub2 {
	bool valid (){
		int x = 0;
		for (int i = 1; i <= n; i++){
			if (a[i] < 0) x++;
			if (x >= 2) break;
		}
		return x <= 1;
	}
	
	void solve (){
		int sum1 = 0, sum2 = 0, sumall = 0;
		bool flag = 0;
		for (int i = 1; i <= n; i++){
			if (a[i] < 0) flag = 1;
			else if (flag == 0) sum1 += a[i];
			else sum2 += a[i];
		}
		for (int i = 1; i <= n; i++) sumall += a[i];
		if (k == 1) cout << max (sum1, max (sum2, sumall));
		else cout << sum1 + sum2;
	}
}

namespace sub3 {
	bool valid (){
		return k == 1;
	}
	
	void solve (){
		for (int i = 1; i <= n; i++) ps[i] = ps[i - 1] + a[i];
		f[n] = ps[n];
		for (int i = n - 1; i >= 1; i--) f[i] = max (f[i + 1], ps[i]);
		int res = 0;
		for (int i = 1; i <= n; i++) res = max (res, f[i] - ps[i - 1]);
		cout << res;
	}
}

void sub6 (){
	dp[1][1] = a[1];
    pre[1] = a[1];
    int res = a[1];
    for (int i = 2; i <= n; i++){
    	for (int j = 1; j <= k; j++){
    		if (j > i) continue;
    		dp[i][j] = max (dp[i][j], max (dp[i - 1][j] + a[i], pre[j - 1] + a[i]));
    		pre[j] = max (pre[j], dp[i][j]);
    		res = max (res, dp[i][j]);
    	}
    }
    cout << res;
}

signed main (){
    ios_base::sync_with_stdio (false);
    cin.tie (NULL);
    cout.tie (NULL);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (sub1::valid ()) sub1::solve ();
    else if (sub2::valid ()) sub2::solve ();
    else if (sub3::valid ()) sub3::solve ();
    else sub6 ();
}

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