oj.uz

Submission #840041

# Submission time Handle Problem Language Result Execution time Memory
840041 2023-08-31T02:46:50 Z cjoa Closing Time (IOI23_closing) C++17
0 / 100
 1000 ms 6492 KB 
#include "closing.h"

#include <vector>
#include <algorithm>

#include <iostream>

using namespace std;

using llong = long long;

const llong INF = 4e18;

vector<llong> F(int N, const vector<int>& W, int src) {
    vector<llong> V(N + 1, INF);
    V[0] = V[1] = 0;
    llong sum_left = 0, sum_left2 = 0;
    for (int l = src; l >= 0; --l) {
        llong sum_right = 0, sum_right2 = 0;
        for (int r = src; r < N; ++r) {
            int len = r - l + 1;
            V[len] = min(V[len], sum_left2 + sum_right2);
            if (r+1 < N) {
                sum_right += W[r];
                sum_right2 += sum_right;
            }
        }
        if (l > 0) {
            sum_left += W[l-1];
            sum_left2 += sum_left;
        }
    }

    for (int len = N-1; len >= 1; len--) {
        if (V[len] > V[len+1])
            V[len] = V[len+1];
    }

/*
    cerr << "src: " << src << endl;
    for (int len = 1; len <= N; len++)
        cerr << V[len] << ' ';
    cerr << endl;
*/

    return V;
}

int max_score(int N, int X, int Y, long long K,
              std::vector<int> U, std::vector<int> V, std::vector<int> W)
{
    // subtasks 2, 3, and 4
//  cerr << "K: " << K << endl;

    vector<llong> VX = F(N, W, X);
    vector<llong> VY = F(N, W, Y);

    int res = 0;
    for (int lenX = 1; lenX <= N and VX[lenX] <= K; lenX++) {
        auto it = upper_bound(VY.begin(), VY.end(), K - VX[lenX]);
        int lenY = it - VY.begin() - 1;
    //  cerr << "lenX: " << lenX << "  lenY: " << lenY << endl;
        res = max(res, lenX + lenY);
    }

    return res;
}

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 Execution timed out 1067 ms 6492 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '30', found: '24'
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '30', found: '24'
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB 1st lines differ - on the 1st token, expected: '30', found: '24'
3 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 -