Submission #936890

#TimeUsernameProblemLanguageResultExecution timeMemory
936890william950615Let's Win the Election (JOI22_ho_t3)C++14
Compilation error
0 ms0 KiB
#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) )); 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 ) */ k = INF; dp[ 1 ][ 0 ] = 0; }; auto do_dp = [&](int p) { double ans=INF; init(); for( int i = 1; i <= N; ++i ) { for( int j = K; j>=0; --j ) { for( int k = K; k >=0; --k ) { dp[ j ][ k ] = min( ( j == 1 ? INF : dp[j-1][k-1]+(1.0f*vc[i].S/(j-1)) ), dp[j][k-1] + (1.0f*vc[i].F/p), ); } } } //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(); }

Compilation message (stderr)

Main.cpp: In lambda function:
Main.cpp:39:4: error: 'k' was not declared in this scope
   39 |    k = INF;
      |    ^
Main.cpp:38:34: warning: unused variable 'j' [-Wunused-variable]
   38 |   for( auto &i : dp ) for( auto &j : i )/* for( auto &k : j ) */
      |                                  ^
Main.cpp: In lambda function:
Main.cpp:52:6: error: expected primary-expression before ')' token
   52 |      );
      |      ^
Main.cpp:57:24: error: invalid types '__gnu_cxx::__alloc_traits<std::allocator<float>, float>::value_type {aka float}[int]' for array subscript
   57 |   ans = min( dp[N&1][p][K], ans );
      |                        ^