제출 #674414

#제출 시각아이디문제언어결과실행 시간메모리
674414abysmalLet's Win the Election (JOI22_ho_t3)C++14
10 / 100
2 ms340 KiB
#include<iostream> #include<stdio.h> #include<stdint.h> #include<vector> #include<algorithm> #include<utility> #include<set> #include<map> #include<queue> #include<stack> #include<iomanip> #include<string> using namespace std; const int64_t INF = (int64_t) 1e18; const int64_t mINF = (int64_t) 1e9 + 7; const int64_t MOD = 998244353; const int nbit = 11; const int ndig = 10; const int nchar = 26; const int p1 = 31; const int p2 = 53; const int D = 4; int dr[D] = {0, 1, 0, -1}; int dc[D] = {1, 0, -1, 0}; // 0 right // 1 down // 2 left // 3 up struct Thing { int a; int b; Thing(int a_, int b_) : a(a_), b(b_) {} bool operator < (const Thing& o) const { if(a != o.a) return a < o.a; return b < o.b; } }; struct Solution { int n; int k; map<Thing, int> a; map<Thing, int> b; Solution() {} void solve() { cin >> n >> k; for(int i = 0; i < n; i++) { int x; int y; cin >> x >> y; a[Thing(x, y)]++; if(y != -1) b[Thing(y, x)]++; } double ans = mINF; double sum = 0; for(int i = 1; i <= k; i++) { double x = 0; int cnt = k - i + 1; for(map<Thing, int>::iterator it = a.begin(); it != a.end(); it++) { if(cnt == 0) break; Thing t = it->first; int c = it->second; for(int j = 0; j < c; j++) { if(cnt == 0) break; x += ((double) t.a) / ((double) i); cnt--; } } ans = min(ans, sum + x); if(b.empty()) break; Thing tmp = b.begin()->first; Thing r = Thing(tmp.b, tmp.a); a[r]--; b[tmp]--; if(b[tmp] == 0) b.erase(tmp); if(a[r] == 0) a.erase(r); sum += ((double) tmp.a) / ((double) i); } cout << setprecision(9) << ans << "\n"; } int modsub(int t1, int t2) { int res = t1 - t2; if(res < 0) res += MOD; return res; } int modadd(int t1, int t2) { int res = t1 + t2; if(res >= MOD) res -= MOD; return res; } int modmul(int t1, int t2) { int64_t res = 1LL * t1 * t2; return (res % MOD); } bool BIT(int& mask, int& j) { return (mask & MASK(j)); } int MASK(int j) { return (1 << j); } }; void __startup() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); } int main() { __startup(); int t = 1; // cin >> t; for(int i = 1; i <= t; i++) { Solution().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...