Submission #936889

#	Time	Username	Problem	Language	Result	Execution time	Memory
936889		william950615	Let's Win the Election (JOI22_ho_t3)	C++14	56 / 100	2531 ms	3416 KiB

Main

#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define mkp make_pair
#define PH push
#define PB push_back
#define REP(i,N) for( int i = 0; i < (N); ++i )
#define FOR(i,a,b) for( int i = (a); i <= (b); ++i )
#define ALL(x) begin(x), end(x)
#define MEM(x) memset(x, 0, sizeof(x))

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<typename T>
using V=vector<T>;
#define double float

void solve() {
	int N, K; cin >> N >> K;
	V<pll> vc(N+1);
	const ll INF = 1e18;
	FOR(i,1,N) cin >> vc[i].F >> vc[i].S;
	for( auto &i : vc ) if( i.S == -1 ) i.S = INF;

	sort( vc.begin()+1, vc.end(), [&]( auto&a, auto&b) {
			return a.S < b.S;
		});
	
	V<V<V<double>>> dp( 2, V<V<double>>( K+1, V<double>(K+1, 0) ));
	//double dp[ N+1 ][ K+1 ][ K+1 ];

	auto init = [&]() {
		for( auto &i : dp ) for( auto &j : i ) for( auto &k : j )
			k = INF;
		dp[ 0 ][ 1 ][ 0 ] = 0;
		dp[ 1 ][ 1 ][ 0 ] = 0;
	};

	auto do_dp = [&](int p) {
		double ans=INF;
		init();
		for( int i = 1; i <= N; ++i ) {
			for( int j = 1; j <= K; ++j ) {
				for( int k = 1; k <= K; ++k ) {
					dp[ i&1 ][ j ][ k ] = min({
						( j == 1 ? INF : dp[~i&1][j-1][k-1]+(1.0f*vc[i].S/(j-1)) ), 
						dp[~i&1][j][k-1] + (1.0f*vc[i].F/p),
						dp[~i&1][j][k]
					});
				}
			}
		}
		//fprintf(stderr, "ans:(%.16lf), p(%d)\n", ans, p );
		ans = min( dp[N&1][p][K], ans );
		return ans;
	};

	int l = 1, r = K;
	double ans = INF;
	while( r-l > 4 ) {
		int l1 = (l+l+r)/3, l2 = (l+r+r)/3;
		double ans1 = do_dp(l1);
		double ans2 = do_dp(l2);
		ans = min( {ans,ans1,ans2} );
		if( ans1 > ans2 ) 
			l=l1;
		else
			r=l2;
	}
	for( int i = l; i<=r; ++i ) 
		ans = min( ans, do_dp(i));

	cout << fixed << setprecision(10);
	cout << ans << '\n';
}

int main() {
	int T = 1;
#ifdef LOCAL
	freopen( "input.txt", "r", stdin);
	freopen( "output.txt", "w", stdout );
	cin >> T;
#else
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#endif
	while(T--) solve();

}

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