oj.uz

Submission #1053537

# Submission time Handle Problem Language Result Execution time Memory
1053537 2024-08-11T12:59:26 Z sofijavelkovska Boarding Passes (BOI22_passes) C++17
60 / 100
 2000 ms 8372 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 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 2208 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 2640 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 2636 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 2632 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 344 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 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 348 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 448 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 1 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 1 ms 344 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 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 348 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 448 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 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 0 ms 612 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 1 ms 348 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 0 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 0 ms 448 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 0 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 1 ms 344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 0 ms 344 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 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 19 ms 1064 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 16 ms 856 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 16 ms 860 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 17 ms 1060 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 16 ms 860 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 16 ms 1060 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 21 ms 1308 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 21 ms 968 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 16 ms 860 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 2208 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 3 ms 2640 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 2636 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 2632 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 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 1 ms 344 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 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 348 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 448 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 1 ms 348 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 0 ms 612 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 1 ms 348 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 0 ms 348 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 0 ms 448 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 0 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 1 ms 344 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 0 ms 344 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 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 19 ms 1064 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 16 ms 856 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 16 ms 860 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 17 ms 1060 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 16 ms 860 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 16 ms 1060 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 21 ms 1308 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 21 ms 968 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 16 ms 860 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 1 ms 344 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 5 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 2204 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 2 ms 2660 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 3 ms 2748 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 3 ms 2632 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 448 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 0 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 0 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 344 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 452 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 0 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 856 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 18 ms 860 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 15 ms 1088 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 16 ms 860 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 16 ms 1060 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 16 ms 860 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 17 ms 856 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 20 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 16 ms 860 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2093 ms 8372 KB Time limit exceeded
97 Halted 0 ms 0 KB -