oj.uz

Submission #748633

# Submission time Handle Problem Language Result Execution time Memory
748633 2023-05-26T16:12:50 Z inventiontime Boarding Passes (BOI22_passes) C++17
25 / 100
 2000 ms 1680 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;
    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;
            loop(idx, n) {

                double ans = 0;
                int cnt = 0, oth = 0;
                for(int i = 0; i <= idx; i++) {
                    if(prev[id[s[i]-'A']]) oth++;
                    else if(id[s[i]-'A'] == ch) {
                        cnt++;
                        ans += oth;
                    }
                }
                ans += cst(cnt);

                cnt = 0, oth = 0;
                for(int i = n-1; i > idx; i--) {
                    if(prev[id[s[i]-'A']]) oth++;
                    else if(id[s[i]-'A'] == ch) {
                        cnt++;
                        ans += oth;
                    }
                }
                ans += cst(cnt);

                ckmin(cost, ans);
                
            }
            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;

}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 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 2 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2078 ms 1680 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 9 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 7 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 7 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 6 ms 340 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 2 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 2 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 2 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 2 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 320 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 2 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 2 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 2 ms 320 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 2 ms 316 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 9 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 7 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 7 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 6 ms 340 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 2 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 2 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 2 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 2 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 320 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 2 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 2 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 2 ms 320 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 2 ms 316 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 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 10 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 7 ms 320 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 7 ms 324 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 9 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 2 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 2 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 2 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 2 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 2 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 2 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 2 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 2 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 2 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 124 ms 540 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 125 ms 556 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Execution timed out 2090 ms 468 KB Time limit exceeded
38 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 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 2 ms 212 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Execution timed out 2078 ms 1680 KB Time limit exceeded
7 Halted 0 ms 0 KB -