oj.uz

Submission #685572

# Submission time Handle Problem Language Result Execution time Memory
685572 2023-01-24T14:44:35 Z MtSaka Boarding Passes (BOI22_passes) C++17
100 / 100
 193 ms 48796 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(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  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 1 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 316 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 224 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 5 ms 3688 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 5 ms 4288 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 4544 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 7 ms 4472 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 316 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 320 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 340 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 324 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 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 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 320 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 212 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 324 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 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 1 ms 324 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 316 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 320 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 340 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 324 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 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 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 320 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 212 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 324 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 316 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 316 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 340 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 324 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 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 212 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 0 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 2888 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 5 ms 3600 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 4 ms 3540 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 4 ms 3532 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 3548 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 6 ms 3528 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 5 ms 3544 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 5 ms 3544 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 5 ms 3540 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 5 ms 3544 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 0 ms 316 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 0 ms 224 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 5 ms 3688 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 5 ms 4288 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 5 ms 4544 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 7 ms 4472 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 324 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 316 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 320 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 340 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 324 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 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 1 ms 340 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 320 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 212 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 324 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 0 ms 212 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 316 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 316 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 340 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 324 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 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 212 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 0 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 2888 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 5 ms 3600 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 4 ms 3540 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 4 ms 3532 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 3548 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 6 ms 3528 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 5 ms 3544 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 5 ms 3544 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 5 ms 3540 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 5 ms 3544 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 14 ms 600 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 45 ms 600 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 340 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 0 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 1 ms 212 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 320 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 340 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 4 ms 3624 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 5 ms 4208 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 6 ms 4536 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 5 ms 4544 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 1 ms 320 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 1 ms 316 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 340 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 340 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 340 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 1 ms 324 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 340 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 212 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 212 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 324 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 216 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 216 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 324 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 212 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 316 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 0 ms 212 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 212 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 3 ms 2900 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 3 ms 2900 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 5 ms 3540 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 4 ms 3540 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 4 ms 3624 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 6 ms 3540 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 5 ms 3484 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 6 ms 3532 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 5 ms 3540 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 5 ms 3540 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 6 ms 3552 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 162 ms 48772 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 20 ms 468 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 170 ms 48696 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 76 ms 48692 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 31 ms 596 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 151 ms 48716 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 162 ms 48796 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 193 ms 48488 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 163 ms 48668 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 177 ms 48584 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 178 ms 48520 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 183 ms 48580 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 92 ms 45168 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 165 ms 48652 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'