Submission #625380

#	Time	Username	Problem	Language	Result	Execution time	Memory
625380		iomoon191	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	204 ms	2380 KiB

Main

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

#define foru(i, a, b) for(int i = a; i <= b; i++)
#define ford(i, a, b) for(int i = a; i >= b; i--)
#define sz(x) (int)(x).size()

#define pb push_back
#define fi first
#define se second
#define db(x) cerr << __LINE__ << " " << #x << " " << x << "\n"
using vi = vector<int>;
using pi = pair<int, int>;

/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/

const ll N = 505;
const ll inf = 1e9;
const ll mod = 1e9 + 7;

ll n, k;
vector<pi> state(N);
double dp[N][N];
 
void solve(){
	cin >> n >> k;
	state.resize(n);
	foru(i, 0, n - 1){
		cin >> state[i].fi >> state[i].se;
		if(state[i].se == -1){
			state[i].se = inf;
		}
	}
	sort(state.begin(), state.end(), [&](pi a, pi b){
		return a.se < b.se;
	});
	double res = inf;
	foru(i, 0, k){
		dp[0][0] = 0;
		foru(j, 1, k - i) dp[0][j] = inf;
		foru(j, 1, n){
			foru(f, 0, k - i){
				ll zz = j - f;
				auto kap = ((1 <= zz and zz <= i) ? 1.0 * state[j - 1].se / zz : 0);
				dp[j][f] = dp[j - 1][f] + kap; 
				if(f){
					dp[j][f] = min(dp[j][f], dp[j - 1][f - 1] + 1.0 * state[j - 1].fi / (i + 1));
				}
			}
		}
		res = min(res, dp[n][k - i]);
	}
	cout << fixed << setprecision(100) << res;
}

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t = 1; 
	while(t--){
		solve();
	}
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 33 / 33
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23