oj.uz

Submission #235380

# Submission time Handle Problem Language Result Execution time Memory
235380 2020-05-28T07:39:15 Z VEGAnn San (COCI17_san) C++14
120 / 120
 585 ms 47816 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) ((int)x.size())
#define MP make_pair
#define ft first
#define sd second
#define PB push_back
#define pli pair<ll,int>
using namespace std;
using namespace __gnu_pbds;
template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long ll;
const int N = 45;
const int PW = 22;
const int oo = 2e9;
ordered_set<pli> st;
vector<ll> vls[N];
ll h[N], g[N], k, sum[(1 << PW)], ans = 0;
int n, mid, nm[N];

void calc(int l, int r){
    int len = (r - l + 1);

    fill(sum, sum + (1 << len), -1);

    sum[0] = 0;

    for (int msk = 0; msk < (1 << len); msk++){
        if (sum[msk] < 0) continue;

//        cerr << sz(vls[1]) << '\n';

        if (sum[msk] >= k)
            ans++;

        int fi = 0, se = len - 1;

        while (fi < len && !(msk & (1 << fi)))
            fi++;

        while (se >= 0 && !(msk & (1 << se)))
            se--;

        for (int i = 0; i < len; i++)
            if (!(msk & (1 << i))){
                int id = i + l;
                ll nw_sum = sum[msk] + g[id];
                int nmsk = (msk | (1 << i));

                if (sum[nmsk] > 0) continue;

                if (msk == 0){
                    vls[i + l].PB(nw_sum);
                    sum[nmsk] = nw_sum;
                } else {
                    if (l == 0){
                        if (i > se && h[id] >= h[se + l]){
                            vls[i + l].PB(nw_sum);
                            sum[nmsk] = nw_sum;
                        }
                    } else {
                        if (i > se && h[id] >= h[se + l]){
                            vls[l + fi].PB(nw_sum);
                            sum[nmsk] = nw_sum;
                        }
                    }
                }
            }
    }
}

bool cmp(int _x, int _y){
    return h[_x] > h[_y];
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> k;

    for (int i = 0; i < n; i++) {
        cin >> h[i] >> g[i];
        nm[i] = i;
    }

    if (n == 1){
        cout << (g[0] >= k ? 1 : 0);
        return 0;
    }

    mid = n / 2;

    calc(0, mid - 1);

    calc(mid, n - 1);

    sort(nm, nm + mid, cmp);
    sort(nm + mid, nm + n, cmp);

    st.clear();

    int ite = 0;

    for (int i = 0, ptr = mid; i < mid; i++){
        while (ptr < n && h[nm[ptr]] >= h[nm[i]]){
            for (ll cr : vls[nm[ptr]])
                st.insert(MP(cr, ite++));
            ptr++;
        }

        for (ll cr : vls[nm[i]]){
            ll ost = k - cr;

            ans += sz(st) - st.order_of_key(MP(ost, -1));
        }
    }

    cout << ans;

    return 0;
}

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 5748 KB Output is correct
2 Correct 7 ms 1152 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 12140 KB Output is correct
2 Correct 12 ms 5248 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 585 ms 47816 KB Output is correct
2 Correct 34 ms 12132 KB Output is correct