oj.uz

Submission #685559

# Submission time Handle Problem Language Result Execution time Memory
685559 2023-01-24T14:26:16 Z MtSaka Boarding Passes (BOI22_passes) C++17
100 / 100
 176 ms 48692 KB 
#include<bits/stdc++.h>
using ll=long long;
#define rep(i,a,b) for(ll i=(ll)a;i<(ll)b;++i)
#define rrep(i,a,b) for(ll i=(ll)b-1;i>=(ll)a;--i)
using namespace std;
int main(){
  string S;cin>>S;
  vector<int>s;
  for(auto&e:S)s.push_back(e-'A');
  const int n=s.size();
  const int g=*max_element(s.begin(),s.end())+1;
  vector idx(g,vector<int>());
  rep(i,0,n)idx[s[i]].push_back(i);
  vector prefix(g,vector<ll>(n,0));
  auto suffix=prefix;
  vector suml(g,vector<ll>(n,0));
  auto sumr=suml;
  rep(i,0,n){
    prefix[s[i]][i]++;
    suffix[s[i]][i]++;
  }
  rep(i,0,g){
    rep(j,0,n-1)prefix[i][j+1]+=prefix[i][j];
    rrep(j,0,n-1)suffix[i][j]+=suffix[i][j+1];
  }
  vector<int>last(g,-1);
  rep(i,0,n){
    rep(j,0,g)suml[j][i]=prefix[j][i];
    if(last[s[i]]!=-1)rep(j,0,g)suml[j][i]+=suml[j][last[s[i]]];
    last[s[i]]=i;
  }
  last=vector<int>(g,-1);
  rrep(i,0,n){
    rep(j,0,g)sumr[j][i]=suffix[j][i];
    if(last[s[i]]!=-1)rep(j,0,g)sumr[j][i]+=sumr[j][last[s[i]]];
    last[s[i]]=i;
  }
  auto calc1=[&](ll bit,ll i)->int {
    int ok=-1,ng=idx[i].size();
    while(ng-ok>1){
      int mid=(ok+ng)>>1;
      int p=idx[i][mid];
      ll l=0,r=0;
      rep(j,0,g){
        if((bit>>j)&1)l+=prefix[j][p]*2,r+=suffix[j][p]*2;
        else if(i==j)l+=prefix[j][p]-1,r+=suffix[j][p]-1;
      }
      if(l<=r)ok=mid;
      else ng=mid;
    }
    return ok;
  };
  auto calc2=[&](ll bit,ll i,int m)->ll {
    ll ret=0;
    if(m!=-1){
      int p=idx[i][m];
      rep(j,0,g){
        if((bit>>j)&1)ret+=suml[j][p]*2;
      }
    }
    if(m!=(int)idx[i].size()-1){
      int p=idx[i][m+1];
      rep(j,0,g){
        if((bit>>j)&1)ret+=sumr[j][p]*2;
      }
    }
    ret+=(ll)m*(m+1)/2;
    ret+=(ll)(idx[i].size()-m-1)*(idx[i].size()-m-2)/2;
    return ret;
  };
  vector dp(1<<g,LLONG_MAX>>2);
  dp[0]=0;
  rep(bit,0,1<<g){
    rep(i,0,g){
      if((bit>>i)&1)continue;
      if(idx[i].empty())dp[bit^(1<<i)]=min(dp[bit^(1<<i)],dp[bit]);
      else{
        int m=calc1(bit,i);
        ll cost=calc2(bit,i,m);
         //cerr<<bit<<" "<<i<<" "<<m<<" "<<cost<<endl;
        dp[bit^(1<<i)]=min(dp[bit^(1<<i)],dp[bit]+cost);
      }
    }
  }
  //for(auto&i:dp)cerr<<i<<endl;
  cout<<dp.back()/2<<(dp.back()&1?".5":"")<<endl;
}

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 0 ms 300 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 6 ms 3680 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 7 ms 4236 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 7 ms 4476 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 7 ms 4440 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 0 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 0 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 0 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 0 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 0 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 0 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 0 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 288 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 0 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 0 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 0 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 0 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 0 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 0 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 0 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 0 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 288 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 0 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 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 0 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 340 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 1 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 Correct 3 ms 2900 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 3 ms 2968 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 5 ms 3540 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 5 ms 3540 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 4 ms 3540 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 5 ms 3540 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 6 ms 3412 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 5 ms 3504 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 6 ms 3516 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 7 ms 3412 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 5 ms 3508 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 5 ms 3412 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.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 0 ms 300 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 6 ms 3680 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 7 ms 4236 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 7 ms 4476 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 7 ms 4440 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 0 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 0 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 0 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 0 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 0 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 0 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 0 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 288 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 0 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 212 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 212 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 212 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 212 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 212 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 212 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 212 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 0 ms 212 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 212 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 340 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 212 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 3 ms 2900 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 3 ms 2968 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 5 ms 3540 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 5 ms 3540 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 4 ms 3540 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 5 ms 3540 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 6 ms 3412 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 5 ms 3504 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 6 ms 3516 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 7 ms 3412 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 5 ms 3508 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 5 ms 3412 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 14 ms 472 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 48 ms 576 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 0 ms 352 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 0 ms 224 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 1 ms 224 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 224 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 352 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 7 ms 3632 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 9 ms 4232 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 7 ms 4488 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 7 ms 4452 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 0 ms 224 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 0 ms 224 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 308 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 312 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 312 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 224 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 308 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 224 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 308 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 0 ms 224 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 224 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 224 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 224 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 224 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 312 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 0 ms 224 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 224 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 3 ms 2880 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 3 ms 2912 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 5 ms 3504 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 5 ms 3540 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 4 ms 3508 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 5 ms 3464 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 5 ms 3412 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 5 ms 3412 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 5 ms 3412 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 5 ms 3412 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 6 ms 3512 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 7 ms 3416 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 174 ms 48692 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 20 ms 472 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 176 ms 48684 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 82 ms 48608 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 29 ms 468 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 158 ms 48692 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 166 ms 48660 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 163 ms 48564 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 166 ms 48576 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 166 ms 48544 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 162 ms 48568 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 163 ms 48544 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 102 ms 45276 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 175 ms 48540 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'