Codeforces #694 Div1 A. Strange Birthday Party

今年(2021年)もよろしくお願いします。
https://codeforces.com/contest/1471/problem/E

問題

N人の人とM個のプレゼントがある。
各人、M以下の正整数値K[i]が与えられている。
また、それぞれのプレゼントの価格C[i]が与えられている。
C[i]は昇順である。

各人に対し、以下のいずれかを行う。

• j≦K[i]であるjに対し、j番目のプレゼントを購入して渡す。この時コストC[j]がかかる。
• プレゼント相当の金額を直接渡す。この時コストC[K[i]]がかかる。

必要総コストの最小値を求めよ。

解法

K[i]の大きい人上位M人に、(より安い)プレゼントを購入できるかどうかをどん欲に当てはめればよい。

int T,N,M;
int K[303030];
int C[303030];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&T);
	while(T--) {
		scanf("%d%d",&N,&M);
		FOR(i,N) {
			scanf("%d",&K[i]);
			K[i]--;
		}
		sort(K,K+N);
		FOR(i,M) {
			scanf("%d",&C[i]);
		}
		ll S=0;
		FOR(i,N) S+=C[K[i]];
		ll ret=S;
		FOR(i,min(N,M)) {
			S-=C[K[N-1-i]];
			S+=C[i];
			ret=min(ret,S);
		}
		cout<<ret<<endl;
		
	}
}

まとめ

すでに16か月ビハインド…何問分あるんだ。