Same Sum Blocks

Same Sum Blocks (Easy)

https://codeforces.com/contest/1141/problem/F1

Same Sum Blocks (Hard)

https://codeforces.com/contest/1141/problem/F2

题解：

#include <bits/stdc++.h>
#define pii pair<int, int>
#define F first
#define S second
#define int long long
using namespace std;
const int MX = 1600;
int v[MX];
vector<pii> ins[MX];
main () {
	int n; cin >> n;
	unordered_map<int, int> mp;
	for(int i = 1; i <= n; i ++) cin >> v[i];
	pii ans = {0, 0};
	for(int i = 1; i <= n; i ++) {
		for(auto it: ins[i]) mp[it.F] = max(mp[it.F], it.S);
		int sum = 0;
		for(int j = i; j <= n; j ++) {
			sum += v[j];
			ans = max(ans, pii{mp[sum] + 1, sum});
			ins[j + 1].push_back({sum, mp[sum] + 1});
		}
	}
	cout << ans.F << '\n';
	set<pii> s;
	for(int i = 1; i <= n; i ++) {
		int sum = 0;
		for(int j = i; j <= n; j ++) {
			sum += v[j];
			if(sum == ans.S) {
				s.insert({i, j});
				break;
			}
		}
	}
	int last = n + 1;
	while(1) {
		while(s.size() and (--s.end()) -> S >= last) s.erase(--s.end());
		if(s.empty()) break; 
		cout << ((--s.end()) -> F) << ' ' << ((--s.end()) -> S) << endl;
		last = (--s.end()) -> F;
		s.erase(--s.end());
	}
}