Submission #3770883


Source Code Expand

#include <cstdio>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
typedef long long ll;

int n;
int k;
int nQuery;
int vs[2000+10];

int main(void) {
  scanf("%d%d%d", &n, &k, &nQuery);
  set<int> ss;
  REP(i, n) {
    scanf("%d", &vs[i]);
    ss.insert(vs[i]);
  }

  int res = 2000000000;
  for(int v : ss) {
    vector<int> cands;
    { // init
      vector<int> sorted;
      REP(i, n) {
        if(vs[i] < v) {
          sort(sorted.begin(), sorted.end());
          REP(j, sorted.size() - k + 1) {
            cands.push_back(sorted[j]);
          }
          sorted.clear();
        } else {
          sorted.push_back(vs[i]);
        }
      }
      if((int)sorted.size() >= k) {
        sort(sorted.begin(), sorted.end());
        REP(j, sorted.size() - k + 1) {
          cands.push_back(sorted[j]);
        }
      }
    }
    if((int)cands.size() >= nQuery) {
      sort(cands.begin(), cands.end());
      res = min(res, cands[nQuery-1] - v);
    }
  }
  printf("%d\n", res);
  
  return 0;
}

Submission Info

Submission Time
Task E - Range Minimum Queries
User ush
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1178 Byte
Status AC
Exec Time 87 ms
Memory 384 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:18:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &n, &k, &nQuery);
                                   ^
./Main.cpp:21:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &vs[i]);
                        ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 54
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 42 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 3 ms 256 KB
subtask_1_07.txt AC 29 ms 384 KB
subtask_1_08.txt AC 27 ms 384 KB
subtask_1_09.txt AC 22 ms 384 KB
subtask_1_10.txt AC 1 ms 256 KB
subtask_1_11.txt AC 34 ms 384 KB
subtask_1_12.txt AC 87 ms 384 KB
subtask_1_13.txt AC 56 ms 384 KB
subtask_1_14.txt AC 33 ms 384 KB
subtask_1_15.txt AC 40 ms 384 KB
subtask_1_16.txt AC 31 ms 384 KB
subtask_1_17.txt AC 45 ms 384 KB
subtask_1_18.txt AC 85 ms 384 KB
subtask_1_19.txt AC 85 ms 384 KB
subtask_1_20.txt AC 58 ms 384 KB
subtask_1_21.txt AC 71 ms 384 KB
subtask_1_22.txt AC 33 ms 384 KB
subtask_1_23.txt AC 20 ms 256 KB
subtask_1_24.txt AC 31 ms 256 KB
subtask_1_25.txt AC 18 ms 256 KB
subtask_1_26.txt AC 17 ms 384 KB
subtask_1_27.txt AC 10 ms 256 KB
subtask_1_28.txt AC 14 ms 256 KB
subtask_1_29.txt AC 44 ms 384 KB
subtask_1_30.txt AC 2 ms 256 KB
subtask_1_31.txt AC 34 ms 384 KB
subtask_1_32.txt AC 39 ms 384 KB
subtask_1_33.txt AC 30 ms 384 KB
subtask_1_34.txt AC 30 ms 384 KB
subtask_1_35.txt AC 31 ms 384 KB
subtask_1_36.txt AC 30 ms 384 KB
subtask_1_37.txt AC 32 ms 384 KB
subtask_1_38.txt AC 25 ms 384 KB
subtask_1_39.txt AC 20 ms 384 KB
subtask_1_40.txt AC 37 ms 384 KB
subtask_1_41.txt AC 12 ms 256 KB
subtask_1_42.txt AC 9 ms 256 KB
subtask_1_43.txt AC 11 ms 256 KB
subtask_1_44.txt AC 11 ms 256 KB
subtask_1_45.txt AC 27 ms 384 KB
subtask_1_46.txt AC 2 ms 256 KB
subtask_1_47.txt AC 30 ms 384 KB
subtask_1_48.txt AC 30 ms 384 KB