Submission #7618173


Source Code Expand

Copy
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define all(a) a.begin(), a.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using namespace std;
typedef long long ll;

int main(){

    int N, K, Q;
    cin >> N >> K >> Q;

    vector<int> A(N + 1);
    rep(i, N)cin >> A[i];
    A[N] = 0;

    int ans = 1000000000;
    rep(loop1, N){

        int minimum = A[loop1];
        vector<int> canuse;
        
        {
            priority_queue<int, vector<int>, greater<int>> que;
            int l = 0;
            rep(r, N + 1){
                if(A[r] < minimum){
                    if(r - l >= K){
                        for(int i = l; i < r; i++)que.push(A[i]);
                        for(int i = 0; i < r - l - K + 1; i++){
                            canuse.push_back(que.top());
                            que.pop();
                        }
                    }
                    l = r + 1;
                }
            }
        }

        if(canuse.size() >= Q){
            sort(all(canuse));
            chmin(ans, canuse[Q - 1] - minimum);
        }
        
    }

    cout << ans << endl;
    return 0;

}

Submission Info

Submission Time
Task E - Range Minimum Queries
User KoD
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1346 Byte
Status
Exec Time 165 ms
Memory 384 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
All 0 / 600 sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_47.txt, subtask_1_48.txt
Case Name Status Exec Time Memory
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB
subtask_1_01.txt 1 ms 256 KB
subtask_1_02.txt 1 ms 256 KB
subtask_1_03.txt 80 ms 256 KB
subtask_1_04.txt 2 ms 256 KB
subtask_1_05.txt 1 ms 256 KB
subtask_1_06.txt 3 ms 256 KB
subtask_1_07.txt 45 ms 256 KB
subtask_1_08.txt 28 ms 256 KB
subtask_1_09.txt 60 ms 256 KB
subtask_1_10.txt 50 ms 256 KB
subtask_1_11.txt 45 ms 256 KB
subtask_1_12.txt 154 ms 256 KB
subtask_1_13.txt 125 ms 256 KB
subtask_1_14.txt 34 ms 256 KB
subtask_1_15.txt 45 ms 256 KB
subtask_1_16.txt 35 ms 256 KB
subtask_1_17.txt 112 ms 256 KB
subtask_1_18.txt 159 ms 256 KB
subtask_1_19.txt 155 ms 256 KB
subtask_1_20.txt 127 ms 256 KB
subtask_1_21.txt 145 ms 256 KB
subtask_1_22.txt 105 ms 256 KB
subtask_1_23.txt 53 ms 384 KB
subtask_1_24.txt 150 ms 256 KB
subtask_1_25.txt 127 ms 256 KB
subtask_1_26.txt 31 ms 256 KB
subtask_1_27.txt 165 ms 256 KB
subtask_1_28.txt 30 ms 256 KB
subtask_1_29.txt 128 ms 256 KB
subtask_1_30.txt 122 ms 256 KB
subtask_1_31.txt 39 ms 256 KB
subtask_1_32.txt 42 ms 256 KB
subtask_1_33.txt 15 ms 256 KB
subtask_1_34.txt 15 ms 256 KB
subtask_1_35.txt 16 ms 256 KB
subtask_1_36.txt 15 ms 256 KB
subtask_1_37.txt 38 ms 256 KB
subtask_1_38.txt 6 ms 256 KB
subtask_1_39.txt 11 ms 256 KB
subtask_1_40.txt 45 ms 256 KB
subtask_1_41.txt 15 ms 256 KB
subtask_1_42.txt 8 ms 256 KB
subtask_1_43.txt 11 ms 256 KB
subtask_1_44.txt 12 ms 256 KB
subtask_1_45.txt 54 ms 256 KB
subtask_1_46.txt 66 ms 256 KB
subtask_1_47.txt 15 ms 256 KB
subtask_1_48.txt 15 ms 256 KB