oj.uz

Submission #824046

# Submission time Handle Problem Language Result Execution time Memory
824046 2023-08-13T12:14:25 Z ttamx Boarding Passes (BOI22_passes) C++14
5 / 100
 5 ms 4604 KB 
#include<bits/stdc++.h>

using namespace std;

typedef long double ld;

const int G=20;
const int N=1e5+5;
const int M=(1<<G)+5;

int n,g;
int a[N];
vector<int> pos[G];
ld dp[M],pref[N],suff[N];

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cout << fixed;
    string s;
    cin >> s;
    n=s.size();
    for(int i=1;i<=n;i++){
        a[i]=s[i-1]-'A';
        pos[a[i]].emplace_back(i);
        g=max(g,a[i]+1);
    }
    for(int mask=1;mask<1<<g;mask++){
        dp[mask]=DBL_MAX;
        for(int bit=0;bit<g;bit++){
            if(mask>>bit&1){
                int mask2=1<<bit^mask;
                int cnt=0;
                for(int i=1;i<=n;i++){
                    pref[i]=pref[i-1];
                    if(a[i]==bit)pref[i]+=0.5l*cnt;
                    cnt+=mask>>a[i]&1;
                }
                cnt=0;
                for(int i=n;i>=1;i--){
                    suff[i]=suff[i+1];
                    if(a[i]==bit)suff[i]+=0.5l*cnt;
                    cnt+=mask>>a[i]&1;
                }
                ld res=DBL_MAX;
                for(int i=0;i<=n;i++)res=min(res,pref[i]+suff[i+1]);
                dp[mask]=min(dp[mask],dp[mask2]+res);
            }
        }
    }
    cout << dp[(1<<g)-1];
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 3668 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 4308 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 4604 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 5 ms 4496 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Incorrect 1 ms 340 KB 1st numbers differ - expected: '1023.0000000000', found: '597.5000000000', error = '0.4159335288'
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Incorrect 1 ms 340 KB 1st numbers differ - expected: '1023.0000000000', found: '597.5000000000', error = '0.4159335288'
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 340 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 0 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 3 ms 3668 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 4308 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 4604 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 5 ms 4496 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 340 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 340 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Incorrect 1 ms 340 KB 1st numbers differ - expected: '1023.0000000000', found: '597.5000000000', error = '0.4159335288'
13 Halted 0 ms 0 KB -