oj.uz

Submission #850419

# Submission time Handle Problem Language Result Execution time Memory
850419 2023-09-16T14:22:02 Z Ahmed57 Boarding Passes (BOI22_passes) C++17
55 / 100
 595 ms 45188 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;
    }
    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;
            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()));
            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:49:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             for(int e = 0;e<arr[j].size();e++){
      |                           ~^~~~~~~~~~~~~~
passes.cpp:53:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             for(int e = 0;e<arr[j].size();e++){
      |                           ~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 2392 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 2 ms 6744 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Runtime error 22 ms 45188 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 4696 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 4444 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 4952 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 4696 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 2392 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 4696 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 2392 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 2392 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 2392 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 2392 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 2392 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 2392 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 2392 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 2392 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 2392 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 2392 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 2392 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 4696 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 4444 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 4952 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 4696 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 2392 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 4696 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 2392 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 2392 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 2392 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 2392 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 2392 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 2392 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 2392 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 2392 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 2392 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 2392 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 2392 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 4696 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 4700 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 4700 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 4700 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 2592 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 4696 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 2392 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 2396 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 2392 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 2392 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 2396 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 2392 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 2392 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 2392 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 2396 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 2392 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 5 ms 40536 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 5 ms 40536 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 595 ms 40604 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 288 ms 40572 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 296 ms 40536 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 289 ms 40512 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 416 ms 40280 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 417 ms 40024 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 418 ms 40192 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 413 ms 40024 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 415 ms 40272 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 416 ms 40132 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 2392 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 2396 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 2396 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 2 ms 6744 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Runtime error 22 ms 45188 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -