Submission #1270704

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270704		akari310	Feast (NOI19_feast)	C++17	71 / 100	28 ms	60996 KiB

feast

// Akari - nna310
/*
   link: https://ideone.com/6pIZZF
		   https://cyboj.ddns.net/problem/dttinh2526_thu2_9_9
*/

// #pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define L(i, j, n) for(int i = j; i <= n; ++i)
#define R(i, j, n) for(int i = n; i >= j; --i)
#define F(x, c) for(auto &x : c)
#define umap unordered_map
#define pb push_back
#define ve vector
#define se second
#define fi first
#define pe pair
using namespace std;
using ll = long long;
const int N = 300005;
const ll INF = (ll) 1e17 + 5;
const int MOD = 1000000007;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int n, k, a[N];
ll t[2005], f[2005][2005], g[2005][2005], res;
void sub1() {
	bool p = false;
	ll t = 0;
	L(i, 1, n){
		t += a[i];
	}
	ll r1 = 0, r2 = 0;
	L(i, 1, n) {
		if (a[i] < 0) {
			p = true;
			continue;
		}
		if (p) {
			r2 += a[i];
		} else {
			r1 += a[i];
		}
	}

	if (k == 1) {
		res = max({t, r1, r2});
	} else {
		res = r1 + r2;
	}

	cout << res;
}
void sub2() {
	ll s = 0;
	L(i, 1, n) {
		s = max(0ll, s + a[i]);
		res = max(res, s);
	}
	cout << res;
}
void sub34() {
	t[0] = 0;
	L(i, 1, n) t[i] = t[i - 1] + a[i];

	L(i, 0, n) {
		L(j, 0, k) f[i][j] = 0;
		f[i][0] = 0; // chọn 0 đoạn
	}

	L(i, 1, n) {
		L(sz, 1, k) {
			// không chọn đoạn kết thúc tại i
			f[i][sz] = f[i - 1][sz];
			// chọn đoạn [j+1..i] làm đoạn thứ sz
			L(j, 0, i - 1) {// tránh vô nghĩa
				ll tmp = t[i] - t[j]; // tổng đoạn [j + 1..i]
				f[i][sz] = max(f[i][sz], f[j][sz - 1] + tmp);
			}
		}
	}

	cout << f[n][k];
}

void sub5() {
	L(i, 0, n) { f[i][0] = 0; }

	// g[i][sz] — giá trị tối đa khi xét prefix 1..i, đã chọn sz đoạn,
	// và đoạn thứ sz bắt buộc kết thúc tại i
	// (tức phần đoạn đang “mở” kết thúc đúng ở vị trí i).

	// f[i][sz] — giá trị tối đa khi xét prefix 1..i, đã chọn sz đoạn,
	// không bắt buộc đoạn kết thúc ở i
	// (tức là tối đa trong mọi phương án chọn sz đoạn chỉ dùng phần tử trong 1..i).

	L(i, 1, n) {
		L(sz, 1, k) {
			// g[i][sz]: đoạn sz kết thúc tại i
			g[i][sz] = max(f[i - 1][sz - 1], g[i - 1][sz]) + a[i];
			// f[i][sz]: tổng lớn nhất với i phần tử, chọn sz đoạn
			f[i][sz] = max(f[i - 1][sz], g[i][sz]);
		}
	}

	cout << f[n][k];
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
// 	if (fopen("kd.inp", "r")) {
// 		freopen("kd.inp", "r", stdin);
// 		freopen("kd.out", "w", stdout);
// 	}
	cin >> n >> k;
	int d = 0;
	L(i, 1, n) {
		cin >> a[i];
		if (a[i] < 0) {
			++d;
		}
	}

	if (d <= 1) {
		sub1();
	} else if (k == 1) {
		sub2();
	} else {
		// sub34();
		sub5();
	}

	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