Submission #341433

#	Time	Username	Problem	Language	Result	Execution time	Memory
341433		wwdd	Bigger segments (IZhO19_segments)	C++14	100 / 100	200 ms	67940 KiB

segments

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
vector<map<ll,ll> > go;
vl w,pr;
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	ll n;
	cin >> n;
	go.assign(n+1,map<ll,ll>());
	pr.push_back(0);
	for(int i=0;i<n;i++) {
		ll t;
		cin >> t;
		w.push_back(t);
		pr.push_back(pr.back()+w.back());
	}
	go[1][1] = pr[1];
	for(int i=1;i<=n;i++) {
		while(go[i].size() > 1) {
			go[i].erase(go[i].begin());
		}
		ll num = go[i].begin()->first;
		ll ko = go[i].begin()->second;
		int nx = lower_bound(pr.begin(),pr.end(),pr[i]+ko)-pr.begin();
		if(nx <= n) {
			if(go[nx].count(num+1)) {
				go[nx][num+1] = min(go[nx][num+1],pr[nx]-pr[i]);
			} else {
				go[nx][num+1] = pr[nx]-pr[i];
			}
		}
		if(i+1 <= n) {
			if(go[i+1].count(num)) {
				go[i+1][num] = min(go[i+1][num],ko+pr[i+1]-pr[i]);
			} else {
				go[i+1][num] = ko+pr[i+1]-pr[i];
			}
		}
	}
	cout << go[n].begin()->first << '\n';
}

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