Submission #73701311

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
struct Problem {
    int id;
    int k;
    long long a;
};
vector<Problem> get_top_unique(const vector<Problem>& candidates, int limit) {
    if (candidates.empty()) return {};
    vector<Problem> sorted = candidates;
    sort(sorted.begin(), sorted.end(), [](const Problem& x, const Problem& y) {
        return x.a > y.a;
    });
    vector<Problem> res;
    set<int> used_genres;
    for (const auto& p : sorted) {
        if (used_genres.find(p.k) == used_genres.end()) {
            res.push_back(p);
            used_genres.insert(p.k);
            if ((int)res.size() == limit) break;
        }
    }
    return res;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    if (!(cin >> N)) return 0;
    vector<Problem> probs(N);
    for (int i = 0; i < N; ++i) {
        probs[i].id = i; 
        cin >> probs[i].k >> probs[i].a;
    }
    vector<vector<Problem>> pref(N);
    vector<vector<Problem>> suff(N);
    vector<Problem> current_pool;
    current_pool.reserve(10);
    for (int i = 0; i < N; ++i) {
        current_pool.push_back(probs[i]);
        pref[i] = get_top_unique(current_pool, 4);
    }
    current_pool.clear();
    for (int i = N - 1; i >= 0; --i) {
        current_pool.push_back(probs[i]);
        suff[i] = get_top_unique(current_pool, 5);
    }
    long long max_total_interest = -1;
    for (int i = 0; i < N; ++i) {
        Problem p3 = probs[i];
        if (i == 0) continue;
        const vector<Problem>& left_candidates = pref[i-1];
        if (left_candidates.size() < 2) continue; 
        if (i == N - 1) continue;
        const vector<Problem>& right_candidates = suff[i+1];
        if (right_candidates.size() < 3) continue;
        for (int j = 0; j < (int)right_candidates.size(); ++j) {
            Problem p4 = right_candidates[j];
            if (p3.k == p4.k) continue;
            if (p4.id <= p3.id) continue; 
            long long best_left_sum = -1;
            for (int a = 0; a < (int)left_candidates.size(); ++a) {
                for (int b = a + 1; b < (int)left_candidates.size(); ++b) {
                    const Problem& c1 = left_candidates[a];
                    const Problem& c2 = left_candidates[b];
                    
                    if (c1.k == p3.k || c1.k == p4.k) continue;
                    if (c2.k == p3.k || c2.k == p4.k) continue;
                    
                    long long s = c1.a + c2.a;
                    if (s > best_left_sum) best_left_sum = s;
                }
            }
            if (best_left_sum == -1) continue;
            long long best_right_sum = -1;
            for (int a = 0; a < (int)right_candidates.size(); ++a) {
                for (int b = a + 1; b < (int)right_candidates.size(); ++b) {
                    const Problem& c1 = right_candidates[a];
                    const Problem& c2 = right_candidates[b];
                    if (c1.id <= p4.id || c2.id <= p4.id) continue;
                    
                    if (c1.k == p3.k || c1.k == p4.k) continue;
                    if (c2.k == p3.k || c2.k == p4.k) continue;
                    
                    long long s = c1.a + c2.a;
                    if (s > best_right_sum) best_right_sum = s;
                }
            }
            if (best_right_sum == -1) continue;
            long long total = p3.a + p4.a + best_left_sum + best_right_sum;
            if (total > max_total_interest) {
                max_total_interest = total;
            }
        }
    }

    cout << max_total_interest << endl;

    return 0;
}

Submission Info

Judge Result