Submission #3010789
Source Code Expand
#include <iostream> #include <vector> #include <queue> #include <algorithm> #include <cmath> #include <iomanip> #include <map> #include <deque> using namespace std; #define REP(i,n) for(int i = 0; i < n; i++) #define ALL(v) v.begin(),v.end() typedef long long ll; typedef pair<int,int> pi; typedef pair<ll,ll> pll; typedef pair<string,string> pss; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<pi> vpi; typedef vector<ll> vll; typedef vector<vll> vvll; double EPS = 1e-9; int INFi = 1000000005; long long INFll = 1000000000000000005ll; double PI = acos(-1); int dirx[8] = {-1,0,0,1,-1,-1,1,1}; int diry[8] = {0,1,-1,0,-1,1,-1,1}; ll MOD = 1000000007; const int MAX_N = 2000; int N, K, Q; int A[MAX_N]; int main(){ cin >> N >> K >> Q; REP(i, N) cin >> A[i]; int ans = INFi; REP(i, N) { int X = A[i]; vvi vec; vi tmp; REP(j, N) { if(A[j] >= X) { tmp.push_back(A[j]); } else { vec.push_back(tmp); tmp.clear(); } if(j == N - 1 && !tmp.empty()) vec.push_back(tmp); } vi rms; REP(j, vec.size()) { sort(ALL(vec[j])); if(vec[j].size() >= K) { REP(k, vec[j].size() - K + 1) { rms.push_back(vec[j][k]); } } } sort(ALL(rms)); if(rms.size() >= Q) ans = min(ans, rms[Q - 1] - X); } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Range Minimum Queries |
User | yacropolisy |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 1451 Byte |
Status | AC |
Exec Time | 167 ms |
Memory | 384 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 600 / 600 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt, sample_03.txt |
All | 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 | AC | 1 ms | 256 KB |
sample_02.txt | AC | 1 ms | 256 KB |
sample_03.txt | AC | 1 ms | 256 KB |
subtask_1_01.txt | AC | 1 ms | 256 KB |
subtask_1_02.txt | AC | 1 ms | 256 KB |
subtask_1_03.txt | AC | 95 ms | 384 KB |
subtask_1_04.txt | AC | 2 ms | 256 KB |
subtask_1_05.txt | AC | 1 ms | 256 KB |
subtask_1_06.txt | AC | 7 ms | 256 KB |
subtask_1_07.txt | AC | 76 ms | 384 KB |
subtask_1_08.txt | AC | 103 ms | 384 KB |
subtask_1_09.txt | AC | 39 ms | 384 KB |
subtask_1_10.txt | AC | 36 ms | 256 KB |
subtask_1_11.txt | AC | 124 ms | 384 KB |
subtask_1_12.txt | AC | 167 ms | 384 KB |
subtask_1_13.txt | AC | 167 ms | 384 KB |
subtask_1_14.txt | AC | 118 ms | 384 KB |
subtask_1_15.txt | AC | 121 ms | 384 KB |
subtask_1_16.txt | AC | 120 ms | 384 KB |
subtask_1_17.txt | AC | 105 ms | 384 KB |
subtask_1_18.txt | AC | 113 ms | 384 KB |
subtask_1_19.txt | AC | 114 ms | 384 KB |
subtask_1_20.txt | AC | 85 ms | 384 KB |
subtask_1_21.txt | AC | 99 ms | 384 KB |
subtask_1_22.txt | AC | 96 ms | 384 KB |
subtask_1_23.txt | AC | 101 ms | 384 KB |
subtask_1_24.txt | AC | 127 ms | 384 KB |
subtask_1_25.txt | AC | 123 ms | 384 KB |
subtask_1_26.txt | AC | 101 ms | 384 KB |
subtask_1_27.txt | AC | 121 ms | 384 KB |
subtask_1_28.txt | AC | 103 ms | 384 KB |
subtask_1_29.txt | AC | 79 ms | 384 KB |
subtask_1_30.txt | AC | 82 ms | 256 KB |
subtask_1_31.txt | AC | 121 ms | 384 KB |
subtask_1_32.txt | AC | 120 ms | 384 KB |
subtask_1_33.txt | AC | 112 ms | 384 KB |
subtask_1_34.txt | AC | 112 ms | 384 KB |
subtask_1_35.txt | AC | 113 ms | 384 KB |
subtask_1_36.txt | AC | 111 ms | 384 KB |
subtask_1_37.txt | AC | 59 ms | 384 KB |
subtask_1_38.txt | AC | 52 ms | 384 KB |
subtask_1_39.txt | AC | 56 ms | 384 KB |
subtask_1_40.txt | AC | 71 ms | 384 KB |
subtask_1_41.txt | AC | 94 ms | 384 KB |
subtask_1_42.txt | AC | 77 ms | 384 KB |
subtask_1_43.txt | AC | 72 ms | 384 KB |
subtask_1_44.txt | AC | 76 ms | 384 KB |
subtask_1_45.txt | AC | 57 ms | 384 KB |
subtask_1_46.txt | AC | 59 ms | 256 KB |
subtask_1_47.txt | AC | 110 ms | 384 KB |
subtask_1_48.txt | AC | 112 ms | 384 KB |