はやし屋

競技プログラミングのメモ きたない

AOJ 0540: Amidakuji

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0540

辿るとできる
面倒だった
無駄なくやるとよい

#include<algorithm>
#include<iostream>
#include<vector>
#include<map>

using namespace std;

int main(){
  int n , m , h , k;
  while(cin >> n >> m >> h >> k &&(n|m|h|k)){
    vector < int > wi[h];
    vector < int > point(n) , p(n);

    for(int i = 0 ; i < n ; ++i){
      cin >> point[i];
      p[i] = i;
    }

    for(int i = 0 ; i < m ; ++i){
      int a,b;
      cin >> a >> b;
      wi[b-1].push_back(a-1);
    }

    for(int i = h-1 ; i >= 0 ; --i){
      for(int j = 0 ; j < wi[i].size() ; ++j){
	int a = wi[i][j];
	swap(point[a],point[a+1]);
      }
    }


    int AL = 0 ;
    for(int i = 0 ; i < k ; ++i)AL += point[i];
    int ret = AL;

    for(int i = 0 ; i < h ; ++i){
      for(int j = 0 ; j < wi[i].size() ; ++j){
	int a = wi[i][j];
	int A = p[a];
	int B = p[a+1];
	swap(p[a],p[a+1]);
	if(A > B)swap(A,B);
	if(A < k && B >= k && point[A] > point[B]){
	  ret = min(ret,AL-point[A]+point[B]);
	}
      }
    }
    cout << ret << endl;
  }
  return 0;
}