Submission #936908

#TimeUsernameProblemLanguageResultExecution timeMemory
936908william950615Let's Win the Election (JOI22_ho_t3)C++14
72 / 100
2556 ms1624 KiB
#pragma GCC optimize("O3,unroll-loops") //#pragma GCC target("avx,popcnt,sse4,abm") #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, mkp(0,0)); const ll INF = 1e18; FOR(i,1,N) cin >> vc[i].F >> vc[i].S; int cnt = 0; for( auto &i : vc ) if( i.S == -1 ) i.S = INF,++cnt; cnt = N-cnt+1; cnt = min( K, cnt ); 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) )); V<V<double>> dp(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 ) */ j = INF; dp[ 1 ][ 0 ] = 0; }; auto do_dp = [&](int p) { double ans=INF; init(); for( int i = 1; i <= N; ++i ) { double val = 1.0f*vc[i].F/p; for( int j = p; j>=1; --j ) { double val2 = ( j ==1 ? INF :1.0f*vc[i].S/(j-1) ); for( int k = K; k >=1; --k ) { dp[ j ][ k ] = min({ ( j == 1 ? INF : dp[j-1][k-1]+val2 ), dp[j][k-1] + val, dp[j][k] }); } } } //fprintf(stderr, "ans:(%.16lf), p(%d)\n", ans, p ); ans = min( dp[p][K], ans ); return ans; }; int l = 1, r = cnt; 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(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...