# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
598811 | 2022-07-19T06:02:26 Z | denniskim | Let's Win the Election (JOI22_ho_t3) | C++17 | 925 ms | 1048576 KB |
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef __int128 lll; typedef long double ld; #define MAX 9223372036854775807LL #define MIN -9223372036854775807LL #define INF 0x3f3f3f3f3f3f3f3f #define fi first #define se second ll n; ll k; pair<ll, ll> a[510]; ld ans = INF; ll chk[510]; ld dp[510][510][510]; int main(void) { scanf("%lld", &n); scanf("%lld", &k); for(ll i = 1 ; i <= n ; i++) { scanf("%lld %lld", &a[i].se, &a[i].fi); if(a[i].fi == -1) a[i].fi = 1000000000; } sort(a + 1, a + 1 + n); for(ll i = 0 ; i <= k ; i++) { for(ll j = 0 ; j <= n ; j++) { for(ll o = 0 ; o <= k ; o++) { for(ll oo = 0 ; oo <= k ; oo++) dp[j][o][oo] = 10000000; } } dp[0][0][0] = 0; for(ll j = 1 ; j <= n ; j++) { for(ll o = 0 ; o <= k ; o++) { for(ll oo = 0 ; oo <= k ; oo++) { dp[j][o][oo] = min(dp[j][o][oo], dp[j - 1][o][oo]); if(o >= 1) dp[j][o][oo] = min(dp[j][o][oo], dp[j - 1][o - 1][oo] + (ld)a[j].se / (ld)(i + 1)); if(o >= 1 && oo >= 1) dp[j][o][oo] = min(dp[j][o][oo], dp[j - 1][o - 1][oo - 1] + (ld)a[j].fi / (ld)oo); } } } printf("%.10Lf\n", dp[n][k][i]); ans = min(ans, dp[n][k][i]); } printf("%.10Lf", ans); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 212 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 212 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 340 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 340 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 340 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 925 ms | 1048576 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 0 ms | 212 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |