A1500 DOBRI 全站第一题解

#include <iostream>
#include <vector>
#include <numeric>

const int OFFSET = 200000;
const int MAX_SUM_SIZE = 400001;
bool two_sum_exists[MAX_SUM_SIZE];

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }

    int good_elements_count = 0;
    std::vector<int> prefix_elements;

    for (int i = 0; i < n; ++i) {
        bool is_good = false;
        int target = a[i];

        for (int element_j : prefix_elements) {
            int required_two_sum = target - element_j;
            if (required_two_sum >= -200000 && required_two_sum <= 200000) {
                if (two_sum_exists[required_two_sum + OFFSET]) {
                    is_good = true;
                    break;
                }
            }
        }

        if (is_good) {
            good_elements_count++;
        }

        for (int element_j : prefix_elements) {
            int new_two_sum = a[i] + element_j;
            two_sum_exists[new_two_sum + OFFSET] = true;
        }
        int self_sum = a[i] + a[i];
        two_sum_exists[self_sum + OFFSET] = true;
        
        prefix_elements.push_back(a[i]);
    }

    std::cout << good_elements_count << '\n';

    return 0;
}