# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
638726 | 2022-09-07T07:30:06 Z | jamezzz | Let's Win the Election (JOI22_ho_t3) | C++17 | 2500 ms | 4296 KB |
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define sf scanf #define pf printf typedef long long ll; typedef long double ld; typedef pair<int,int> ii; #define maxn 505 #define INF 1023456789 int n,k,a[maxn],b[maxn]; vector<ii> v; ld memo[maxn][maxn]; int main(){ sf("%d%d",&n,&k); for(int i=0;i<n;++i){ int x,y; sf("%d%d",&x,&y); if(y==-1)y=INF; v.push_back({x,y}); } sort(v.begin(),v.end(),[](ii &a,ii &b){ if(a.se==b.se)return a.fi>b.fi; else return a.se<b.se; }); int cnt=0; for(int i=0;i<n;++i){ tie(a[i],b[i])=v[i]; if(b[i]!=INF)++cnt; } ld ans=INF; for(int take=0;take<=cnt;++take){ for(int i=0;i<=n+1;++i){ for(int j=0;j<=n+1;++j){ memo[i][j]=INF; } } memo[0][0]=0; for(int pos=0;pos<n;++pos){ for(int ppl=take;ppl>=0;--ppl){ for(int vote=pos+1;vote>=0;--vote){ ld ans=memo[ppl][vote]; if(vote!=0)ans=min(ans,memo[ppl][vote-1]+(ld)a[pos]/(take+1)); if(vote!=0&&ppl!=0&&b[pos]!=INF){ ans=min(ans,memo[ppl-1][vote-1]+(ld)b[pos]/ppl); } memo[ppl][vote]=ans; } } } ans=min(ans,memo[take][k]); } pf("%.15Lf\n",ans); } /* 7 5 393 646 375 666 374 676 320 635 288 668 284 758 333 702 1258.500000000000000 */
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 280 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 4 ms | 4180 KB | Output is correct |
6 | Correct | 6 ms | 4268 KB | Output is correct |
7 | Correct | 4 ms | 4180 KB | Output is correct |
8 | Correct | 5 ms | 4180 KB | Output is correct |
9 | Correct | 5 ms | 4160 KB | Output is correct |
10 | Correct | 4 ms | 4180 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 280 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 4 ms | 4180 KB | Output is correct |
6 | Correct | 6 ms | 4268 KB | Output is correct |
7 | Correct | 4 ms | 4180 KB | Output is correct |
8 | Correct | 5 ms | 4180 KB | Output is correct |
9 | Correct | 5 ms | 4160 KB | Output is correct |
10 | Correct | 4 ms | 4180 KB | Output is correct |
11 | Correct | 0 ms | 212 KB | Output is correct |
12 | Execution timed out | 2572 ms | 4180 KB | Time limit exceeded |
13 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 0 ms | 340 KB | Output is correct |
6 | Correct | 0 ms | 340 KB | Output is correct |
7 | Correct | 0 ms | 340 KB | Output is correct |
8 | Correct | 0 ms | 340 KB | Output is correct |
9 | Correct | 0 ms | 340 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
13 | Correct | 1 ms | 340 KB | Output is correct |
14 | Correct | 1 ms | 340 KB | Output is correct |
15 | Correct | 1 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 0 ms | 340 KB | Output is correct |
6 | Correct | 0 ms | 340 KB | Output is correct |
7 | Correct | 0 ms | 340 KB | Output is correct |
8 | Correct | 0 ms | 340 KB | Output is correct |
9 | Correct | 0 ms | 340 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
13 | Correct | 1 ms | 340 KB | Output is correct |
14 | Correct | 1 ms | 340 KB | Output is correct |
15 | Correct | 1 ms | 340 KB | Output is correct |
16 | Correct | 1 ms | 340 KB | Output is correct |
17 | Correct | 1 ms | 340 KB | Output is correct |
18 | Correct | 1 ms | 340 KB | Output is correct |
19 | Correct | 1 ms | 340 KB | Output is correct |
20 | Correct | 1 ms | 340 KB | Output is correct |
21 | Correct | 1 ms | 308 KB | Output is correct |
22 | Correct | 1 ms | 308 KB | Output is correct |
23 | Correct | 1 ms | 340 KB | Output is correct |
24 | Correct | 1 ms | 340 KB | Output is correct |
25 | Correct | 2 ms | 340 KB | Output is correct |
26 | Correct | 1 ms | 340 KB | Output is correct |
27 | Correct | 1 ms | 340 KB | Output is correct |
28 | Correct | 1 ms | 340 KB | Output is correct |
29 | Correct | 1 ms | 308 KB | Output is correct |
30 | Correct | 1 ms | 340 KB | Output is correct |
31 | Correct | 1 ms | 340 KB | Output is correct |
32 | Correct | 1 ms | 340 KB | Output is correct |
33 | Correct | 1 ms | 340 KB | Output is correct |
34 | Correct | 1 ms | 340 KB | Output is correct |
35 | Correct | 1 ms | 340 KB | Output is correct |
36 | Correct | 1 ms | 316 KB | Output is correct |
37 | Correct | 1 ms | 340 KB | Output is correct |
38 | Correct | 1 ms | 340 KB | Output is correct |
39 | Correct | 1 ms | 340 KB | Output is correct |
40 | Correct | 1 ms | 340 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 340 KB | Output is correct |
2 | Correct | 1 ms | 212 KB | Output is correct |
3 | Correct | 1 ms | 340 KB | Output is correct |
4 | Correct | 1 ms | 340 KB | Output is correct |
5 | Correct | 0 ms | 340 KB | Output is correct |
6 | Correct | 0 ms | 340 KB | Output is correct |
7 | Correct | 0 ms | 340 KB | Output is correct |
8 | Correct | 0 ms | 340 KB | Output is correct |
9 | Correct | 0 ms | 340 KB | Output is correct |
10 | Correct | 1 ms | 340 KB | Output is correct |
11 | Correct | 1 ms | 340 KB | Output is correct |
12 | Correct | 1 ms | 340 KB | Output is correct |
13 | Correct | 1 ms | 340 KB | Output is correct |
14 | Correct | 1 ms | 340 KB | Output is correct |
15 | Correct | 1 ms | 340 KB | Output is correct |
16 | Correct | 1 ms | 340 KB | Output is correct |
17 | Correct | 1 ms | 340 KB | Output is correct |
18 | Correct | 1 ms | 340 KB | Output is correct |
19 | Correct | 1 ms | 340 KB | Output is correct |
20 | Correct | 1 ms | 340 KB | Output is correct |
21 | Correct | 1 ms | 308 KB | Output is correct |
22 | Correct | 1 ms | 308 KB | Output is correct |
23 | Correct | 1 ms | 340 KB | Output is correct |
24 | Correct | 1 ms | 340 KB | Output is correct |
25 | Correct | 2 ms | 340 KB | Output is correct |
26 | Correct | 1 ms | 340 KB | Output is correct |
27 | Correct | 1 ms | 340 KB | Output is correct |
28 | Correct | 1 ms | 340 KB | Output is correct |
29 | Correct | 1 ms | 308 KB | Output is correct |
30 | Correct | 1 ms | 340 KB | Output is correct |
31 | Correct | 1 ms | 340 KB | Output is correct |
32 | Correct | 1 ms | 340 KB | Output is correct |
33 | Correct | 1 ms | 340 KB | Output is correct |
34 | Correct | 1 ms | 340 KB | Output is correct |
35 | Correct | 1 ms | 340 KB | Output is correct |
36 | Correct | 1 ms | 316 KB | Output is correct |
37 | Correct | 1 ms | 340 KB | Output is correct |
38 | Correct | 1 ms | 340 KB | Output is correct |
39 | Correct | 1 ms | 340 KB | Output is correct |
40 | Correct | 1 ms | 340 KB | Output is correct |
41 | Correct | 204 ms | 872 KB | Output is correct |
42 | Correct | 124 ms | 876 KB | Output is correct |
43 | Correct | 196 ms | 872 KB | Output is correct |
44 | Correct | 115 ms | 852 KB | Output is correct |
45 | Correct | 204 ms | 880 KB | Output is correct |
46 | Correct | 146 ms | 872 KB | Output is correct |
47 | Correct | 197 ms | 972 KB | Output is correct |
48 | Correct | 104 ms | 888 KB | Output is correct |
49 | Correct | 225 ms | 828 KB | Output is correct |
50 | Correct | 108 ms | 876 KB | Output is correct |
51 | Correct | 186 ms | 876 KB | Output is correct |
52 | Correct | 120 ms | 872 KB | Output is correct |
53 | Correct | 240 ms | 876 KB | Output is correct |
54 | Correct | 193 ms | 872 KB | Output is correct |
55 | Correct | 190 ms | 880 KB | Output is correct |
56 | Correct | 237 ms | 876 KB | Output is correct |
57 | Correct | 196 ms | 876 KB | Output is correct |
58 | Correct | 188 ms | 888 KB | Output is correct |
59 | Correct | 198 ms | 852 KB | Output is correct |
60 | Correct | 193 ms | 852 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 2567 ms | 4296 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | Output is correct |
2 | Correct | 0 ms | 212 KB | Output is correct |
3 | Correct | 0 ms | 280 KB | Output is correct |
4 | Correct | 0 ms | 212 KB | Output is correct |
5 | Correct | 4 ms | 4180 KB | Output is correct |
6 | Correct | 6 ms | 4268 KB | Output is correct |
7 | Correct | 4 ms | 4180 KB | Output is correct |
8 | Correct | 5 ms | 4180 KB | Output is correct |
9 | Correct | 5 ms | 4160 KB | Output is correct |
10 | Correct | 4 ms | 4180 KB | Output is correct |
11 | Correct | 0 ms | 212 KB | Output is correct |
12 | Execution timed out | 2572 ms | 4180 KB | Time limit exceeded |
13 | Halted | 0 ms | 0 KB | - |