oj.uz

Submission #711192

# Submission time Handle Problem Language Result Execution time Memory
711192 2023-03-16T09:43:03 Z rrrr10000 Boarding Passes (BOI22_passes) C++14
100 / 100
 169 ms 48892 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);
        }
    }
    ll ans=dp.back();
    if(ans%2==0)out(ans/2);
    else{
        cout<<ans/2;
        out(".5");
    }
}

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 10 ms 980 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 4 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 7 ms 568 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 6 ms 532 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 9 ms 1060 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 39 ms 38268 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 44 ms 45544 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 47 ms 48460 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 49 ms 48528 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 8 ms 620 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 33 ms 596 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 22 ms 596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 16 ms 596 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 14 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 24 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 20 ms 584 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 34 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 26 ms 584 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 24 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 23 ms 580 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 22 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 21 ms 580 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 21 ms 580 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 22 ms 580 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 8 ms 620 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 33 ms 596 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 22 ms 596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 16 ms 596 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 14 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 24 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 20 ms 584 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 34 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 26 ms 584 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 24 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 23 ms 580 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 22 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 21 ms 580 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 21 ms 580 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 22 ms 580 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 9 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 8 ms 596 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 36 ms 596 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 25 ms 596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 20 ms 624 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 14 ms 572 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 580 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 23 ms 588 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 23 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 21 ms 588 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 21 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 25 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 25 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 22 ms 588 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 25 ms 580 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 16 ms 5428 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 14 ms 5428 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 61 ms 5484 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 59 ms 5428 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 28 ms 5448 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 54 ms 5368 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 60 ms 5364 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 60 ms 5304 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 57 ms 5304 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 62 ms 5348 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 65 ms 5276 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 78 ms 5348 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 980 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 4 ms 468 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 7 ms 568 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 6 ms 532 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 9 ms 1060 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 39 ms 38268 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Correct 44 ms 45544 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
8 Correct 47 ms 48460 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
9 Correct 49 ms 48528 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
10 Correct 12 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
11 Correct 8 ms 620 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
12 Correct 33 ms 596 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
13 Correct 22 ms 596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
14 Correct 16 ms 596 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
15 Correct 14 ms 468 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
16 Correct 24 ms 596 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
17 Correct 20 ms 584 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 34 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
20 Correct 26 ms 584 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
21 Correct 24 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
22 Correct 23 ms 580 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
23 Correct 22 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
24 Correct 21 ms 580 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
25 Correct 21 ms 580 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
26 Correct 22 ms 580 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
27 Correct 9 ms 468 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
28 Correct 8 ms 596 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
29 Correct 36 ms 596 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
30 Correct 25 ms 596 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
31 Correct 20 ms 624 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
32 Correct 14 ms 572 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 580 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
35 Correct 23 ms 588 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
36 Correct 23 ms 468 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
37 Correct 21 ms 588 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
38 Correct 21 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
39 Correct 25 ms 468 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
40 Correct 25 ms 596 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
41 Correct 22 ms 588 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
42 Correct 25 ms 580 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 16 ms 5428 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
45 Correct 14 ms 5428 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
46 Correct 61 ms 5484 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
47 Correct 59 ms 5428 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
48 Correct 28 ms 5448 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
49 Correct 54 ms 5368 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
50 Correct 60 ms 5364 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
51 Correct 60 ms 5304 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
52 Correct 57 ms 5304 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
53 Correct 62 ms 5348 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
54 Correct 65 ms 5276 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
55 Correct 78 ms 5348 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
56 Correct 15 ms 544 KB found '7.5000000000', expected '7.5000000000', error '0.0000000000'
57 Correct 38 ms 572 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
58 Correct 13 ms 980 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
59 Correct 5 ms 556 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
60 Correct 6 ms 584 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 9 ms 980 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
63 Correct 40 ms 38356 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
64 Correct 44 ms 45704 KB found '1100977812.5000000000', expected '1100977812.5000000000', error '0.0000000000'
65 Correct 46 ms 48584 KB found '1249950000.5000000000', expected '1249950000.5000000000', error '0.0000000000'
66 Correct 46 ms 48644 KB found '1249975000.0000000000', expected '1249975000.0000000000', error '0.0000000000'
67 Correct 10 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 31 ms 604 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
70 Correct 22 ms 620 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
71 Correct 18 ms 596 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
72 Correct 14 ms 584 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
73 Correct 25 ms 560 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
74 Correct 24 ms 592 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
75 Correct 23 ms 468 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
76 Correct 24 ms 576 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
77 Correct 23 ms 596 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
78 Correct 23 ms 468 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
79 Correct 24 ms 584 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
80 Correct 22 ms 468 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
81 Correct 21 ms 468 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
82 Correct 24 ms 468 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
83 Correct 24 ms 596 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
84 Correct 13 ms 5376 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
85 Correct 14 ms 5440 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
86 Correct 59 ms 5484 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
87 Correct 66 ms 5396 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
88 Correct 27 ms 5404 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
89 Correct 56 ms 5372 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
90 Correct 63 ms 5372 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
91 Correct 76 ms 5372 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
92 Correct 58 ms 5360 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
93 Correct 57 ms 5344 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
94 Correct 56 ms 5384 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
95 Correct 59 ms 5352 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'
96 Correct 160 ms 48800 KB found '1239972790.0000000000', expected '1239972790.0000000000', error '0.0000000000'
97 Correct 36 ms 592 KB found '128.0000000000', expected '128.0000000000', error '0.0000000000'
98 Correct 139 ms 48572 KB found '161053893.0000000000', expected '161053893.0000000000', error '0.0000000000'
99 Correct 71 ms 48780 KB found '1249625032.0000000000', expected '1249625032.0000000000', error '0.0000000000'
100 Correct 27 ms 568 KB found '10.5000000000', expected '10.5000000000', error '0.0000000000'
101 Correct 136 ms 48804 KB found '1095334900.0000000000', expected '1095334900.0000000000', error '0.0000000000'
102 Correct 148 ms 48892 KB found '1249723731.0000000000', expected '1249723731.0000000000', error '0.0000000000'
103 Correct 159 ms 48680 KB found '1239994164.5000000000', expected '1239994164.5000000000', error '0.0000000000'
104 Correct 169 ms 48832 KB found '1239994234.5000000000', expected '1239994234.5000000000', error '0.0000000000'
105 Correct 134 ms 48600 KB found '1239994121.0000000000', expected '1239994121.0000000000', error '0.0000000000'
106 Correct 136 ms 48676 KB found '1239994009.0000000000', expected '1239994009.0000000000', error '0.0000000000'
107 Correct 147 ms 48628 KB found '1239993860.5000000000', expected '1239993860.5000000000', error '0.0000000000'
108 Correct 141 ms 48652 KB found '1237107336.5000000000', expected '1237107336.5000000000', error '0.0000000000'
109 Correct 138 ms 48828 KB found '1239994062.5000000000', expected '1239994062.5000000000', error '0.0000000000'