Submission #1025962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025962		vjudge1	San (COCI17_san)	C++17	72 / 120	171 ms	65536 KiB

san

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

typedef long long ll;

const int N = 42;
ll n, k, h[N], g[N];
map<ll, ll> lft[N], rght[N], tmp;

int main(){
    cin >> n >> k;
    for (int i = 1; i <= n; i ++)
        cin >> h[i] >> g[i];

    lft[0][0] = 1;
    for (int i = 1; i <= n / 2; i ++){
        tmp.clear();
        for (int j = 0; j < i; j ++){
            if (h[j] > h[i]) continue;
            for (auto [x, c] : lft[j]){
                tmp[x + g[i]] += c;
            }
        }
        lft[i] = tmp;
    }

    h[n + 1] = 1e9 + 7;
    rght[n + 1][0] = 1;
    for (int i = n; i > n / 2; i --){
        tmp.clear();
        for (int j = i + 1; j <= n + 1; j ++){
            if (h[i] > h[j]) continue;
            for (auto [x, c] : rght[j]){
                tmp[x + g[i]] += c;
            }
        }
        rght[i] = tmp;
    }

    ll ans = 0;
    for (int i = 0; i <= n / 2; i ++){
        for (int j = n / 2 + 1; j <= n + 1; j ++){
            if (h[i] > h[j]) continue;
            auto p1 = lft[i].end();
            auto p2 = rght[j].begin();

            ll total = 0;
            for (auto [x, c] : rght[j])
                total += c;

            while (p1 != lft[i].begin() and p2 != rght[j].end()){
                p1--;
                
                while (p2 != rght[j].end() and (p1 -> first) + (p2 -> first) < k){
                    total -= p2 -> second;
                    p2++;
                }
                if (p2 == rght[j].end()) break;

                ans += total;
            }
        }
    }

    cout << ans << endl;
}

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