oj.uz

Submission #850405

# Submission time Handle Problem Language Result Execution time Memory
850405 2023-09-16T14:04:37 Z Ahmed57 Boarding Passes (BOI22_passes) C++17
25 / 100
 36 ms 84072 KB 
#include <bits/stdc++.h>
using namespace std;
int c = 0;
vector<int> arr[10];
int pref[1024][10001],suf[1024][10001];
long double dp[1024];
long double ge(double x){
    return (x*(x-1))/4;
}
long double solve(int mask){
    if(mask==(1<<c)-1){
        return 0;
    }
    if(dp[mask]==dp[mask])return dp[mask];
    long double ans = 10000000.0;
    for(int j = 0;j<c;j++){
        if(!(mask&(1<<j))){
            long long all = 0 , xd = 0;
            for(int e = 0;e<arr[j].size();e++){
                all+=suf[arr[j][e]][mask];
            }
            ans = min(ans,solve(mask^(1<<j))+all+xd+ge(arr[j].size()));
            for(int e = 0;e<arr[j].size();e++){
                all-=suf[arr[j][e]][mask];
                xd+=pref[arr[j][e]][mask];
                ans = min(ans,solve(mask^(1<<j))+all+xd+ge(e+1)+ge(arr[j].size()-e-1));
            }
        }
    }
    return dp[mask] = ans;
}
int main(){
    string s;cin>>s;
    map<char,int> x;
    int ind = -1;
    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);
        }
    }
    for(int mask = 0;mask<(1<<c);mask++){
        for(int i = 0;i<s.size();i++){
            pref[i][mask] = (mask&(1<<(x[s[i]]-1))?1:0);
            if(i)pref[i][mask]+=pref[i-1][mask];
        }
        for(int i = s.size()-1;i>=0;i--){
            suf[i][mask] =(mask&(1<<(x[s[i]]-1))?1:0);
            if(i<s.size()-1)suf[i][mask]+=suf[i+1][mask];
        }
    }
    memset(dp,-1,sizeof dp);
    cout<<solve(0)<<endl;
    return 0;
}

Compilation message

passes.cpp: In function 'long double solve(int)':
passes.cpp:19:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |             for(int e = 0;e<arr[j].size();e++){
      |                           ~^~~~~~~~~~~~~~
passes.cpp:23:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |             for(int e = 0;e<arr[j].size();e++){
      |                           ~^~~~~~~~~~~~~~
passes.cpp: In function 'int main()':
passes.cpp:46:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for(int i = 0;i<s.size();i++){
      |                       ~^~~~~~~~~
passes.cpp:52:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             if(i<s.size()-1)suf[i][mask]+=suf[i+1][mask];
      |                ~^~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 76380 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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 2 ms 12636 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 2 ms 12636 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 2 ms 12636 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 2 ms 12636 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 6492 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 2 ms 12636 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 6492 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 6564 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 6488 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 6492 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 2 ms 6492 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 6492 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 6492 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 6492 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 6492 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 6492 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 2 ms 12636 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 2 ms 12636 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 2 ms 12636 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 2 ms 12636 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 6492 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 2 ms 12636 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 6492 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 6564 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 6488 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 6492 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 2 ms 6492 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 6492 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 6492 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 6492 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 6492 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 6492 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 6492 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 12636 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 2 ms 12636 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 2 ms 12636 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 2 ms 12632 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 6492 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 2 ms 12636 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 6492 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 6488 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 6492 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 6492 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 6492 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 6492 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 6492 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 6492 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 6492 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 6492 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Runtime error 36 ms 84072 KB Execution killed with signal 11
36 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 76380 KB 1st numbers differ - expected: '100800.5000000000', found: '100800.0000000000', error = '0.0000049603'
2 Halted 0 ms 0 KB -