Submission #750872

#TimeUsernameProblemLanguageResultExecution timeMemory
750872KihihihiLet's Win the Election (JOI22_ho_t3)C++17
100 / 100
356 ms4952 KiB
#include <iostream> #include <iomanip> #include <algorithm> #include <numeric> #include <cmath> #include <cassert> #include <ctime> #include <chrono> #include <cstdio> #include <random> #include <vector> #include <string> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <deque> #include <queue> #include <bitset> #include <list> #include <fstream> #include <functional> #include <complex> using namespace std; mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count()); short skip_cin = 0; const long long INF = 1e9, MOD = 1e9 + 7, MOD2 = 998244353, LOG = 19; const long double EPS = 1e-9, PI = acos(-1); void solve() { long long n, k; vector<pair<double, double>> v; cin >> n >> k; v.resize(n); for (long long i = 0; i < n; i++) { cin >> v[i].first >> v[i].second; if (v[i].second == -1) { v[i].second = INF; } } sort(v.begin(), v.end(), [](pair<double, double>& x, pair<double, double>& y) { if (x.second == y.second) { return x.first > y.first; } return x.second < y.second; } ); vector<vector<double>> srta(n + 1); for (long long i = n - 1; i > -1; i--) { srta[i] = srta[i + 1]; srta[i].push_back(v[i].first); sort(srta[i].begin(), srta[i].end()); } double ans = INF; for (long long fr = 0; fr < k + 1; fr++) { vector<vector<double>> dp(n + 1, vector<double>(fr + 1, INF)); dp[0][0] = 0; for (long long i = 0; i < n; i++) { for (long long j = 0; j < fr + 1; j++) { if (j > 0) { dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - 1] + v[i].second / (double)(j)); } dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + v[i].first / (double)(fr + 1)); } } for (long long i = fr; i < n + 1; i++) { if (srta[i].size() < k - i) { break; } double add = 0; for (long long j = 0; j < k - i; j++) { add += srta[i][j]; } add /= (fr + 1); ans = min(ans, dp[i][fr] + add); } } cout << fixed << setprecision(20) << ans << "\n"; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); srand(time(NULL)); int tst = 1; //cin >> tst; while (tst--) { solve(); } return 0; } /* <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 ⠀⠀⠀⠀⠀⠀⠀⠀⠀⣠⠤⠖⠚⢉⣩⣭⡭⠛⠓⠲⠦⣄⡀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⢀⡴⠋⠁⠀⠀⠊⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠳⢦⡀⠀⠀⠀⠀ ⠀⠀⠀⠀⢀⡴⠃⢀⡴⢳⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⣆⠀⠀⠀ ⠀⠀⠀⠀⡾⠁⣠⠋⠀⠈⢧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢧⠀⠀ ⠀⠀⠀⣸⠁⢰⠃⠀⠀⠀⠈⢣⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣇⠀ ⠀⠀⠀⡇⠀⡾⡀⠀⠀⠀⠀⣀⣹⣆⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢹⠀ ⠀⠀⢸⠃⢀⣇⡈⠀⠀⠀⠀⠀⠀⢀⡑⢄⡀⢀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇ ⠀⠀⢸⠀⢻⡟⡻⢶⡆⠀⠀⠀⠀⡼⠟⡳⢿⣦⡑⢄⠀⠀⠀⠀⠀⠀⠀⠀⢸⡇ ⠀⠀⣸⠀⢸⠃⡇⢀⠇⠀⠀⠀⠀⠀⡼⠀⠀⠈⣿⡗⠂⠀⠀⠀⠀⠀⠀⠀⢸⠁ ⠀⠀⡏⠀⣼⠀⢳⠊⠀⠀⠀⠀⠀⠀⠱⣀⣀⠔⣸⠁⠀⠀⠀⠀⠀⠀⠀⢠⡟⠀ ⠀⠀⡇⢀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠠⠀⡇⠀⠀⠀⠀⠀⠀⠀⠀⢸⠃⠀ ⠀⢸⠃⠘⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠁⠀⠀⢀⠀⠀⠀⠀⠀⣾⠀⠀ ⠀⣸⠀⠀⠹⡄⠀⠀⠈⠁⠀⠀⠀⠀⠀⠀⠀⡞⠀⠀⠀⠸⠀⠀⠀⠀⠀⡇⠀⠀ ⠀⡏⠀⠀⠀⠙⣆⠀⠀⠀⠀⠀⠀⠀⢀⣠⢶⡇⠀⠀⢰⡀⠀⠀⠀⠀⠀⡇⠀⠀ ⢰⠇⡄⠀⠀⠀⡿⢣⣀⣀⣀⡤⠴⡞⠉⠀⢸⠀⠀⠀⣿⡇⠀⠀⠀⠀⠀⣧⠀⠀ ⣸⠀⡇⠀⠀⠀⠀⠀⠀⠉⠀⠀⠀⢹⠀⠀⢸⠀⠀⢀⣿⠇⠀⠀⠀⠁⠀⢸⠀⠀ ⣿⠀⡇⠀⠀⠀⠀⠀⢀⡤⠤⠶⠶⠾⠤⠄⢸⠀⡀⠸⣿⣀⠀⠀⠀⠀⠀⠈⣇⠀ ⡇⠀⡇⠀⠀⡀⠀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠸⡌⣵⡀⢳⡇⠀⠀⠀⠀⠀⠀⢹⡀ ⡇⠀⠇⠀⠀⡇⡸⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠮⢧⣀⣻⢂⠀⠀⠀⠀⠀⠀⢧ ⣇⠀⢠⠀⠀⢳⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⡎⣆⠀⠀⠀⠀⠀⠘ ⢻⠀⠈⠰⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⠘⢮⣧⡀⠀⠀⠀⠀ ⠸⡆⠀⠀⠇⣾⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠆⠀⠀⠀⠀⠀⠀⠀⠙⠳⣄⡀⢢⡀ <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 <3 */

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:83:32: warning: comparison of integer expressions of different signedness: 'std::vector<double>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   83 |             if (srta[i].size() < k - i)
      |                 ~~~~~~~~~~~~~~~^~~~~~~
#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...