oj.uz

Submission #1099556

# Submission time Handle Problem Language Result Execution time Memory
1099556 2024-10-11T15:37:57 Z epicci23 Boarding Passes (BOI22_passes) C++17
100 / 100
 559 ms 332808 KB 
#include "bits/stdc++.h"
#define int long long
#define double long double
#define all(v) v.begin() , v.end()
#define sz(a) (int) a.size()
using namespace std;

const int LOG = 15;
const double INF = 1e18;
const int N = 1e5 + 5;
int suf[LOG][LOG][N];
int pre[LOG][LOG][N];
int ar[N],n,G;
vector<double> dp((1LL<<LOG) + 5,INF);
vector<int> pos[LOG];

void calc(){
  for(int i=0;i<G;i++){
  	for(int j=0;j<G;j++){
     if(i==j) continue;
     int res=0,kac=0;
     for(int x=1;x<=n;x++){
       if(ar[x]==j) kac++;
       else if(ar[x]==i) res+=kac;
       pre[i][j][x]=res;
     }
  	}
  }

  for(int i=0;i<G;i++){
  	for(int j=0;j<G;j++){
     if(i==j) continue;
     int res=0,kac=0;
     for(int x=n;x>=1;x--){
       if(ar[x]==j) kac++;
       else if(ar[x]==i) res+=kac;
       suf[i][j][x]=res;
     }
  	}
  }
}

double Get_Cost(int ind,int u,int mask){
  int le = ind + 1, ri = sz(pos[u]) - ind - 1;
  double res = le*(le-1)/4.0L + ri*(ri-1)/4.0L;
  //cout << "ilk: " << res << '\n';
  for(int i=0;i<G;i++){
  	if(ind==-1) break;
  	if(!(mask>>i&1)) continue;
  	res += pre[u][i][pos[u][ind]];
  }
  //cout << "sec: " << res << '\n';
  for(int i=0;i<G;i++){
    if(ind+1>=sz(pos[u])) break;
  	if(!(mask>>i&1)) continue;
  	res += suf[u][i][pos[u][ind+1]];
  }
  //cout << "tri: " << res << '\n';
  return res;
}


void _(){
  string s;
  cin >> s;
  n=sz(s);

  vector<int> zip;
  for(int i=0;i<n;i++) zip.push_back(s[i]-'A');
  sort(all(zip));
  zip.erase(unique(all(zip)),zip.end());
  for(int i=1;i<=n;i++) ar[i]=lower_bound(all(zip),s[i-1]-'A')-zip.begin();
  dp[0] = 0;
  G = sz(zip);
  for(int i=1;i<=n;i++) pos[ar[i]].push_back(i);

  calc();
  
  //cout << Get_Cost(0,ar[2],(1<<ar[1])) << '\n';

  for(int mask=1;mask<(1LL<<G);mask++){
  	for(int u=0;u<G;u++){
  	  if(!(mask>>u&1)) continue;
  	  int l = -1, r = sz(pos[u]) - 1;
  	  while(r-l>4){
        int mid = (l + r) / 2;
        if( Get_Cost(mid,u,mask^(1<<u)) > Get_Cost(mid+1,u,mask^(1<<u)) )
           l=mid;
        else
           r=mid;
  	  } 

  	  // cout << mask << ' ' << u << ' ' << l+1 << '\n';
  	  for(int ll=l;ll<=r;ll++)
  	   dp[mask] = min(dp[mask], dp[mask^(1<<u)] + Get_Cost(ll,u,mask^(1<<u)) );
  	}
  }

  cout << dp[(1LL<<G)-1] << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  cout << fixed << setprecision(16);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1112 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 856 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 856 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 860 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 1016 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 3860 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 4112 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 4372 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 5 ms 4116 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 860 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 860 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 1372 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 1372 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 1440 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 1372 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 1372 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 1248 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 1372 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 1372 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 1372 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 1372 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 1372 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 1372 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 1372 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 1372 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 1372 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 860 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 1 ms 860 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 1 ms 1372 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 1 ms 1372 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 1 ms 1440 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 1 ms 1372 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 1 ms 1372 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 1 ms 1248 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 1 ms 1372 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 1 ms 1372 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 1 ms 1372 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 1 ms 1372 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 1 ms 1372 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 1 ms 1372 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 1 ms 1372 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 1 ms 1372 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 1 ms 1372 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 1 ms 860 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 1 ms 860 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 1 ms 1372 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 1 ms 1372 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 1 ms 1372 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 1 ms 1372 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 1 ms 1372 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 1 ms 1372 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 1 ms 1372 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 1 ms 1372 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 1 ms 1372 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 1 ms 1512 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 1 ms 1372 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 1 ms 1372 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 1 ms 1372 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 1 ms 1372 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 1 ms 1372 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 1 ms 1368 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 1 ms 1372 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 14 ms 16264 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 12 ms 16216 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 9 ms 16476 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 12 ms 16388 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 11 ms 15960 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 12 ms 15964 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 12 ms 15964 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 12 ms 16172 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 12 ms 15964 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 11 ms 16016 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 1112 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 1 ms 856 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 1 ms 856 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 1 ms 860 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 1 ms 1016 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 4 ms 3860 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 4 ms 4112 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 4 ms 4372 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 5 ms 4116 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 1 ms 860 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 1 ms 860 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 1 ms 1372 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 1 ms 1372 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 1 ms 1440 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 1 ms 1372 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 1 ms 1372 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 1 ms 1248 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 1 ms 1372 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 1 ms 1372 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 1 ms 1372 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 1 ms 1372 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 1 ms 1372 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 1 ms 1372 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 1 ms 1372 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 1 ms 1372 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 1 ms 1372 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 1 ms 860 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 1 ms 860 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 1 ms 1372 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 1 ms 1372 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 1 ms 1372 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 1 ms 1372 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 1 ms 1372 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 1 ms 1372 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 1 ms 1372 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 1 ms 1372 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 1 ms 1372 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 1 ms 1512 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 1 ms 1372 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 1 ms 1372 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 1 ms 1372 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 1 ms 1372 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 1 ms 1372 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 1 ms 1368 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 1 ms 1372 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 14 ms 16264 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 12 ms 16216 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 9 ms 16476 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 12 ms 16388 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 11 ms 15960 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 12 ms 15964 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 12 ms 15964 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 12 ms 16172 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 12 ms 15964 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 11 ms 16016 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 1 ms 1116 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 52 ms 3420 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 1 ms 856 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 1 ms 860 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 1 ms 860 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 1 ms 860 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 1 ms 860 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 4 ms 3752 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 4 ms 4116 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 4 ms 4116 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 5 ms 4120 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 1 ms 864 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 1 ms 860 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 1 ms 1372 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 1 ms 1372 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 1 ms 1372 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 2 ms 1372 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 1 ms 1368 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 1 ms 1372 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 1 ms 1372 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 1 ms 1372 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 1 ms 1372 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 1 ms 1372 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 1 ms 1372 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 1 ms 1512 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 1 ms 1372 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 1 ms 1372 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 1 ms 1372 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 1 ms 1372 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 1 ms 1368 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 13 ms 16220 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 11 ms 16220 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 9 ms 16476 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 12 ms 16216 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 11 ms 15964 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 12 ms 15960 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 11 ms 15964 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 10 ms 15964 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 11 ms 15964 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 10 ms 15964 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 539 ms 332648 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 32 ms 3164 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 440 ms 332556 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 177 ms 332484 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 36 ms 3420 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 480 ms 332556 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 547 ms 332580 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 548 ms 332552 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 551 ms 332552 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 540 ms 332552 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 509 ms 332556 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 559 ms 332552 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 313 ms 288780 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 557 ms 332808 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'