Submission #370592

#	Time	Username	Problem	Language	Result	Execution time	Memory
370592		Seanliu	Bigger segments (IZhO19_segments)	C++17	0 / 100	161 ms	262148 KiB

segments

#include <iostream>
#include <utility>
#include <algorithm>
#include <deque>
#define pii pair<int,int> 
#define F first
#define S second
#define int long long int
using namespace std;

const int maxN = 5e5 + 326;
int N, arr[maxN];

deque<pii> dandiao[maxN];

signed main(){
	cin >> N;
	for(int i = 1; i <= N; i++){
		cin >> arr[i];
		arr[i] += arr[i - 1];
	}
	dandiao[0].push_back({0, 0});
	int ans = 0;
	for(int i = 1; i <= N; i++){
		deque<pii> tmp = deque<pii>();
		//cout << "i = " << i << endl;
		for(int j = 0; j < i; j++){
			auto p = upper_bound(dandiao[j].begin(), dandiao[j].end(), pii{arr[i] - arr[j], maxN});
			if(p == dandiao[j].begin()) continue;
			p--;
			//cout << "j = " << j << endl;
			//cout << "Found: " << p->F << " " << p->S << endl;
			tmp.emplace_back(arr[i] - arr[j], p->S + 1);
			//cout << "j = " << j << ", ans = " << p->S + 1 << endl;
			ans = max(ans, p->S + 1);
		}
		sort(tmp.begin(), tmp.end());
		for(auto [s, x] : tmp){
			if(!dandiao[i].size() || dandiao[i].back().S < x) dandiao[i].emplace_back(s, x);
		}
	}
	cout << ans << endl;
}

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