oj.uz

Submission #1098954

# Submission time Handle Problem Language Result Execution time Memory
1098954 2024-10-10T11:17:54 Z not_amir Boarding Passes (BOI22_passes) C++14
25 / 100
 2000 ms 1520 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long double ld;
typedef long long ll;

constexpr int N = 15;

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:23:8: warning: unused variable 'res' [-Wunused-variable]
   23 |     ll res = n * n;
      |        ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 600 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 6 ms 600 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 7 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 8 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 596 ms 604 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2041 ms 1520 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 67 ms 1112 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 64 ms 856 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 65 ms 600 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 68 ms 600 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 11 ms 600 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 55 ms 600 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 21 ms 604 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 21 ms 604 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 21 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 21 ms 604 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 21 ms 600 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 21 ms 604 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 21 ms 604 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 25 ms 600 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 21 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 23 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 67 ms 1112 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 64 ms 856 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 65 ms 600 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 68 ms 600 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 11 ms 600 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 55 ms 600 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 21 ms 604 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 21 ms 604 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 21 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 21 ms 604 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 21 ms 600 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 21 ms 604 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 21 ms 604 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 25 ms 600 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 21 ms 604 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 23 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 9 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 65 ms 604 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 64 ms 600 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 65 ms 604 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 72 ms 604 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 11 ms 600 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 55 ms 604 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 22 ms 604 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 21 ms 604 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 21 ms 604 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 21 ms 600 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 21 ms 604 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 22 ms 604 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 21 ms 604 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 21 ms 600 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 21 ms 600 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 21 ms 604 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Execution timed out 2080 ms 604 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 547 ms 600 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 6 ms 600 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 7 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 8 ms 604 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 596 ms 604 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2041 ms 1520 KB Time limit exceeded
7 Halted 0 ms 0 KB -