Submission #1270435

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270435		duyanhchupapi	Feast (NOI19_feast)	C++20	71 / 100	49 ms	30792 KiB

feast

#include <bits/stdc++.h>
using namespace std; using ll = long long; const int N = 300005;
int n, k, a[N];
ll p[N], bit[N], dp[2002][2020];
void up(int id, ll val) {
	while(id <= n) bit[id] = max(bit[id], val), id += -id&id;
}

ll MAX(int id) {
	ll res = 0;
	while(id > 0) res = max(res, bit[id]), id -= -id&id;
	return res;	
}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> k;
	int mn = (int)2e9, dem = 0;
	for(int i=1;i<=n;++i) cin >> a[i], p[i] = p[i-1] + a[i], mn = min(mn, a[i]), dem += (a[i] < 0);
	if(mn >= 0) {
		cout << p[n]; return 0;
	}
	if(k == 1) {
		ll MIN = 0, ans = 0;
		for(int i=1;i<=n;++i) ans = max(ans, p[i] - MIN), MIN = min(MIN, p[i]);
		cout << ans;return 0;
	}
	if(dem == 1) {
		ll ans = 0;
		for(int i=1;i<=n;++i) ans += max(a[i], 0);
		cout << ans;return 0;
	}
	for(int j=1;j<=k;++j) {
		fill(bit,bit+n+1,0);
		for(int i=1;i<=n;++i) 
			up(i,dp[i][j-1] - p[i]), dp[i][j] = max(dp[i-1][j], p[i] + MAX(i));
	}
	cout << dp[n][k];
	return 0;
}

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