oj.uz

Submission #711199

# Submission time Handle Problem Language Result Execution time Memory
711199 2023-03-16T09:45:56 Z rrrr10000 Boarding Passes (BOI22_passes) C++14
100 / 100
 210 ms 48788 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<P> vp;
typedef vector<vp> vvp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
template<class T> void outvv(T v){for(auto x:v)outv(x);}
template<class T> void outvp(T v){rep(i,v.size()){cout<<'('<<v[i].fi<<','<<v[i].se<<')';}cout<<endl;}
template<class T> void outvvp(T v){for(auto x:v)outvp(x);}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}

int main(){
    string str;cin>>str;
    ll n=15,m=str.size();
    vvi g(n);
    rep(i,m)g[str[i]-'A'].pb(i);
    vvp cost(n,vp(m));
    rep(i,n){
        ll cnt=0;
        rep(j,m){
            if(str[j]-'A'==i)cnt++;
            cost[i][j]=P(cnt*2,(g[i].size()-cnt)*2);
        }
    }
    vvp rui=cost;
    rep(i,n)rep(j,n)rep(k,g[j].size()-1)rui[i][g[j][k+1]].fi+=rui[i][g[j][k]].fi;
    rep(i,n)rep(j,n)for(ll k=g[j].size()-1;k>0;k--)rui[i][g[j][k-1]].se+=rui[i][g[j][k]].se;
    vi dp(1<<n,1001001001001001001);
    dp[0]=0;
    rep(bit,1<<n){
        rep(i,n)if(!(bit>>i&1)){
            ll ok=-1,ng=g[i].size();
            while(ng-ok>1){
                ll md=(ok+ng)/2;
                ll cost0=md,cost1=g[i].size()-1-md;
                rep(j,n)if(bit>>j&1){
                    cost0+=cost[j][g[i][md]].fi;
                    cost1+=cost[j][g[i][md]].se;
                }
                if(cost0<cost1)ok=md;
                else ng=md;
            }
            ll ncost=dp[bit]+(ok+1)*ok/2+(g[i].size()-ok-1)*(g[i].size()-ok-2)/2;
            if(ok!=-1){
                rep(j,n)if(bit>>j&1)ncost+=rui[j][g[i][ok]].fi;
            }
            if(ng!=g[i].size()){
                rep(j,n)if(bit>>j&1)ncost+=rui[j][g[i][ng]].se;
            }
            chmin(dp[bit|(1<<i)],ncost);
        }
    }
    double ans=dp.back()/2.0;
  cout<<fixed<<setprecision(15);
    out(ans);
}

Compilation message

passes.cpp: In function 'int main()':
passes.cpp:58:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             if(ng!=g[i].size()){
      |                ~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 980 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 5 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 6 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 6 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 10 ms 980 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 39 ms 38264 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 46 ms 45588 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 47 ms 48508 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 51 ms 48544 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 8 ms 596 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 28 ms 616 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 23 ms 628 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 17 ms 620 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 14 ms 572 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 27 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 26 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 22 ms 584 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 23 ms 564 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 21 ms 468 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 28 ms 584 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 26 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 29 ms 572 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 22 ms 584 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 22 ms 588 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 24 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 8 ms 596 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 28 ms 616 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 23 ms 628 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 17 ms 620 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 14 ms 572 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 27 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 26 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 22 ms 584 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 23 ms 564 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 21 ms 468 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 28 ms 584 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 26 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 29 ms 572 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 22 ms 584 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 22 ms 588 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 24 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 10 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 8 ms 620 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 31 ms 596 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 25 ms 604 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 19 ms 620 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 14 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 25 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 20 ms 568 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 23 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 24 ms 564 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 21 ms 580 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 23 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 25 ms 580 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 30 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 23 ms 580 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 21 ms 584 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 22 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 13 ms 5428 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 13 ms 5432 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 62 ms 5428 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 54 ms 5408 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 28 ms 5428 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 65 ms 5356 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 61 ms 5352 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 57 ms 5348 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 59 ms 5344 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 62 ms 5332 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 82 ms 5348 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 82 ms 5304 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 980 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 5 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 6 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 6 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 10 ms 980 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 39 ms 38264 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 46 ms 45588 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 47 ms 48508 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 51 ms 48544 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 10 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 8 ms 596 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 28 ms 616 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 23 ms 628 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 17 ms 620 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 14 ms 572 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 27 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 26 ms 468 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
18 Correct 22 ms 584 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
19 Correct 23 ms 564 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 21 ms 468 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 28 ms 584 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 26 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 29 ms 572 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 22 ms 584 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 22 ms 588 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 24 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 10 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 8 ms 620 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 31 ms 596 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 25 ms 604 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 19 ms 620 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 14 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
33 Correct 25 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
34 Correct 20 ms 568 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 23 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 24 ms 564 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 21 ms 580 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 23 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 25 ms 580 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 30 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 23 ms 580 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 21 ms 584 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
43 Correct 22 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
44 Correct 13 ms 5428 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 13 ms 5432 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 62 ms 5428 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 54 ms 5408 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 28 ms 5428 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 65 ms 5356 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 61 ms 5352 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 57 ms 5348 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 59 ms 5344 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 62 ms 5332 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 82 ms 5348 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 82 ms 5304 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 15 ms 576 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 39 ms 564 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 12 ms 980 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 5 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 7 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
61 Correct 7 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
62 Correct 15 ms 980 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 48 ms 38320 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 66 ms 45496 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 52 ms 48456 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 55 ms 48556 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 13 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
68 Correct 8 ms 596 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
69 Correct 30 ms 596 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 25 ms 616 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 19 ms 624 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 15 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 24 ms 612 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 21 ms 580 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 22 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 22 ms 588 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 25 ms 588 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 22 ms 580 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 22 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 23 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 25 ms 588 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 22 ms 588 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 23 ms 468 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 13 ms 5428 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 13 ms 5428 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 57 ms 5388 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 65 ms 5300 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 29 ms 5300 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 57 ms 5304 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 60 ms 5304 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 62 ms 5356 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 58 ms 5344 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 66 ms 5304 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 66 ms 5344 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 66 ms 5304 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 157 ms 48700 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 37 ms 596 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 139 ms 48592 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 70 ms 48544 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 28 ms 468 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 132 ms 48700 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 144 ms 48788 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 147 ms 48572 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 149 ms 48660 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 187 ms 48612 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 173 ms 48624 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 208 ms 48628 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 158 ms 48548 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 210 ms 48728 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'