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());
}
}