# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
748643 | 2023-05-26T16:51:26 Z | inventiontime | Boarding Passes (BOI22_passes) | C++17 | 2000 ms | 3524 KB |
#include <bits/stdc++.h> using namespace std; #define int ll #define endl '\n' //comment for interactive #define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define pb push_back #define re resize #define ff first #define ss second #define all(x) (x).begin(), (x).end() #define all1(x) (x).begin()+1, (x).end() #define loop(i, n) for(int i = 0; i < n; i++) #define loop1(i, n) for(int i = 1; i <= n; i++) #define print(x) cout << #x << ": " << x << endl << flush typedef long long ll; typedef vector<int> vi; typedef vector<double> vd; typedef array<int, 2> ii; typedef array<int, 3> ti; typedef vector<ii> vii; typedef vector<ti> vti; typedef vector<vi> vvi; typedef priority_queue<int> pq; template<class T> bool ckmin(T&a, T b) { bool B = a > b; a = min(a, b); return B; } template<class T> bool ckmax(T&a, T b) { bool B = a < b; a = max(a, b); return B; } const int inf = 1e17; double cst(int x) { return (double) x * (x-1) / 4; } void solve() { string s; cin >> s; int n = s.size(); vvi pos(26); loop(i, n) pos[s[i]-'A'].pb(i); vi ch; loop(i, 26) if(!pos[i].empty()) ch.pb(i); int g = ch.size(); vi id(26); loop(i, g) id[ch[i]] = i; if(g == 1) { cout << setprecision(16) << cst(n/2) + cst((n+1)/2) << endl; return; } vd dp(1 << g, inf); dp[0] = 0; loop(pre, 1 << g) { bitset<15> prev(pre); loop(ch, g) if(!prev[ch]) { int nxt = pre + (1 << ch); double cost = inf; vd left(n); vd right(n+1); int cnt = 0, oth = 0; for(int i = 0; i < n; i++) { if(i) left[i] = left[i-1]; if(prev[id[s[i]-'A']]) oth++; else if(id[s[i]-'A'] == ch) { cnt++; left[i] += oth; left[i] += cst(cnt); left[i] -= cst(cnt-1); } } cnt = 0, oth = 0; for(int i = n-1; i >= 0; i--) { right[i] = right[i+1]; if(prev[id[s[i]-'A']]) oth++; else if(id[s[i]-'A'] == ch) { cnt++; right[i] += oth; right[i] += cst(cnt); right[i] -= cst(cnt-1); } } loop(i, n) ckmin(cost, left[i] + right[i+1]); ckmin(dp[nxt], dp[pre] + cost); } } cout << setprecision(16) << dp[(1 << g) - 1] << endl; } signed main() { fast_io; int t = 1; //cin >> t; while(t--) solve(); return 0; }
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
2 | Correct | 1 ms | 212 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
3 | Correct | 0 ms | 212 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
4 | Correct | 0 ms | 212 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
5 | Correct | 1 ms | 212 KB | found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 | Correct | 2 ms | 1680 KB | found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000' |
7 | Correct | 2 ms | 1680 KB | found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000' |
8 | Correct | 2 ms | 1680 KB | found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000' |
9 | Correct | 2 ms | 1680 KB | found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000' |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 | Correct | 0 ms | 212 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 | Correct | 1 ms | 212 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
4 | Correct | 1 ms | 276 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
5 | Correct | 1 ms | 212 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
6 | Correct | 1 ms | 212 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
7 | Correct | 1 ms | 212 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
8 | Correct | 1 ms | 212 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
9 | Correct | 1 ms | 212 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
10 | Correct | 1 ms | 212 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
11 | Correct | 1 ms | 212 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
12 | Correct | 1 ms | 212 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
13 | Correct | 0 ms | 212 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
14 | Correct | 1 ms | 212 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
15 | Correct | 1 ms | 212 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
16 | Correct | 1 ms | 212 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
17 | Correct | 1 ms | 212 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
2 | Correct | 0 ms | 212 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
3 | Correct | 1 ms | 212 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
4 | Correct | 1 ms | 276 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
5 | Correct | 1 ms | 212 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
6 | Correct | 1 ms | 212 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
7 | Correct | 1 ms | 212 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
8 | Correct | 1 ms | 212 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
9 | Correct | 1 ms | 212 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
10 | Correct | 1 ms | 212 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
11 | Correct | 1 ms | 212 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
12 | Correct | 1 ms | 212 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
13 | Correct | 0 ms | 212 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
14 | Correct | 1 ms | 212 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
15 | Correct | 1 ms | 212 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
16 | Correct | 1 ms | 212 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
17 | Correct | 1 ms | 212 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
18 | Correct | 1 ms | 212 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
19 | Correct | 0 ms | 212 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
20 | Correct | 1 ms | 212 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
21 | Correct | 1 ms | 212 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
22 | Correct | 1 ms | 212 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
23 | Correct | 0 ms | 212 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
24 | Correct | 1 ms | 212 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
25 | Correct | 0 ms | 212 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
26 | Correct | 1 ms | 212 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
27 | Correct | 1 ms | 212 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
28 | Correct | 0 ms | 212 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
29 | Correct | 1 ms | 212 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
30 | Correct | 1 ms | 212 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
31 | Correct | 1 ms | 212 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
32 | Correct | 1 ms | 212 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
33 | Correct | 1 ms | 212 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
34 | Correct | 1 ms | 212 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
35 | Correct | 1 ms | 468 KB | found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000' |
36 | Correct | 0 ms | 468 KB | found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000' |
37 | Correct | 888 ms | 820 KB | found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000' |
38 | Correct | 411 ms | 688 KB | found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000' |
39 | Correct | 360 ms | 636 KB | found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000' |
40 | Correct | 415 ms | 708 KB | found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000' |
41 | Correct | 413 ms | 688 KB | found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000' |
42 | Correct | 404 ms | 820 KB | found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000' |
43 | Correct | 412 ms | 728 KB | found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000' |
44 | Correct | 399 ms | 716 KB | found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000' |
45 | Correct | 403 ms | 644 KB | found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000' |
46 | Correct | 399 ms | 640 KB | found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000' |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 212 KB | found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
2 | Correct | 1 ms | 212 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
3 | Correct | 0 ms | 212 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
4 | Correct | 0 ms | 212 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
5 | Correct | 1 ms | 212 KB | found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
6 | Correct | 2 ms | 1680 KB | found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000' |
7 | Correct | 2 ms | 1680 KB | found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000' |
8 | Correct | 2 ms | 1680 KB | found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000' |
9 | Correct | 2 ms | 1680 KB | found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000' |
10 | Correct | 0 ms | 212 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
11 | Correct | 0 ms | 212 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
12 | Correct | 1 ms | 212 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
13 | Correct | 1 ms | 276 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
14 | Correct | 1 ms | 212 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
15 | Correct | 1 ms | 212 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
16 | Correct | 1 ms | 212 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
17 | Correct | 1 ms | 212 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
18 | Correct | 1 ms | 212 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
19 | Correct | 1 ms | 212 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
20 | Correct | 1 ms | 212 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
21 | Correct | 1 ms | 212 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
22 | Correct | 0 ms | 212 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
23 | Correct | 1 ms | 212 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
24 | Correct | 1 ms | 212 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
25 | Correct | 1 ms | 212 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
26 | Correct | 1 ms | 212 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
27 | Correct | 1 ms | 212 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
28 | Correct | 0 ms | 212 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
29 | Correct | 1 ms | 212 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
30 | Correct | 1 ms | 212 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
31 | Correct | 1 ms | 212 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
32 | Correct | 0 ms | 212 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
33 | Correct | 1 ms | 212 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
34 | Correct | 0 ms | 212 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
35 | Correct | 1 ms | 212 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
36 | Correct | 1 ms | 212 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
37 | Correct | 0 ms | 212 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
38 | Correct | 1 ms | 212 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
39 | Correct | 1 ms | 212 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
40 | Correct | 1 ms | 212 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
41 | Correct | 1 ms | 212 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
42 | Correct | 1 ms | 212 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
43 | Correct | 1 ms | 212 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
44 | Correct | 1 ms | 468 KB | found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000' |
45 | Correct | 0 ms | 468 KB | found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000' |
46 | Correct | 888 ms | 820 KB | found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000' |
47 | Correct | 411 ms | 688 KB | found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000' |
48 | Correct | 360 ms | 636 KB | found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000' |
49 | Correct | 415 ms | 708 KB | found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000' |
50 | Correct | 413 ms | 688 KB | found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000' |
51 | Correct | 404 ms | 820 KB | found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000' |
52 | Correct | 412 ms | 728 KB | found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000' |
53 | Correct | 399 ms | 716 KB | found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000' |
54 | Correct | 403 ms | 644 KB | found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000' |
55 | Correct | 399 ms | 640 KB | found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000' |
56 | Correct | 1 ms | 212 KB | found '7.5000000000', expected '7.5000000000', error '0.0000000000' |
57 | Correct | 79 ms | 572 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
58 | Correct | 1 ms | 320 KB | found '100800.5000000000', expected '100800.5000000000', error '0.0000000000' |
59 | Correct | 0 ms | 320 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
60 | Correct | 1 ms | 320 KB | found '0.0000000000', expected '0.0000000000', error '-0.0000000000' |
61 | Correct | 1 ms | 212 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
62 | Correct | 1 ms | 212 KB | found '124002.0000000000', expected '124002.0000000000', error '0.0000000000' |
63 | Correct | 2 ms | 1680 KB | found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000' |
64 | Correct | 2 ms | 1800 KB | found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000' |
65 | Correct | 2 ms | 1804 KB | found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000' |
66 | Correct | 2 ms | 1804 KB | found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000' |
67 | Correct | 0 ms | 212 KB | found '1.0000000000', expected '1.0000000000', error '0.0000000000' |
68 | Correct | 1 ms | 212 KB | found '1225.0000000000', expected '1225.0000000000', error '0.0000000000' |
69 | Correct | 1 ms | 320 KB | found '1023.0000000000', expected '1023.0000000000', error '0.0000000000' |
70 | Correct | 1 ms | 212 KB | found '294.0000000000', expected '294.0000000000', error '0.0000000000' |
71 | Correct | 1 ms | 212 KB | found '1087.0000000000', expected '1087.0000000000', error '0.0000000000' |
72 | Correct | 1 ms | 212 KB | found '1.5000000000', expected '1.5000000000', error '0.0000000000' |
73 | Correct | 1 ms | 212 KB | found '703.0000000000', expected '703.0000000000', error '0.0000000000' |
74 | Correct | 1 ms | 212 KB | found '55.5000000000', expected '55.5000000000', error '0.0000000000' |
75 | Correct | 1 ms | 212 KB | found '56.0000000000', expected '56.0000000000', error '0.0000000000' |
76 | Correct | 1 ms | 212 KB | found '45.0000000000', expected '45.0000000000', error '0.0000000000' |
77 | Correct | 1 ms | 212 KB | found '66.5000000000', expected '66.5000000000', error '0.0000000000' |
78 | Correct | 1 ms | 212 KB | found '67.0000000000', expected '67.0000000000', error '0.0000000000' |
79 | Correct | 1 ms | 212 KB | found '66.0000000000', expected '66.0000000000', error '0.0000000000' |
80 | Correct | 1 ms | 212 KB | found '47.0000000000', expected '47.0000000000', error '0.0000000000' |
81 | Correct | 1 ms | 320 KB | found '50.0000000000', expected '50.0000000000', error '0.0000000000' |
82 | Correct | 1 ms | 212 KB | found '49.0000000000', expected '49.0000000000', error '0.0000000000' |
83 | Correct | 1 ms | 212 KB | found '57.0000000000', expected '57.0000000000', error '0.0000000000' |
84 | Correct | 1 ms | 468 KB | found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000' |
85 | Correct | 1 ms | 464 KB | found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000' |
86 | Correct | 870 ms | 796 KB | found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000' |
87 | Correct | 408 ms | 640 KB | found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000' |
88 | Correct | 363 ms | 620 KB | found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000' |
89 | Correct | 419 ms | 792 KB | found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000' |
90 | Correct | 408 ms | 644 KB | found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000' |
91 | Correct | 406 ms | 652 KB | found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000' |
92 | Correct | 409 ms | 644 KB | found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000' |
93 | Correct | 409 ms | 708 KB | found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000' |
94 | Correct | 405 ms | 644 KB | found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000' |
95 | Correct | 406 ms | 640 KB | found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000' |
96 | Execution timed out | 2078 ms | 3524 KB | Time limit exceeded |
97 | Halted | 0 ms | 0 KB | - |