oj.uz

Submission #1097800

# Submission time Handle Problem Language Result Execution time Memory
1097800 2024-10-08T09:40:36 Z tien1710 Triple Jump (JOI19_jumps) C++14
5 / 100
 4000 ms 2904 KB 
#include <iostream>
#include <vector>
#include <climits>

using namespace std;

// Hàm tìm tổng lớn nhất của 3 số với điều kiện x < y < z và y - x <= z - y trong khoảng [L, R]
int findMaxSumInRange(const vector<int>& arr, int L, int R) {
    // Nếu không đủ phần tử để tạo thành bộ ba, trả về 0
    if (R - L + 1 < 3) return 0;

    int maxSum = INT_MIN;

    // Duyệt qua tất cả các chỉ số y trong khoảng [L+1, R-1]
    for (int y = L + 1; y <= R - 1; ++y) {
        // Với mỗi y, tìm x trong khoảng [L, y-1] và z trong khoảng [y+1, R]
        for (int x = L; x < y; ++x) {
            for (int z = y + 1; z <= R; ++z) {
                // Kiểm tra điều kiện y - x <= z - y
                if (y - x <= z - y) {
                    // Tính tổng của bộ ba
                    int currentSum = arr[x] + arr[y] + arr[z];
                    // Cập nhật tổng lớn nhất
                    maxSum = max(maxSum, currentSum);
                }
            }
        }
    }

    return maxSum == INT_MIN ? 0 : maxSum; // Trả về 0 nếu không có bộ ba hợp lệ
}

int main() {
    int N;
    cin >> N;

    vector<int> arr(N);
    for (int i = 0; i < N; ++i) {
        cin >> arr[i];
    }

    int Q;
    cin >> Q;

    // Xử lý từng truy vấn với khoảng [L, R]
    for (int i = 0; i < Q; ++i) {
        int L, R;
        cin >> L >> R;
        L--; R--; // Chuyển về chỉ số 0-based

        // Gọi hàm tìm tổng lớn nhất của 3 số trong khoảng [L, R]
        int result = findMaxSumInRange(arr, L, R);

        // In kết quả cho truy vấn hiện tại
        cout << result << endl;
    }

    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 424 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 408 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Execution timed out 4083 ms 348 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4027 ms 2904 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 2 ms 348 KB Output is correct
5 Correct 2 ms 424 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 2 ms 408 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Execution timed out 4083 ms 348 KB Time limit exceeded
12 Halted 0 ms 0 KB -