oj.uz

Submission #898153

# Submission time Handle Problem Language Result Execution time Memory
898153 2024-01-04T11:00:51 Z GrindMachine Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 2644 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

void solve(int test_case)
{
    string s; cin >> s;
    ll n = sz(s);
    s = "$" + s;

    ll siz = 0;
    rep1(i,n){
        amax(siz,(ll)s[i]-'A'+1);
    }

    vector<ll> pos[siz];
    rep1(i,n) pos[s[i]-'A'].pb(i);

    vector<ll> dp(1<<siz,inf2);
    dp[0] = 0;

    vector<ll> pref(n+5);

    rep(mask,1<<siz){
        fill(all(pref),0);
        rep(c,siz){
            if(mask&(1<<c)){
                trav(i,pos[c]){
                    pref[i]++;
                }
            }
        }

        rep1(i,n) pref[i] += pref[i-1];

        rep(c,siz){
            if(mask&(1<<c)) conts;
            auto &p = pos[c];
            if(p.empty()){
                amin(dp[mask|(1<<c)],dp[mask]);
                conts;
            }

            ll s1 = 0, s2 = sz(p);
            ll cost1 = 0, cost2 = 0;

            trav(i,p){
                cost2 += pref[n]-pref[i];
            }

            ll mn_cost = inf2;
            amin(mn_cost,s2*(s2-1)+cost2*4);

            trav(i,p){
                s1++, s2--;
                cost1 += pref[i];
                cost2 -= pref[n]-pref[i];
                amin(mn_cost,s1*(s1-1)+s2*(s2-1)+cost1*4+cost2*4);
            }

            amin(dp[mask|(1<<c)],dp[mask]+mn_cost);
        }
    }

    ld ans = (ld)dp[(1<<siz)-1]/4;
    cout << fixed << setprecision(11);
    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 1740 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 1996 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 2036 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 2252 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 0 ms 460 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 372 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 344 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 464 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 0 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 0 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 0 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 0 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 0 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 0 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 0 ms 452 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 0 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 0 ms 456 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 0 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 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 0 ms 460 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 372 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 344 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 464 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 0 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 0 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 0 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 0 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 0 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 0 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 0 ms 452 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 0 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 0 ms 456 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 0 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 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 0 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 0 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 0 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 0 ms 344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 0 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 0 ms 452 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 0 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 0 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 0 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 612 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 0 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 344 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 0 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 0 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 10 ms 700 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 10 ms 604 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 42 ms 688 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 37 ms 656 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 37 ms 600 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 38 ms 604 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 41 ms 720 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 39 ms 600 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 39 ms 604 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 39 ms 604 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 39 ms 604 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 39 ms 600 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 0 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 1740 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 1996 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 2036 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 4 ms 2252 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 0 ms 460 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 372 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 344 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 464 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 0 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 0 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 0 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 0 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 0 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 0 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 0 ms 452 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 0 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 0 ms 456 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 0 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 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 0 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 0 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 0 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 0 ms 344 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 0 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 0 ms 452 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 0 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 0 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 0 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 612 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 0 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 344 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 0 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 0 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 10 ms 700 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 10 ms 604 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 42 ms 688 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 37 ms 656 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 37 ms 600 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 38 ms 604 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 41 ms 720 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 39 ms 600 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 39 ms 604 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 39 ms 604 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 39 ms 604 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 39 ms 600 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 8 ms 712 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 7 ms 600 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 348 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 0 ms 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 0 ms 460 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 0 ms 344 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 0 ms 348 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 2 ms 1796 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 3 ms 2252 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 3 ms 2252 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 2 ms 2252 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 0 ms 348 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 0 ms 348 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 0 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 0 ms 348 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 0 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 0 ms 348 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 0 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 0 ms 348 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 0 ms 348 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 0 ms 348 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 0 ms 348 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 0 ms 348 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 0 ms 348 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 0 ms 348 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 10 ms 600 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 10 ms 604 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 40 ms 604 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 37 ms 604 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 45 ms 600 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 38 ms 600 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 40 ms 604 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 39 ms 604 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 42 ms 692 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 39 ms 460 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 39 ms 856 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 39 ms 600 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2036 ms 2644 KB Time limit exceeded
97 Halted 0 ms 0 KB -