oj.uz

Submission #1037822

# Submission time Handle Problem Language Result Execution time Memory
1037822 2024-07-29T08:54:44 Z fv3 Closing Time (IOI23_closing) C++17
9 / 100
 1000 ms 10100 KB 
#include "closing.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll INF = 1ll << 60ll;

int max_score(int N, int X, int Y, ll K,
              vector<int> U, vector<int> V, vector<int> W)
{
    // Subtask 4:
    // Find optimal distance X should move to the right
    // O(N²)

    int best = 0;
    for (int r = X; r < N; r++)
    {
        vector<ll> closingTime(N);

        int res = 0;
        ll k_sum = 0;

        for (int i = X + 1; i <= r; i++)
        {
            closingTime[i] = closingTime[i-1] + W[i-1];
            k_sum += closingTime[i];
            res++;
        }
        if (k_sum > K)
            break;

        for (int l = Y; l >= 0; l--)
        {
            int score = res;
            ll sum = k_sum;

            vector<ll> ct = closingTime;

            best = max(best, res);
            vector<ll> dist(N);
            for (int i = Y - 1; i >= l; i--)
            {
                dist[i] = dist[i+1] + W[i];
                sum += max(0ll, dist[i] - ct[i]);
                ct[i] = max(ct[i], dist[i+1] + W[i]);
                score++;
            }
            if (sum > K)
                break;

            priority_queue<pair<ll, int>> q;
            q.push({0, X});
            q.push({0, Y});

            while (!q.empty())
            {
                int s = q.top().second;

                if (sum - q.top().first > K)
                    break;
                sum -= q.top().first;
                score++;
                q.pop();

                if (s <= X && s)
                {
                    // Go left as X
                    dist[s-1] = dist[s] + W[s-1];
                    q.push({-max(0ll, dist[s-1] - ct[s-1]), s-1});
                }
                else if (s >= Y && s < N - 1)
                {
                    // Go right as Y
                    dist[s+1] = dist[s] + W[s];
                    q.push({-max(0ll, dist[s+1] - ct[s+1]), s+1});
                }
            }

            //cerr << ": " << r << " " << l << " = " << score << " (" << sum << ")\n";
            best = max(best, score);
        }
    }

    return best;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 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 Execution timed out 1041 ms 10100 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

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

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 436 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 436 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 0 ms 432 KB Output is correct
14 Correct 4 ms 600 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Incorrect 1 ms 348 KB 25th lines differ - on the 1st token, expected: '32', found: '31'
19 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 436 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 436 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 436 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 2 ms 348 KB Output is correct
13 Correct 0 ms 432 KB Output is correct
14 Correct 4 ms 600 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Incorrect 1 ms 348 KB 25th lines differ - on the 1st token, expected: '32', found: '31'
19 Halted 0 ms 0 KB -

Subtask #5
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 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 0 ms 348 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 0 ms 348 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 0 ms 348 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 0 ms 348 KB 1st lines differ - on the 1st token, expected: '6', found: '5'
2 Halted 0 ms 0 KB -