提出 #56582789

---

ソースコード 拡げる

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
	int n, k;
	cin >> n >> k;

	vector<ll> a(n), b(n);
	for (int i=0; i<n; i++){
		cin >> a[i] >> b[i];
	}

	// x=1,2,...,50 に対して、その上位 K 個を求める
	vector data(51, vector<ll>(k, -1));
	for (int x=1; x<51; x++){
		for (int i=0; i<n; i++){
			ll t = a[i] * x + b[i];
			for (int j=0; j<k; j++){
				if (data[x][j] == -1
					|| a[data[x][j]] * x + b[data[x][j]] <= t) {
					for (int l=k-1; l>=j+1; l--){
						data[x][l] = data[x][l-1];
					}
					data[x][j] = i;
					break;
				}
			}
		}
	}

	ll ans = 0;
	vector<bool> used(n);

	// p_1, ..., p_k を列挙
	auto dfs = [&](auto self, int num, ll now_value) -> void {
		if (num == k){			
			ans = max(ans, now_value);
			return;
		}

		ll t = min(now_value, 50LL);
		int cnt = 0;
		for (int i=0; i<k; i++){
			if (cnt >= k-num) break;
			if (used[data[t][i]]) continue;
			used[data[t][i]] = true;
			cnt += 1;
			self(self, num+1, a[data[t][i]] * now_value + b[data[t][i]]);
			used[data[t][i]] = false;
		}
	};

	dfs(dfs, 0, 1);
	cout << ans << endl;
	
}

提出情報

ジャッジ結果