oj.uz

Submission #840708

# Submission time Handle Problem Language Result Execution time Memory
840708 2023-08-31T16:08:11 Z Mahtimursu Closing Time (IOI23_closing) C++17
21 / 100
 1000 ms 10592 KB 
#include "closing.h"

#include <vector>

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#define NN (2 << 12)

int n, x, y;
ll k;

ll tree[2 * NN];
ll pt[3][NN];

void set(int k, ll x) {
    k += NN;
    tree[k] = x;

    for (k /= 2; k >= 1; k /= 2) {
        tree[k] = tree[2 * k] + tree[2 * k + 1];
    }
}

ll sum(int a, int b) {
    a += NN;
    b += NN;
    ll ans = 0;
    while (a <= b) {
        if (a % 2 == 1) ans += tree[a++];
        if (b % 2 == 0) ans += tree[b--];
        a /= 2; b /= 2;
    }

    return ans;
}

ll gt(int i, int a, int b) {
    ll ans = pt[i][b];
    if (a != 0) ans -= pt[i][a - 1];
    return ans;
}

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{

    n = N;
    x = X;
    y = Y;
    k = K;

    pt[0][x] = 0;
    for (int i = x - 1; i >= 0; --i) {
        pt[0][i] = W[i] + pt[0][i + 1];
    }
    for (int i = x + 1; i < n; ++i) {
        pt[0][i] = W[i - 1] + pt[0][i - 1];
    }

    pt[1][y] = 0;
    for (int i = y - 1; i >= 0; --i) {
        pt[1][i] = W[i] + pt[1][i + 1];
    }
    for (int i = y + 1; i < n; ++i) {
        pt[1][i] = W[i - 1] + pt[1][i - 1];
    }

    pt[2][0] = pt[1][0];
    for (int i = 1; i < n; ++i) {
        pt[2][i] = pt[2][i - 1] + max(pt[0][i], pt[1][i]);
        pt[1][i] += pt[1][i - 1];
        pt[0][i] += pt[0][i - 1];
    }

    /*for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << pt[i][j] << " ";
        }
        cout << endl;
    }*/

    int best = 0;

    for (int ar = x; ar < n; ++ar) {
        for (int bl = y; bl >= 0; --bl) {
            ll cur = 0;
            int ans = 0;
            if (bl <= ar) {
                cur += gt(2, bl, ar);
                ans += 2 * (ar - bl + 1);
            }

            // [a, bl-1]
            int tmp = min(bl - 1, ar);
            if (x <= tmp) {
                cur += gt(0, x, tmp);
                ans += (tmp) - x + 1;
            }

            // [ar + 1, b]
            tmp = max(ar + 1, bl);
            if (tmp <= y) {
                cur += gt(1, tmp, y);
                ans += y - tmp + 1;
            }

            // too large
            if (cur > k) break;
            ll left = k - cur;

            //cout << "ar: " << ar << " bl: " << bl << " cur: " << cur << " k: " << k << " ans: " << ans << endl;

            int li = min(bl - 1, x - 1);
            int ri = max(ar + 1, y + 1);

            while (true) {
                ll small = k;
                int use = 0;
                if (li >= 0) {
                    small = gt(0, li, li);
                    use = 1;
                }
                if (ri < n && gt(1, ri, ri) < small) {
                    small = gt(1, ri, ri);
                    use = 2;
                }

                if (use == 0 || left < small) break;

                if (use == 1) li--;
                if (use == 2) ri++;

                left -= small;
                ans++;
            }
            best = max(best, ans);
        }
    }


    return best;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 10592 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 12 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 50 ms 308 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 12 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 50 ms 308 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 4 ms 340 KB Output is correct
26 Execution timed out 1082 ms 340 KB Time limit exceeded
27 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -