oj.uz

Submission #1053540

# Submission time Handle Problem Language Result Execution time Memory
1053540 2024-08-11T13:01:36 Z sofijavelkovska Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 8448 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN=1e5, MAXK=15;
const long long INF=1e18;

string s;
int n, k;
vector<vector<int> > groups;
double memo[(1<<MAXK)];
double inv[MAXN+1];

double dp(int mask)
{
    if (memo[mask]!=-1)
        return memo[mask];
    if (mask==(1<<k)-1)
        return memo[mask]=0;
    int prefix[n]={0};
    for (int i=0; i<k; i++)
    {
        if (!(mask&(1<<i)))
            continue;
        for (auto x : groups[i])
            prefix[x]=1;
    }
    for (int i=1; i<n; i++)
        prefix[i]=prefix[i-1]+prefix[i];
    int m=prefix[n-1];
    double answer=INF;
    for (int i=0; i<k; i++)
    {
        if (mask&(1<<i))
            continue;
        double mintotal=INF;
        long long maininv=0;
        int g=groups[i].size();
        for (auto x : groups[i])
            if (x!=0)
                maininv=maininv+prefix[x-1];
        mintotal=min(mintotal, inv[g]+maininv);
        for (int j=g-1; j>=0; j--)
        {
            int x=groups[i][j];
            if (x!=0)
                maininv=maininv-prefix[x-1];
            maininv=maininv+(m-prefix[x]);
            mintotal=min(mintotal, inv[j]+inv[g-j]+maininv);
        }
        answer=min(answer, dp(mask|(1<<i))+mintotal);
    }

    return memo[mask]=answer;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> s;
    n=s.size();
    map<char, vector<int> > groupsbychar;
    for (int i=0; i<n; i++)
        groupsbychar[s[i]].push_back(i);
    for (auto t : groupsbychar)
        groups.push_back(t.second);
    k=groups.size();
    for (int i=0; i<=n; i++)
        inv[i]=(double)i*(i-1)/4;
    for (int i=0; i<(1<<k); i++)
        memo[i]=-1;
    cout << fixed << setprecision(5) << dp(0);

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 1 ms 2276 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 2472 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 2704 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 2704 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 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 0 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 0 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 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 1 ms 344 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 344 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 348 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 0 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 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 0 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 0 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 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 1 ms 344 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 344 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 348 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 0 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 0 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 1 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 0 ms 344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 0 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 0 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 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 0 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 0 ms 348 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 0 ms 604 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 0 ms 604 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 17 ms 860 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 17 ms 860 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 17 ms 860 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 17 ms 856 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 17 ms 860 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 17 ms 860 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 17 ms 1076 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 17 ms 1064 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 17 ms 856 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 19 ms 1076 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 344 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 1 ms 2276 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 2472 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 2704 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 2704 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 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 0 ms 348 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 0 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 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 1 ms 344 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 344 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 348 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 0 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 0 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 1 ms 348 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 0 ms 344 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 0 ms 348 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 348 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 0 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 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 0 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 0 ms 348 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 0 ms 604 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 0 ms 604 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 17 ms 860 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 17 ms 860 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 17 ms 860 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 17 ms 856 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 17 ms 860 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 17 ms 860 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 17 ms 1076 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 17 ms 1064 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 17 ms 856 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 19 ms 1076 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 0 ms 348 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 4 ms 604 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 0 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 348 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 0 ms 348 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 2272 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 3 ms 2472 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 2 ms 2704 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 2 ms 2704 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 344 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 0 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 1 ms 604 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 0 ms 604 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 17 ms 1080 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 17 ms 860 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 17 ms 860 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 17 ms 1056 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 22 ms 860 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 17 ms 1076 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 19 ms 1048 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 17 ms 860 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 17 ms 860 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 17 ms 860 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2099 ms 8448 KB Time limit exceeded
97 Halted 0 ms 0 KB -