oj.uz

Submission #1098955

# Submission time Handle Problem Language Result Execution time Memory
1098955 2024-10-10T11:19:14 Z not_amir Boarding Passes (BOI22_passes) C++14
60 / 100
 1253 ms 1404 KB 
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")

typedef long double ld;
typedef long long ll;

constexpr int N = 10;

int h[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string S;
    cin >> S;
    int n = S.size();
    for(char c : S) {
        h[c - 'A'] = 1;
    }
    for(int i = 0, it = 0; i < N; i++)
        if(h[i])
            h[i] = it++;
    ll res = n * n;
    vector<ll> dp(1 << N, ll(n) * ll(n));
    dp[0] = 0;
    for(int i = 1; i < 1 << N; i++) {
        for(int j = 0; j < N; j++) {
            if(i & (1 << j)) {
                ll ans = dp[i ^ (1 << j)];
                vector<ll> rem(n);
                for(int k = 0, it = 0, sum = 0; k < n; k++) {
                    if(h[S[k] - 'A'] == j) {
                        rem[k] = it++ + 2 * sum;
                        ans += rem[k];
                    }
                    else if(i & (1 << h[S[k] - 'A']))
                        sum++;
                }
                ll mini = ans;
                for(int k = n - 1, it = 0, sum = 0; k>= 0; k--) {
                    if(h[S[k] - 'A'] == j) {
                        ans -= rem[k];
                        ans += it++ + 2 * sum;
                    }
                    else if(i & (1 << h[S[k] - 'A']))
                        sum++;
                    mini = min(mini, ans);
                }
                dp[i] = min(dp[i], mini);
            }
        }
    }
    cout << fixed << setprecision(6) << ld(dp[(1 << N) - 1]) / 2.0;
}

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:25:8: warning: unused variable 'res' [-Wunused-variable]
   25 |     ll res = n * n;
      |        ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 348 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 13 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 955 ms 1268 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 1155 ms 1404 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 1253 ms 1372 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 1228 ms 1372 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 2 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 2 ms 460 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 2 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 2 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 0 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 344 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 344 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 2 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 2 ms 460 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 2 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 2 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 0 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 344 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 344 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 2 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 2 ms 344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 2 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 121 ms 348 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 119 ms 344 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 222 ms 592 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 119 ms 348 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 119 ms 348 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 124 ms 348 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 133 ms 348 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 126 ms 344 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 127 ms 544 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 123 ms 348 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 129 ms 556 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 124 ms 536 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 348 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 13 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 955 ms 1268 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 1155 ms 1404 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 1253 ms 1372 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 1228 ms 1372 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 2 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 2 ms 460 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 2 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 2 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 0 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 344 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 344 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 2 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 2 ms 344 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 2 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 344 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 121 ms 348 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 119 ms 344 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 222 ms 592 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 119 ms 348 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 119 ms 348 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 124 ms 348 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 133 ms 348 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 126 ms 344 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 127 ms 544 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 123 ms 348 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 129 ms 556 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 124 ms 536 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Incorrect 1 ms 348 KB 1st numbers differ - expected: '7.5000000000', found: '13.5000000000', error = '0.8000000000'
57 Halted 0 ms 0 KB -