Submission #1247596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247596		nqknht	San (COCI17_san)	C++20	120 / 120	190 ms	4408 KiB

san

#include <bits/stdc++.h>

#define ll long long
#define fi first
#define se second
#define len(s) (ll) s.size()

const ll I = 1050000 + 9;

using namespace std;

ll n, k, h[41], g[41];
ll rs = 0;
vector<ll> bag[41];
vector<ll> box;
map<ll, ll> id;

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> h[i] >> g[i];
        if (id[h[i]] == 0)
        {
            box.push_back(h[i]);
            id[h[i]] = 1;
        }
    }
    sort(box.begin(), box.end());
    for (int i = 0; i < len(box); i++)
        id[box[i]] = i + 1;
    int mid = n / 2;
    for (int bit = 1; bit < (1 << (n - mid)); bit++)
    {
        ll sum = 0, pre = 0, sav = -1, sw = 1;
        for (int i = 0; i < (n - mid); i++)
        {
            if (((1 << i) & bit) == 0)
                continue;
            if (sav == -1)
                sav = id[h[mid + i + 1]];
            if (h[mid + i + 1] < pre)
            {
                sw = 0;
                break;
            }
            sum += g[mid + i + 1];
            pre = h[mid + i + 1];
        }
        if (sw == 0)
            continue;
        bag[sav].push_back(sum);
        if (sum >= k)
            rs++;
    }
    for (int i = 1; i <= len(box); i++)
        if (!bag[i].empty())
            sort(bag[i].begin(), bag[i].end());
    for (int bit = 1; bit < (1 << mid); bit++)
    {
        ll sum = 0, sav = 0, pre = 0, sw = 1;
        for (int i = 0; i < mid; i++)
        {
            if (((1 << i) & bit) == 0)
                continue;
            if (h[i + 1] < pre)
            {
                sw = 0;
                break;
            }
            sav = id[h[i + 1]];
            sum += g[i + 1];
            pre = h[i + 1];
        }
        if (sw == 0)
            continue;
        if (sum >= k)
            rs++;
        for (int i = sav; i <= len(box); i++)
        {
            if (bag[i].empty())
                continue;
            auto it = lower_bound(bag[i].begin(), bag[i].end(), k - sum) - bag[i].begin();
            rs += len(bag[i]) - it;
        }
    }
    cout << rs;
    return 0;
}

• Subtask 1: 24 / 24
• Subtask 2: 24 / 24
• Subtask 3: 24 / 24
• Subtask 4: 24 / 24
• Subtask 5: 24 / 24