Submission #1123702

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123702		njoop	San (COCI17_san)	C++17	120 / 120	98 ms	7696 KiB

san

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

struct building {
    int h, g;
};

building arr[50];
vector<int> res[50];
int n, k, ans;

void search1(int r, int cur, int last, int sum) {
    if(cur == r+1) {
        res[last].push_back(sum);
        return;
    }
    search1(r, cur+1, last, sum);
    if(last == 0 || arr[last].h <= arr[cur].h) search1(r, cur+1, cur, sum+arr[cur].g);
}

void search2(int r, int cur, int st, int last, int sum) {
    if(cur == r+1) {
        if(st == 0) return;
        res[st].push_back(sum);
        return;
    }
    search2(r, cur+1, st, last, sum);
    if(st == 0) search2(r, cur+1, cur, cur, sum+arr[cur].g);
    else if(arr[last].h <= arr[cur].h) search2(r, cur+1, st, cur, sum+arr[cur].g);
}

signed main() {
    cin >> n >> k;
    for(int i=1; i<=n; i++) {
        cin >> arr[i].h >> arr[i].g;
    }
    search1(n/2, 1, 0, 0);
    search2(n, (n/2)+1, 0, 0, 0);
    for(int i=0; i<=n; i++) {
        sort(res[i].begin(), res[i].end());
    }
    for(int i=0; i<=n/2; i++) {
        for(int j: res[i]) {
            for(int l=(n/2)+1; l<=n; l++) {
                if(arr[l].h < arr[i].h) continue;
                ans += res[l].size()-(upper_bound(res[l].begin(), res[l].end(), k-j-1) - res[l].begin());
            }
            if(j >= k) ans++;
        }
    }
    cout << ans;
    return 0;
}

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