oj.uz

Submission #850421

# Submission time Handle Problem Language Result Execution time Memory
850421 2023-09-16T14:23:17 Z Ahmed57 Boarding Passes (BOI22_passes) C++17
0 / 100
 1 ms 2396 KB 
#include <bits/stdc++.h>
using namespace std;
int c = 0;
vector<int> arr[15];
short pref[10001][1024],suf[10001][1024];
long double dp[1024];
int sz;
long double ge(long double x){
    if(x<=1)return 0;
    return (x*(x-1))/4.0;
}
int main(){
    string s;cin>>s;
    map<char,int> x;
    int ind = -1;
    sz = s.size();
    for(auto i:s){
        ind++;
        if(x[i]==0){
            x[i] = ++c;
            arr[c-1].push_back(ind);
        }else{
            arr[x[i]-1].push_back(ind);
        }
    }
    if(c>10){
        cout<<"a3"<<endl;
        return 0;
    }
    if(c>1){
    for(int mask = 0;mask<(1<<c);mask++){
        for(int i = 0;i<sz;i++){
            pref[i][mask] = (mask&(1<<(x[s[i]]-1))?1:0);
            if(i)pref[i][mask]+=pref[i-1][mask];
        }
        for(int i = sz-1;i>=0;i--){
            suf[i][mask] =(mask&(1<<(x[s[i]]-1))?1:0);
            if(i<sz-1)suf[i][mask]+=suf[i+1][mask];
        }
    }
    }
    for(int mask = (1<<c)-1;mask>=0;mask--){
    if(mask==(1<<c)-1){
        dp[mask] = 0;
        continue;
    }
    dp[mask] = 1000000000.0;
    for(int j = 0;j<c;j++){
        if(!(mask&(1<<j))){
            long long all = 0 , xd = 0;
            if(c>1){for(int e = 0;e<arr[j].size();e++){
                all+=suf[arr[j][e]][mask];
            }
            }
            dp[mask] = min(dp[mask],dp[mask^(1<<j)]+all+xd+ge(arr[j].size()));
            if(c==1)continue;
            for(int e = 0;e<arr[j].size();e++){
                all-=suf[arr[j][e]][mask];
                xd+=pref[arr[j][e]][mask];
                dp[mask] = min(dp[mask],dp[mask^(1<<j)]+all+xd+ge(e+1)+ge(arr[j].size()-e-1));
            }
        }
    }
    }
    cout<<setprecision(4)<<fixed<<dp[0]<<endl;
    return 0;
}

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:51:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |             if(c>1){for(int e = 0;e<arr[j].size();e++){
      |                                   ~^~~~~~~~~~~~~~
passes.cpp:57:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             for(int e = 0;e<arr[j].size();e++){
      |                           ~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st numbers differ - expected: '100800.5000000000', found: '201825.5000000000', error = '1.0022271715'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Incorrect 1 ms 344 KB 1st numbers differ - expected: '1225.0000000000', found: '2475.0000000000', error = '1.0204081633'
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Incorrect 1 ms 344 KB 1st numbers differ - expected: '1225.0000000000', found: '2475.0000000000', error = '1.0204081633'
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st numbers differ - expected: '100800.5000000000', found: '201825.5000000000', error = '1.0022271715'
2 Halted 0 ms 0 KB -