AOJ 0540: Amidakuji

横棒を通るときに、番号をその棒に記録しておけば、もう片方から来たときにO(1)で交差してることが分かります。
交差を切ることで、得点を入れ替えることができるから、最も得点差(点数を減らせる量)の大きいものを求めれば良いです。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAX_N 1000

int n,m,h,k;
int point[MAX_N+1],score[MAX_N+1],cross[MAX_N+1][MAX_N];

int main(){
	while(scanf("%d%d%d%d",&n,&m,&h,&k),n){
		memset(point,0,sizeof(point));
		memset(cross,0,sizeof(cross));
		
		for(int i = 1; i <= n; i++) scanf("%d",point+i);
		for(int i = 0; i < m; i++){
			int a,b;
			scanf("%d%d,",&a,&b);
			cross[a][b-1] = -1;//-1で初期化しておく
		}
		
		int cut = 0;
		for(int i = 1; i <= n; i++){
			int pos = i;
			int swp = 0;
			for(int j = 0; j < h; j++){
				if(cross[pos][j]){
					if(cross[pos][j] == -1){
						cross[pos][j] = i;
					}else{
						int t = cross[pos][j];
						if(t<=k && k<i && swp<score[t]){
							swp = score[t];
						}
					}
					pos++;
				}else if(cross[pos-1][j]){
					pos--;
					if(cross[pos][j] == -1){
						cross[pos][j] = i;
					}else{
						int t = cross[pos][j];
						if(t<=k && k<i && swp<score[t]){
							swp = score[t];
						}
					}
				}
			}
			score[i] = point[pos];
			cut = max(cut,swp-score[i]);
		}
		
		int ans = -cut;
		for(int i = 1; i <= k; i++) ans += score[i];
		printf("%d\n",ans);
	}
	return 0;
}