oj.uz

Submission #1025962

# Submission time Handle Problem Language Result Execution time Memory
1025962 2024-07-17T11:53:15 Z vjudge1 San (COCI17_san) C++17
72 / 120
 171 ms 65536 KB 
#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.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 8536 KB Output is correct
2 Correct 2 ms 944 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 15780 KB Output is correct
2 Correct 7 ms 2140 KB Output is correct

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 171 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -