Submission #1197776

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197776		aarb_.tomatexd	Boat (APIO16_boat)	C++20	0 / 100	2094 ms	440 KiB

boat

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<pair<int, int>> range(n);
    for (int i = 0; i < n; ++i)
        cin >> range[i].first >> range[i].second;

    int total = 0;
    for (int mask = 1; mask < (1 << n); ++mask) {
        vector<int> idx;
        for (int i = 0; i < n; ++i)
            if (mask & (1 << i))
                idx.push_back(i);

        int count = 1;
        int prev_max = range[idx[0]].second;
        int ways = 0;

        // Brute-force all valid increasing assignments
        function<void(int, int)> dfs = [&](int pos, int prev) {
            if (pos == idx.size()) {
                ways++;
                return;
            }
            int i = idx[pos];
            for (int val = range[i].first; val <= range[i].second; ++val) {
                if (val > prev)
                    dfs(pos + 1, val);
            }
        };

        dfs(0, -1);
        total += ways;
    }
    cout << total << '\n';
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42