Codeforces #547 Div. 3 F - Same Sum Blocks (Hard) (R1900)

区間スケジューリングと聞いて

問題へのリンク

問題概要

要素からなる数列 が与えられる。以下の条件を満たす最大個数の区間を求めよ (どれか 1 つ復元せよ)。

• どの 2 つの区間も交差しない
• どの区間についても含まれる値の総和が等しい

制約

• 
• 

考えたこと

区間をすべて列挙しても 通りなので列挙はできる。

そうすると、区間の値の和として考えられる値も 通りになる。それぞれについて、区間スケジューリング問題を解けば良い。

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
using pint = pair<int,int>;

int main() {
    int N; cin >> N;
    vector<long long> a(N), s(N+1, 0);
    for (int i = 0; i < N; ++i) cin >> a[i], s[i+1] = s[i] + a[i];

    map<long long, vector<pint> > hash;
    for (int i = 0; i < N; ++i)
        for (int j = i+1; j <= N; ++j)
            hash[s[j]-s[i]].push_back(pint(i, j));

    int res = 0;
    vector<pint> ans;
    for (auto it : hash) {
        long long val = it.first;
        auto inters = it.second;

        sort(inters.begin(), inters.end(), [&](pint a, pint b) {
                return a.second < b.second; });

        long long cur = -(1LL<<60);
        vector<pint> sol;
        for (auto inter : inters) {
            if (cur <= inter.first) {
                cur = inter.second;
                sol.push_back(inter);
            }
        }
        if (res < sol.size()) {
            res = sol.size();
            ans = sol;
        }
    }
    
    cout << res << endl;
    for (auto p : ans) {
        cout << p.first + 1 << " " << p.second << endl;
    }
}