oj.uz

Submission #734908

# Submission time Handle Problem Language Result Execution time Memory
734908 2023-05-03T08:54:40 Z adrilen Boarding Passes (BOI22_passes) C++17
100 / 100
 525 ms 354852 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
typedef pair<int, int> pii;
constexpr int maxn = 1e5 + 5, maxg = 15;

ll dp[1 << maxg] = { 0 };

ll f[maxn] = { 0 };

ll left_pref[maxn][maxg][maxg] = { 0 }, right_pref[maxn][maxg][maxg] = { 0 };
vector <int> groups[maxg];

int n, g;
// Finding the best way to split the new group given that some groups allready are seated
ll query(int allready, int next_one)
{
    int lower = 0, upper = groups[next_one].size(), mid;
    ll sleft = 0, sright = 0;
    while (lower < upper)
    {
        mid = (lower + upper) >> 1;

        // Testing mid
        sleft = sright = 0;      

        sleft += f[mid] + f[groups[next_one].size() - mid];
        sright += f[mid + 1] + f[groups[next_one].size() - mid - 1];

        for (int y = 0; y < g; y++)
        {
            if ((allready & (1 << y)) == 0) continue;


            if (groups[next_one][mid] != 0) 
                sleft += left_pref[groups[next_one][mid] - 1][next_one][y];
            sleft += right_pref[groups[next_one][mid]][next_one][y];

            if (groups[next_one][mid] + 1 != n) 
                sright += right_pref[groups[next_one][mid] + 1][next_one][y];
            sright += left_pref[groups[next_one][mid]][next_one][y];
        }

        // cout << mid << " " << sleft << " \t" << mid + 1 << " " << sright << "\n";

        if (sleft < sright) upper = mid;
        else lower = mid + 1;
    }
    // cout << allready << " " << next_one << " " << "A" << min(sleft, sright) << "\n";
    return min(sleft, sright);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    for (int i = 1; i < maxn - 1; i++) f[i + 1] = f[i] + i; // Double the actual amount


    string s;
    cin >> s;
    n = s.size();
    vector <int> v(n);
    for (int i = 0; i < n; i++) {
        v[i] = s[i] - 'A';
        groups[s[i] - 'A'].emplace_back(i);
        g = max(g, s[i] - 'A' + 1);
    }


    ll sum, seen;
    // Making prefixsum from left
    for (int x = 0; x < g; x++)         // Want to place
    {
        for (int y = 0; y < g; y++)     // Already placed
        {
            if (x == y) continue;
            sum = 0, seen = 0;
            for (int i = 0; i < n; i++)
            {
                if (v[i] == x) sum += seen;
                else if (v[i] == y) seen += 2; // Double the actual amount to keep to integers

                left_pref[i][x][y] = sum; 
                // cout << i << " " << seen << " " << sum << "\n";
            }
        }
    }

    // Making right prefix
    for (int x = 0; x < g; x++)         // Want to place
    {
        for (int y = 0; y < g; y++)     // Already placed
        {
            if (x == y) continue;
            sum = 0, seen = 0;
            for (int i = n - 1; i >= 0; i--)
            {
                if (v[i] == x) sum += seen;
                else if (v[i] == y) seen += 2; // Double the actual amount to keep to integers

                right_pref[i][x][y] = sum;
            }
        }
    }



    // Solving with bitset dp
    ll best;
    for (int i = 0; i < (1 << g); i++)
    {

        best = 2e15;
        for (int y = 0; y < g; y++)
        {
            if (i & (1 << y))
            {
                best = min(best, dp[i - (1 << y)] + query(i - (1 << y), y));
                // Update best
            }
        }
        if (best == 2e15) best = 0;
        dp[i] = best;
    }
    cout << dp[(1 << g) - 1] / 2;
    if (dp[(1 << g) - 1] & 1) cout << ".5";
    cout << "\n";

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 1108 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 1108 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 1108 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 1120 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 2324 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 2348 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 3 ms 2452 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 ms 2480 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 1108 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 1364 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 1364 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 1364 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 1492 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 1108 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 1368 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 1108 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 1108 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 1108 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 1108 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 1108 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 1236 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 1108 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 1108 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 1236 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 1236 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 1108 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 1364 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 1364 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 1364 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 1492 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 1108 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 1368 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 1108 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 1108 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 1108 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 1108 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 1108 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 1236 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 1108 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 1108 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 1236 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 1236 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 1108 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 1364 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 1384 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 1376 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 1364 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 1108 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 1376 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 1108 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 2 ms 1120 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 1120 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 1108 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 1236 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 1236 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 1236 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 1108 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 1108 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 1108 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 20 ms 36436 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 20 ms 36484 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 23 ms 36436 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 27 ms 36468 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 21 ms 36504 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 22 ms 36224 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 24 ms 35708 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 27 ms 35680 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 24 ms 35668 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 22 ms 35744 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 24 ms 35716 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 25 ms 35668 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1108 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 1108 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 1108 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 1108 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 1120 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 2 ms 2324 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 2 ms 2348 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 3 ms 2452 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 3 ms 2480 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 1108 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 1364 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 1364 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 1364 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 1492 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 1108 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 1368 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 1108 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 1108 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 1108 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 1108 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 1108 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 1236 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 1108 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 1108 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 1236 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 1236 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 1108 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 1364 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 1384 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 1376 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 1364 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 1108 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 1376 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 1108 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 2 ms 1120 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 1120 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 1108 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 1236 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 1236 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 1236 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 1108 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 1108 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 1108 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 20 ms 36436 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 20 ms 36484 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 23 ms 36436 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 27 ms 36468 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 21 ms 36504 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 22 ms 36224 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 24 ms 35708 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 27 ms 35680 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 24 ms 35668 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 22 ms 35744 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 24 ms 35716 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 25 ms 35668 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 13 ms 1364 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 35 ms 1404 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 2 ms 1112 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 ms 1108 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 1 ms 1108 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 1108 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 1108 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 2 ms 2256 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 3 ms 2344 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 3 ms 2476 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 2 ms 2452 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 1 ms 1108 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 1 ms 1368 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 1364 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 1364 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 1364 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 1108 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 1364 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 1236 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 1236 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 1108 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 1116 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 1108 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 2 ms 1120 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 1124 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 2 ms 1108 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 1108 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 2 ms 1108 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 23 ms 36480 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 20 ms 36436 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 25 ms 36436 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 28 ms 36384 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 28 ms 36456 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 25 ms 36328 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 26 ms 35752 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 24 ms 35652 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 24 ms 35668 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 24 ms 35668 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 23 ms 35668 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 25 ms 35668 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 525 ms 354852 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 16 ms 1364 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 493 ms 354580 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 394 ms 354828 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 21 ms 1380 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 445 ms 354672 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 481 ms 354740 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 476 ms 353560 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 468 ms 353276 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 501 ms 353468 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 468 ms 353560 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 515 ms 353284 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 376 ms 352872 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 500 ms 353340 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'