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

输入 n(≤1500) 和长为 n 的数组 a(-1e5≤a[i]≤1e5)，下标从 1 开始。

你需要从 a 中选出尽量多的非空连续子数组，这些子数组不能重叠，且元素和相等。
输出子数组的个数 k，然后输出 k 行，每行两个数表示子数组的左右端点。可以按任意顺序输出，多种方案可以输出任意一种。

输入
7
4 1 2 2 1 5 3
输出
3
7 7
2 3
4 5

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

const int N = 1510;
typedef long long LL;
typedef pair<int, int> PII;

struct node{
    int l, r;
};
int n;
int s[N];
int a[N];

int main (){
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++){
        scanf("%d", &a[i]);
        s[i] = s[i - 1] + a[i];
    }
    unordered_map<int, vector<node>> hs;
    for(int j = 1; j <= n; j ++){
        for(int i = 1; i <= j; i ++){
            hs[s[j] - s[i - 1]].push_back({i, j});
        }
    }
    int res = 0;
    vector<node> ans;
    for(auto &[k, v] : hs){
        int sz = v.size();
        int cnt = 0, ed = -1e9;
        vector<node> s;
        for(auto &[l, r] : v){
            if(l > ed){
                ed = r;
                s.push_back({l, r});
                cnt ++;
            }
        }
        if(cnt > res){
            res = cnt;
            ans = s;
        }
    }
    printf("%d\n", res);
    for(auto &[k, v] : ans) printf("%d %d\n", k, v);
    return 0;
}