JOI'09 本選3問目 あみだくじ

問題概要

あみだくじの横棒を一本消して,左k本がゴールで獲得する点数の総和を最小化せよ.

解法

注意:本来この解法はTLEするように制約は設定されているはずですが,出題された2009年と比較して計算速度が向上してるため現在のジャッジでは120ms程度でACします.

まず,横棒を消さずに一度シミュレーションします.i番目にに何番目からスタートした人がいるかがわかります.
ここから逆回ししていき,i番目にいる人がどこにゴールするかという情報もわかります.
ある横棒を消すという操作は,逆回しの際に上をswapするが下をswapしないということになるので,下のswapをする前にN本それぞれについて最小値を求めることができます.

ソースコード

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define FOR(i,n,m) for(int i=(n);i<(m);i++)
#define REP(i,n) FOR(i,0,n)
#define REPR(i,n) for(int i=(n);i>=0;i--)
#define all(vec) vec.begin(),vec.end()
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using P=pair<ll,ll>;
using PP=pair<ll,P>;
using vp=vector<P>;
using vpp=vector<PP>;
using vs=vector<string>;
#define fi first
#define se second
#define pb push_back
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}
const ll MOD=1000000007LL;
const int INF=1<<30;
const ll LINF=1LL<<60;
int main(){
    int n,m,h,k;
    cin>>n>>m>>h>>k;
    vl a(n);
    REP(i,n){
        cin>>a[i];
    }
    vp b(m);
    REP(i,m){
        cin>>b[i].se>>b[i].fi;
        b[i].se--;
    }
    sort(all(b));
    vl now(n);
    REP(i,n){
        now[i]=i;
    }
    REP(i,m){
        swap(now[b[i].se],now[b[i].se+1]);
    }
    ll sum=0;
    REP(i,n){
        if(now[i]<k){
            sum+=a[i];
        }
    }
    vl go(n);
    REP(i,n){
        go[i]=i;
    }
    ll ans=sum;
    REPR(i,m-1){
        swap(now[b[i].se],now[b[i].se+1]);
        ll cnt=0;
        REP(i,n){
            if(now[i]<k){
                cnt+=a[go[i]];
            }
        }
        swap(go[b[i].se],go[b[i].se+1]);
        chmin(ans,cnt);
    }
    cout<<ans<<endl;
    return 0;
}