Contest Duration: ~ (local time) (100 minutes) Back to Home

Submission #2567234

Source Code Expand

Copy
```#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define itrep(i, a) for (auto i = (a).begin(); i != (a).end(); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()
#define mp(a, b) make_pair((a), (b))

using namespace std;

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, -1, 0, 1 };

template<class T> void inputVector(vector<T>& v, int n) {
v.resize(n);
for (int i = 0; i < v.size(); i++) cin >> v[i];
}

signed main() {
int N, K, Q;
cin >> N >> K >> Q;

vector<int> A;
inputVector(A, N);

set<int> st;
for (int num : A) {
st.insert(num);
}

int ret = INT_MAX;
for (int num : st) {
vector<int> canUse;

priority_queue<int> q;
rep(i, N) {
if (A[i] >= num) {
q.push(-A[i]);
} else {
while (q.size() >= K) {
canUse.push_back(-q.top());
q.pop();
}
while (!q.empty()) q.pop();
}
}
while (q.size() >= K) {
canUse.push_back(-q.top());
q.pop();
}

//cerr << "num:" << num << endl;
//for (int num2 : canUse) cerr << num2 << " ";
//cerr << endl;

if (canUse.size() < Q) break;

sort(all(canUse));

ret = min(ret, canUse[Q - 1] - canUse[0]);
}

cout << ret << endl;

return 0;
}
```

#### Submission Info

Submission Time 2018-05-26 21:51:35+0900 E - Range Minimum Queries iwashi31 C++14 (GCC 5.4.1) 600 1676 Byte AC 166 ms 512 KB

#### Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
All 600 / 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 44 ms 384 KB
subtask_1_04.txt 2 ms 256 KB
subtask_1_05.txt 1 ms 256 KB
subtask_1_06.txt 2 ms 256 KB
subtask_1_07.txt 38 ms 384 KB
subtask_1_08.txt 3 ms 384 KB
subtask_1_09.txt 38 ms 512 KB
subtask_1_10.txt 2 ms 256 KB
subtask_1_11.txt 11 ms 384 KB
subtask_1_12.txt 105 ms 384 KB
subtask_1_13.txt 45 ms 384 KB
subtask_1_14.txt 10 ms 384 KB
subtask_1_15.txt 39 ms 384 KB
subtask_1_16.txt 3 ms 384 KB
subtask_1_17.txt 45 ms 384 KB
subtask_1_18.txt 166 ms 384 KB
subtask_1_19.txt 160 ms 384 KB
subtask_1_20.txt 132 ms 384 KB
subtask_1_21.txt 150 ms 384 KB
subtask_1_22.txt 3 ms 384 KB
subtask_1_23.txt 27 ms 384 KB
subtask_1_24.txt 44 ms 512 KB
subtask_1_25.txt 12 ms 384 KB
subtask_1_26.txt 13 ms 384 KB
subtask_1_27.txt 4 ms 384 KB
subtask_1_28.txt 2 ms 384 KB
subtask_1_29.txt 71 ms 384 KB
subtask_1_30.txt 2 ms 256 KB
subtask_1_31.txt 11 ms 384 KB
subtask_1_32.txt 30 ms 384 KB
subtask_1_33.txt 3 ms 384 KB
subtask_1_34.txt 3 ms 384 KB
subtask_1_35.txt 6 ms 384 KB
subtask_1_36.txt 3 ms 384 KB
subtask_1_37.txt 45 ms 512 KB
subtask_1_38.txt 2 ms 384 KB
subtask_1_39.txt 14 ms 384 KB
subtask_1_40.txt 2 ms 384 KB
subtask_1_41.txt 2 ms 384 KB
subtask_1_42.txt 2 ms 384 KB
subtask_1_43.txt 2 ms 384 KB
subtask_1_44.txt 2 ms 384 KB
subtask_1_45.txt 13 ms 384 KB
subtask_1_46.txt 2 ms 256 KB
subtask_1_47.txt 3 ms 384 KB
subtask_1_48.txt 3 ms 384 KB