제출 #1181664

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1181664		nuutsnoynton	Bigger segments (IZhO19_segments)	C++20	0 / 100	0 ms	328 KiB

segments

#include<bits/stdc++.h>

using namespace std;
using ll = long long;
ll dp[3003][3003], a[3002], pre[3002];
vector < ll > V[3003];
ll Sum(ll x, ll y) {
	return pre[y] - pre[x - 1];
}

int main() {
	ll n, m, s, sum,sum1, r, x, y, i, j, ans, t, cnt;

	cin >> n;
	
	
	pre[0] = 0;
	for (i = 1; i <= n; i ++) {
		cin >> a[i];
		pre[i] = pre[i - 1] + a[i];
		V[i].push_back(0);
	}
	vector < ll > v, q;
	q.push_back(0);
	v.push_back(0);
	v.push_back(pre[1]* 2);
	q.push_back(pre[1]);
	V[1].push_back(pre[1]);
	for (i = 2; i <= n; i ++) {
		if ( v.back() <= pre[i]) {
			r = v.size() - 1;
			sum1 = pre[i] - q[q.size() - 2];
			//cout << i << " A " << sum1 << endl;
			ans = 0;
			for ( j = 0; j < V[r].size(); j ++) {
			//	cout << V[r][j] << " " << sum1 - V[r][j] << "\n";
				if ( V[r][j] <= (sum1 - V[r][j])) ans = j;
			}
			//cout << ans << " " << pre[i] + (sum1 - V[r][ans]) << " " << pre[i] << endl;
			q.push_back(pre[i]);
			v.push_back(pre[i] + (sum1 - V[r][ans]));
			//cout << v.back() << "SR" << endl;
			V[r + 1].push_back(sum1 - V[r][ans]);
		}
		else {
			r = upper_bound(v.begin(), v.end(), pre[i]) - v.begin();
			r --;
			while (r  >= 0) {
				s = pre[i] - q[r];
				V[r + 1].push_back(s);
				r --;
			}
		}
	}
	
	cout << v.size() - 1<< endl;
}

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