Advertisement
Guest User

Untitled

a guest
May 26th, 2018
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.39 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. signed main(){
  5. ios_base::sync_with_stdio(false);
  6. cin.tie(0);
  7. int n, k, q;
  8. cin >> n >> k >> q;
  9. vector<int> v(n);
  10. for (int i=0; i < n; i++) cin >> v[i];
  11. vector<pair<int, int> > srt;
  12. for (int i=0; i < n; i++) srt.push_back(make_pair(v[i], i));
  13. sort(srt.begin(), srt.end());
  14. int ans = 1e18;
  15. for (int i=0; i < n; i++){
  16. if (i!=0){
  17. if (srt[i-1].first == srt[i].first) continue;
  18. }
  19. vector<int> block;
  20. for (int j=0; j < i; j++) block.push_back(srt[j].second);
  21. block.push_back(-1);
  22. block.push_back(n);
  23. sort(block.begin(), block.end());
  24. vector<int> abl;
  25. for (int j=0; j < block.size() - 1; j++){
  26. vector<int> best;
  27. for (int p=block[j]+1; p <= block[j+1]-1; p++) best.push_back(v[p]);
  28. sort(best.begin(), best.end(), greater<int>());
  29. while (best.size() >= k){
  30. abl.push_back(best.back());
  31. best.pop_back();
  32. }
  33. }
  34. sort(abl.begin(), abl.end());
  35. if (abl.size() < q) continue;
  36. ans = min(ans, abl[q-1] - abl[0]);
  37. }
  38. cout << ans;
  39. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement