Submission #1025986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025986		vjudge1	San (COCI17_san)	C++17	96 / 120	151 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;

            // cout << endl;
            // cout << i << " -- " << j << " : " << endl;

            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;

                // cout << p1 -> first << " " << p1 -> second << " -- " << total << endl;

                ans += p1 -> second * total;
            }
        }
    }

    cout << ans << endl;
}


/*


6 1
1 1
2 1
3 1
4 1
5 1
6 1
7 1
8 1
9 1
10 1
11 1
12 1
13 1
14 1
15 1
16 1
17 1
18 1
19 1
20 1
21 1
22 1
23 1
24 1
25 1
26 1
27 1
28 1
29 1
30 1
31 1
32 1
33 1
34 1
35 1
36 1 
37 1
38 1
39 1
40 1



*/

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