Submission #1247488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247488		nqknht	San (COCI17_san)	C++20	96 / 120	182 ms	131072 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 = 11e5 + 9;

using namespace std;

ll n, k, h[I], g[I], pf[41][I], rs = 0;
vector<pair<ll, ll>> bag;
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.push_back({sum, sav});
        if (sum >= k)
            rs++;
    }
    sort(bag.begin(), bag.end());
    for (int i = 0; i < len(bag); i++)
        for (int j = 1; j <= len(box); j++)
            pf[j][i + 1] = pf[j][i] + (bag[i].se >= j);
    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++;
        int id = lower_bound(bag.begin(), bag.end(), make_pair(k - sum, sav)) - bag.begin();
        if (id == len(bag))
            continue;
        rs += pf[sav][len(bag)] - pf[sav][id];
    }
    cout << rs;
    return 0;
}

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