Submission #928603

#TimeUsernameProblemLanguageResultExecution timeMemory
928603jcelinLet's Win the Election (JOI22_ho_t3)C++14
100 / 100
884 ms7000 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> ii; typedef pair<ll,ll> pll; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<ll> vll; typedef vector<pll> vpll; #define PB push_back #define PF push_front #define PPB pop_back #define PPF pop_front #define X first #define Y second #define MP make_pair #define all(x) (x).begin(), (x).end() const int mod = 1e9 + 7; //998244353; const int inf = 1e9 + 7; const ll INF = 1e18 + 7; const int logo = 20; const int MAXN = 700; const int off = 1 << logo; const int trsz = off << 1; const int dx[] = {1, -1, 0, 0}; const int dy[] = {0, 0, -1, 1}; typedef long double ld; typedef pair<ld, ld> pld; const ld eps = 1e-15; vector<pld> arr; ld dp[MAXN][MAXN]; bool cmp(pld &a, pld &b){ if(abs(a.Y - b.Y) > eps) return a.Y < b.Y; return a.X < b.X; } void solve(){ int n, k; cin >> n >> k; arr.resize(n); for(auto &x : arr){ cin >> x.X >> x.Y; if(x.Y == -1) x.Y = (ld)inf; } sort(all(arr), cmp); //L - broj pomocnika //R - broj obicnih ld ans = inf; for(int L=0; L<=k; L++){ for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) dp[i][j] = (ld)inf; dp[0][0] = 0; for(int i=1; i<=n; i++){ pld cur = arr[i - 1]; for(int R=0; R<=min(i, k - L); R++){ int clef = i - R; if(R) dp[i][R] = min(dp[i][R], dp[i - 1][R - 1] + (ld)cur.X / (ld)(L + 1)); if(clef <= L) dp[i][R] = min(dp[i][R], dp[i - 1][R] + (ld)cur.Y / (ld)clef); else dp[i][R] = min(dp[i][R], dp[i - 1][R]); } } ans = min(ans, dp[n][k - L]); } cout << fixed << setprecision(10) << ans << "\n"; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int tt = 1; //cin >> tt; while(tt--) solve(); return 0; }
#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...