oj.uz

Submission #708020

# Submission time Handle Problem Language Result Execution time Memory
708020 2023-03-10T19:31:15 Z Johann Uplifting Excursion (BOI22_vault) C++14
5 / 100
 5000 ms 8892 KB 
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
typedef vector<ll> vi;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

const int MAXSIZE = 1000000;

void resetPQ(priority_queue<pii, vpii> &q, int cut)
{
    priority_queue<pii, vpii> qq;
    while (!q.empty())
    {
        pii tmp = q.top();
        q.pop();
        if (tmp.second >= cut)
            qq.push(tmp);
    }
    swap(q, qq);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll M, L;
    cin >> M >> L;
    vi A(2 * M + 1);
    for (int i = 0; i < sz(A); ++i)
        cin >> A[i];

    vi dp(MAXSIZE, -1);
    ll center = MAXSIZE / 2;
    dp[center] = A[M];
    for (int foo = 0; foo < 2; ++foo)
    {
        reverse(all(A)), reverse(all(dp));
        for (ll m = 1; m <= M; ++m)
        {
            ll maxNum = A[m + M];
            for (ll r = 0; r < m; ++r)
            {
                priority_queue<pii, vpii> q;
                for (int i = 0; m * i + r < sz(dp); ++i)
                {
                    int idx = m * i + r;
                    while (!q.empty() && q.top().second < idx - maxNum * m)
                        q.pop();
                    if (sz(q) > 2 * m)
                        resetPQ(q, idx - maxNum * m);
                    if (dp[idx] != -1)
                        q.push({dp[idx] - i, idx});
                    if (!q.empty())
                        dp[idx] = i + q.top().first;
                }
            }
        }
    }

    ll ans = -1;
    if (0 <= center + L && center + L < sz(dp))
        ans = dp[center + L];
    if (ans == -1)
        cout << "impossible\n";
    else
        cout << ans << "\n";

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8148 KB Output is correct
2 Correct 22 ms 8148 KB Output is correct
3 Correct 9 ms 8108 KB Output is correct
4 Correct 59 ms 8132 KB Output is correct
5 Correct 865 ms 8148 KB Output is correct
6 Correct 1121 ms 8164 KB Output is correct
7 Correct 530 ms 8148 KB Output is correct
8 Correct 921 ms 8148 KB Output is correct
9 Correct 2548 ms 8148 KB Output is correct
10 Correct 436 ms 8148 KB Output is correct
11 Correct 516 ms 8148 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8148 KB Output is correct
2 Correct 22 ms 8148 KB Output is correct
3 Correct 9 ms 8108 KB Output is correct
4 Correct 59 ms 8132 KB Output is correct
5 Correct 865 ms 8148 KB Output is correct
6 Correct 1121 ms 8164 KB Output is correct
7 Correct 530 ms 8148 KB Output is correct
8 Correct 921 ms 8148 KB Output is correct
9 Correct 2548 ms 8148 KB Output is correct
10 Correct 436 ms 8148 KB Output is correct
11 Correct 516 ms 8148 KB Output is correct
12 Correct 17 ms 8148 KB Output is correct
13 Correct 17 ms 8128 KB Output is correct
14 Correct 8 ms 8148 KB Output is correct
15 Correct 57 ms 8148 KB Output is correct
16 Correct 864 ms 8148 KB Output is correct
17 Correct 1160 ms 8168 KB Output is correct
18 Correct 595 ms 8152 KB Output is correct
19 Correct 833 ms 8068 KB Output is correct
20 Correct 2533 ms 8272 KB Output is correct
21 Correct 532 ms 8148 KB Output is correct
22 Correct 424 ms 8128 KB Output is correct
23 Execution timed out 5024 ms 8152 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #3-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 8128 KB Output is correct
2 Execution timed out 5047 ms 8892 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 8128 KB Output is correct
2 Execution timed out 5047 ms 8892 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 8128 KB Output is correct
2 Execution timed out 5047 ms 8892 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8148 KB Output is correct
2 Correct 22 ms 8148 KB Output is correct
3 Correct 9 ms 8108 KB Output is correct
4 Correct 59 ms 8132 KB Output is correct
5 Correct 865 ms 8148 KB Output is correct
6 Correct 1121 ms 8164 KB Output is correct
7 Correct 530 ms 8148 KB Output is correct
8 Correct 921 ms 8148 KB Output is correct
9 Correct 2548 ms 8148 KB Output is correct
10 Correct 436 ms 8148 KB Output is correct
11 Correct 516 ms 8148 KB Output is correct
12 Correct 59 ms 8128 KB Output is correct
13 Execution timed out 5047 ms 8892 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #5-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 8128 KB Output is correct
2 Execution timed out 5047 ms 8892 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8148 KB Output is correct
2 Correct 22 ms 8148 KB Output is correct
3 Correct 9 ms 8108 KB Output is correct
4 Correct 59 ms 8132 KB Output is correct
5 Correct 865 ms 8148 KB Output is correct
6 Correct 1121 ms 8164 KB Output is correct
7 Correct 530 ms 8148 KB Output is correct
8 Correct 921 ms 8148 KB Output is correct
9 Correct 2548 ms 8148 KB Output is correct
10 Correct 436 ms 8148 KB Output is correct
11 Correct 516 ms 8148 KB Output is correct
12 Correct 17 ms 8148 KB Output is correct
13 Correct 17 ms 8128 KB Output is correct
14 Correct 8 ms 8148 KB Output is correct
15 Correct 57 ms 8148 KB Output is correct
16 Correct 864 ms 8148 KB Output is correct
17 Correct 1160 ms 8168 KB Output is correct
18 Correct 595 ms 8152 KB Output is correct
19 Correct 833 ms 8068 KB Output is correct
20 Correct 2533 ms 8272 KB Output is correct
21 Correct 532 ms 8148 KB Output is correct
22 Correct 424 ms 8128 KB Output is correct
23 Execution timed out 5024 ms 8152 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #6-1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 8128 KB Output is correct
2 Execution timed out 5047 ms 8892 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6-2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8148 KB Output is correct
2 Correct 22 ms 8148 KB Output is correct
3 Correct 9 ms 8108 KB Output is correct
4 Correct 59 ms 8132 KB Output is correct
5 Correct 865 ms 8148 KB Output is correct
6 Correct 1121 ms 8164 KB Output is correct
7 Correct 530 ms 8148 KB Output is correct
8 Correct 921 ms 8148 KB Output is correct
9 Correct 2548 ms 8148 KB Output is correct
10 Correct 436 ms 8148 KB Output is correct
11 Correct 516 ms 8148 KB Output is correct
12 Correct 17 ms 8148 KB Output is correct
13 Correct 17 ms 8128 KB Output is correct
14 Correct 8 ms 8148 KB Output is correct
15 Correct 57 ms 8148 KB Output is correct
16 Correct 864 ms 8148 KB Output is correct
17 Correct 1160 ms 8168 KB Output is correct
18 Correct 595 ms 8152 KB Output is correct
19 Correct 833 ms 8068 KB Output is correct
20 Correct 2533 ms 8272 KB Output is correct
21 Correct 532 ms 8148 KB Output is correct
22 Correct 424 ms 8128 KB Output is correct
23 Execution timed out 5024 ms 8152 KB Time limit exceeded
24 Halted 0 ms 0 KB -