Submission #625372

#	Time	Username	Problem	Language	Result	Execution time	Memory
625372		iomoon191	Let's Win the Election (JOI22_ho_t3)	C++17	11 / 100	173 ms	2304 KiB

Main

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/

#include <bits/stdc++.h>

#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, l, r) for(int i = l; i >= r; i--)
using ll = long long;
// #define int ll;

#define sz(a) (int)a.size()
#define fi first
#define se second
#define db(x) cerr << __LINE__ << " " << #x << " " << x << "\n"
#define pi pair<int, int>
#define vi vector<int>

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

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

using namespace std;

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(false); cin.tie(NULL); cout.tie(NULL);
	int t = 1; 
	while(t--){
		solve();
	}
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:40:18: warning: overflow in conversion from 'll' {aka 'long long int'} to 'int' changes value from '1000000000000000000' to '-1486618624' [-Woverflow]
   40 |    state[i].se = inf;
      |                  ^~~

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