oj.uz

Submission #576703

# Submission time Handle Problem Language Result Execution time Memory
576703 2022-06-13T09:37:44 Z InternetPerson10 Boarding Passes (BOI22_passes) C++17
0 / 100
 1 ms 212 KB 
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

ll BIG = 1e13;

vector<int> nums;
vector<vector<int>> ct;
vector<ll> dp;
vector<vector<ll>> pref;
vector<vector<int>> v;

int n, g;

ll solve(int bit);

ll solvebit(int bit, int las) {
    int bi = bit - (1 << las);
    ll ans = solve(bi);
    ll tot = BIG, tot2 = 0;
    ll m = ct[las].size();
    if(m == 0) return ans;
    ll x = 0;
    for(int g : ct[las]) {
        for(int k : v[bi]) {
            tot2 += pref[k][g];
        }
    }
    for(int k : v[bi]) {
        x += pref[k][n];
    }
    tot = min(tot, 2 * tot2 + (m * m - m) / 2);
    for(ll i = m-1; i >= 0; i--) {
        tot2 += x;
        for(int k : v[bi]) {
            tot2 -= 2 * pref[k][ct[las][i]];
        }
        assert(tot2 >= 0);
        tot = min(tot, 2 * tot2 + (i * i - i) / 2 + ((m-i) * (m-i) - (m-i)) / 2);
    }
    return ans + tot;
}

ll solve(int bit) {
    if(bit == 0) return 0;
    if(dp[bit] != BIG) return dp[bit];
    ll ans = BIG;
    for(int i : v[bit]) {
        ans = min(ans, solvebit(bit, i));
    }
    return dp[bit] = ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    n = s.size();
    nums.resize(n);
    ct.resize(15);
    g = 0;
    for(int i = 0; i < n; i++) {
        nums[i] = s.at(i) - 'A';
        g = max(g, nums[i]+1);
        ct[nums[i]].push_back(i);
    }
    v.resize(1 << g);
    for(int i = 0; i < (1 << g); i++) {
        for(int j = 0; j < g; j++) {
            if((1 << j) & i) v[i].push_back(j);
        }
    }
    pref.resize(g);
    dp.resize(1 << g, BIG);
    dp[0] = 0;
    for(int i = 0; i < g; i++) {
        pref[i].resize(n+1);
        for(int j = 0; j < n; j++) {
            pref[i][j+1] = pref[i][j];
            if(nums[j] == i) pref[i][j+1]++;
        }
    }
    cout << fixed << setprecision(1) << (double)solve((1 << g) - 1) / 2.0 << endl;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -