fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. int N, M, H, K;
  8. int S[1003];
  9. int C[1003];
  10. vector<pair<int, int> > stick;
  11.  
  12. int main() {
  13.     scanf("%d %d %d %d", &N, &M, &H, &K);
  14.     for (int i = 0; i < N; i++) {
  15.         scanf("%d", &S[i]);
  16.         C[i] = i;
  17.     }
  18.     for (int i = 0; i < M; i++) {
  19.         int a, b;
  20.         scanf("%d %d", &a, &b);
  21.         stick.emplace_back(b, a);
  22.     }
  23.  
  24.     sort(stick.begin(), stick.end());
  25.  
  26.     for (int i = M - 1; i >= 0; i--) {
  27.         int a = stick[i].second;
  28.         swap(S[a - 1], S[a]);
  29.     }
  30.  
  31.     int sum = 0;
  32.     for (int i = 0; i < K; i++) {
  33.         sum += S[i];
  34.     }
  35.  
  36.     int answer = sum;
  37.  
  38.     for (int i = 0; i < M; i++) {
  39.         int a = stick[i].second;
  40.         swap(S[a - 1], S[a]);
  41.  
  42.         int tmp = sum;
  43.         if (0 <= C[a - 1] && C[a - 1] < K) {
  44.             tmp -= (S[a] - S[a - 1]);
  45.         }
  46.         if (0 <= C[a] && C[a] < K) {
  47.             tmp -= (S[a - 1] - S[a]);
  48.         }
  49.         answer = min(answer, tmp);
  50.         swap(C[a - 1], C[a]);
  51.     }
  52.     printf("%d\n", answer);
  53.     return 0;
  54. }
Success #stdin #stdout 0s 3484KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/FCmmZN
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!