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
Task E - Range Minimum Queries
User iwashi31
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1676 Byte
Status
Exec Time 166 ms
Memory 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