oj.uz

Submission #823799

# Submission time Handle Problem Language Result Execution time Memory
823799 2023-08-13T06:54:08 Z PoonYaPat Boarding Passes (BOI22_passes) C++14
60 / 100
 2000 ms 1812 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll ans,dp[1<<15]; //2 times expected value
int m,n,g[100005];
vector<int> group[15];

ll cal(ll a) {
    return a*(a-1)/2;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    string s; cin>>s;
    n=s.size();
    for (int i=0; i<(1<<15); ++i) dp[i]=2e15;
    
    map<char,int> mp;
    for (int i=0; i<n; ++i) mp[s[i]]=0;
    for (auto k : mp) mp[k.first]=m++;
    for (int i=0; i<n; ++i) group[mp[s[i]]].push_back(i), g[i]=mp[s[i]];

    dp[0]=0;
    for (int mask=1; mask<(1<<m); ++mask) {
        //find dp[mask]
        bool have[15];
        for (int i=0; i<m; ++i) {
            if (mask&(1<<i)) have[i]=true;
            else have[i]=false;
        }

        for (int i=0; i<m; ++i) {
            if (mask&(1<<i)) { //consider case i is the last boarding group to put in

                ll cnt_back=0,sum_back=0,cnt_front=0,sum_front=0,cb=0,cf=0;
                for (int x=n-1; x>=0; --x) {
                    if (have[g[x]]) {
                        if (g[x]!=i) ++cnt_back;
                        else sum_back+=cnt_back, ++cb;
                    }
                }

                dp[mask]=min(dp[mask],dp[mask^(1<<i)]+cal(cb)+2*sum_back); //all get in from back

                for (int x=0; x<n; ++x) { //people number 0 to x get in from front
                    if (have[g[x]]) {
                        if (g[x]!=i) {
                            ++cnt_front;
                            --cnt_back;
                        } else {
                            ++cf;
                            --cb;
                            sum_front+=cnt_front;
                            sum_back-=cnt_back;
                            dp[mask]=min(dp[mask],dp[mask^(1<<i)]+cal(cf)+cal(cb)+2*sum_back+2*sum_front);
                        }
                    }
                }
            }
        }
    }

    cout<<dp[(1<<m)-1]/2;
    if (dp[(1<<m)-1]%2==1) cout<<".5";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 468 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 1684 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 1684 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 1684 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 1684 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 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 468 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 468 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 0 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 468 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 468 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 468 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 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 468 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 468 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 0 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 468 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 468 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 468 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 0 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 468 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 468 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 468 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 724 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 724 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 536 ms 704 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 73 ms 596 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 79 ms 744 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 82 ms 684 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 111 ms 724 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 118 ms 724 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 111 ms 724 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 105 ms 596 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 110 ms 724 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 108 ms 724 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 0 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 468 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 1684 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 1684 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 2 ms 1684 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 2 ms 1684 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 468 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 468 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 0 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 468 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 468 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 0 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 468 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 468 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 0 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 468 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 468 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 468 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 468 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 724 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 724 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 536 ms 704 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 73 ms 596 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 79 ms 744 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 82 ms 684 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 111 ms 724 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 118 ms 724 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 111 ms 724 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 105 ms 596 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 110 ms 724 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 108 ms 724 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 1 ms 596 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 54 ms 560 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 0 ms 596 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 1 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 596 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 2 ms 1684 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 2 ms 1684 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 2 ms 1812 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 2 ms 1812 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 1 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 1 ms 468 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 468 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 592 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 468 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 592 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 512 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 468 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 468 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 468 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 1 ms 724 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 724 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 536 ms 724 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 94 ms 596 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 78 ms 740 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 80 ms 692 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 111 ms 724 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 110 ms 724 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 111 ms 724 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 121 ms 596 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 110 ms 724 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 108 ms 724 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Execution timed out 2066 ms 1748 KB Time limit exceeded
97 Halted 0 ms 0 KB -