oj.uz

답안 #723150

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
723150 2023-04-13T09:20:28 Z drdilyor Boarding Passes (BOI22_passes) C++17
25 / 100
 2000 ms 676 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;

ld exp_inv(ll x) {
    return x * (x-1) / 2.0l;
}

int main() {
    char a = 'A';
    string s; cin >> s;
    const int G = 7;
    int n = s.size();
    vector memo(1<<G, (ld)-1);
    auto dp = [&](auto& dp, int used)->ld{
        if (memo[used] >= 0) return memo[used];
        if (__builtin_popcount(used) == G) return 0;
        ld res = 1e18;
        for (int i = 0 ;i < G; i++) {
            ld cur = 1e18;
            if (used&1<<i) continue;
            vector has(n, 0);
            for (int j = 0; j < n; j++) {
                if (used& 1<<(s[j] - a))
                    has[j] = 1;
            }
            for (int mid = 1; mid < n; mid++) {
                ll sum = 0;
                ll t= 0, c1{}, c2{};
                for (int j = 0; j < mid; j++) {
                    if (s[j] == i + a)
                        sum += t, c1++;
                    else t += has[j];
                }
                t = 0;
                for (int j = n-1; j >= mid; j--) {
                    if (s[j] == i + a)
                        sum += t, c2++;
                    else t += has[j];
                }
                cur = min(cur, sum + (exp_inv(c1) + exp_inv(c2)) / 2);
            }
            res = min(res, cur + dp(dp, used |1<<i));
        }
        return memo[used] = res;
    };
    cout << dp(dp, 0) << '\n';
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 258 ms 212 KB 1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603'
2 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 4 ms 296 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 5 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 5 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 5 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 4 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 4 ms 296 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 5 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 5 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 5 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 4 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 4 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 6 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 4 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 5 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 0 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 4 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 212 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 2 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Execution timed out 2070 ms 676 KB Time limit exceeded
36 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 258 ms 212 KB 1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603'
2 Halted 0 ms 0 KB -