yukicoder : No.2617 容量3のナップザック

こっちも普通に解けたね。
https://yukicoder.me/problems/no/2617

問題

N個のアイテムがあり、それぞれの重さと価値が与えられる。
重さは3以下の整数である。
合計3の重さまでのアイテムが入るナップサックがK個ある。
これらに詰め込める価値の総和の最大値を求めよ。

解法

同じ重さなら、価値の高い方から詰めるのが良い。
重さ2のアイテムを詰める数vを総当たりしよう。
その際、重さ2のアイテムと合わせ、重さ1のアイテムも上位v個は確定で詰められる。

残りのナップサックは(K-v)個あるので、重さ3のアイテムか、重さ1のアイテムを3個詰めるかのパターンのうち上位(K-v)個を選ぼう。
この時、重さ1のアイテムの3個セットの組み合わせはv%3の値に応じ3パターンあるので、各パターンにおける上位(K-v)個を更新していこう。

ll N,K,seed,A,B,M;
ll F[2020202];
vector<ll> W[4];
multiset<ll> L[3],R[3];
ll S[3];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K>>seed>>A>>B>>M;
	F[0]=seed;
	FOR(i,2*N) {
		F[i+1]=(F[i]*A+B)%M;
	}
	FOR(i,N) {
		x=F[i]%3+1;
		W[x].push_back(F[N+i]*x);
	}
	FOR(i,K+1) W[2].push_back(0);
	FOR(i,3*K+10) W[1].push_back(0);
	FOR(i,4) {
		sort(ALL(W[i]));
		reverse(ALL(W[i]));
	}
	FOR(i,3) {
		vector<ll> C;
		FOR(j,W[3].size()) {
			C.push_back(W[3][j]);
		}
		FOR(j,K+1) {
			ll a=W[1][i+j*3]+W[1][i+j*3+1]+W[1][i+j*3+2];
			C.push_back(a);
		}
		sort(ALL(C));
		reverse(ALL(C));
		FOR(j,K) L[i].insert(C[j]), S[i]+=C[j];
	}
	ll ma=0;
	ll sum=0;
	FOR(i,K+1) {
		if(i) sum+=W[2][i-1]+W[1][i-1];
		x=i%3;
		if(i>=3) {
			ll a=W[1][i-1]+W[1][i-2]+W[1][i-3];
			if(L[x].count(a)) {
				L[x].erase(L[x].find(a));
				S[x]-=a;
			}
		}
		while(L[x].size()>K-i) {
			ll a=*L[x].begin();
			S[x]-=a;
			L[x].erase(L[x].begin());
		}
		ma=max(ma,sum+S[x]);
	}
	cout<<ma<<endl;
	
}

まとめ

想定解法とは違うっぽい？