제출 #1023969

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1023969		yellowtoad	Bigger segments (IZhO19_segments)	C++17	37 / 100	1578 ms	9560 KiB

segments

#include <iostream>
using namespace std;

long long n, a[500010], sum, dp[500010], p[500010], cnt, pos;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1; i <= n; i++) {
		sum = a[i];
		for (int j = i-1; j >= 0; j--) {
			if (dp[j] <= sum) {
				dp[i] = sum;
				p[i] = j;
				break;
			}
			sum += a[j];
		}
	}
	pos = n;
	while (pos > 0) {
		pos = p[pos];
		cnt++;
	}
	cout << cnt << endl;
}

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 10 / 10
• Subtask 4: 0 / 36
• Subtask 5: 0 / 27