oj.uz

Submission #805985

# Submission time Handle Problem Language Result Execution time Memory
805985 2023-08-04T04:10:52 Z winter0101 Boarding Passes (BOI22_passes) C++14
55 / 100
 102 ms 14740 KB 
#include<bits/stdc++.h>
using namespace std;
#define all(fl) fl.begin(),fl.end()
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pli pair<long long,int>
#define gcd __gcd
#define lcm(x,y) x*y/__gcd(x,y)
#define pil pair<int,long long>
#define pll pair<long long,long long>
#define eb emplace_back
const long long inf=1e15;
const int maxn=1e5+9;
long long f[1<<15];
int a[maxn][15],b[maxn][15];
int cnt[15];
vector<int>id[15];
string s;
vector<int>bit[1<<15];
long long g(int gr,int k,int mask){
long long cost=0;
int mp=sz(id[gr]);
for (auto v:bit[mask]){
    if (mp==0)continue;
    if (k==0){
    cost+=2*b[id[gr][0]][v];
    }
    else if (k==mp){
    cost+=2*a[id[gr].back()][v];
    }
    else {
    int id1=id[gr][k-1],id2=id[gr][k];
    cost+=2*a[id1][v]+2*b[id2][v];
    }
}
cost+=k*(k-1)/2;
cost+=(mp-k)*(mp-k-1)/2;
return cost;
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("temp.INP","r",stdin);
    //freopen("temp.ANS","w",stdout);
    f[0]=0;
    cin>>s;
    int n=sz(s);
    s=" "+s;
    for1(i,1,n){
    for1(j,0,14){
    a[i][j]=cnt[j];
    }
    cnt[s[i]-'A']++;
    id[s[i]-'A'].pb(i);
    }
    memset(cnt,0,sizeof(cnt));
    for2(i,n,1){
    for1(j,0,14){
    b[i][j]=cnt[j];
    }
    cnt[s[i]-'A']++;
    }
    for1(i,0,14){
    for1(j,1,sz(id[i])-1){
    for1(k,0,14){
    a[id[i][j]][k]+=a[id[i][j-1]][k];
    }
    }
    for2(j,sz(id[i])-2,0){
    for1(k,0,14){
    b[id[i][j]][k]+=b[id[i][j+1]][k];
    }
    }
    }
    for1(i,0,(1<<15)-1){
    for1(j,0,14){
    if (i>>j&1)bit[i].pb(j);
    }
    f[i]=inf;
    }
    f[0]=0;
    for1(i,0,(1<<15)-1){
    if (f[i]>=inf)continue;
    for1(j,0,14){
    if (i>>j&1)continue;
    int l=0,r=sz(id[j]);
    while (l!=r){
        int mid=(l+r)/2;
        if (g(j,mid,i)>g(j,mid+1,i)){
            l=mid+1;
        }
        else r=mid;
    }
    f[i+(1<<j)]=min(f[i+(1<<j)],f[i]+g(j,l,i));
    }
    }
    long double answ=f[(1<<15)-1];
    answ=answ*0.5;
    cout<<setprecision(4)<<fixed<<answ;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3284 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 12 ms 3184 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 13 ms 3184 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 13 ms 3180 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 17 ms 3284 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 29 ms 12776 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Incorrect 29 ms 14740 KB 1st numbers differ - expected: '1100977812.5000000000', found: '-1046505835.5000000000', error = '1.9505240011'
8 Halted 0 ms 0 KB -

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3156 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 16 ms 3196 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 29 ms 3184 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 27 ms 3156 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 20 ms 3156 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 18 ms 3156 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 31 ms 3156 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 27 ms 3152 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 23 ms 3184 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 21 ms 3152 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 21 ms 3180 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 20 ms 3164 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 25 ms 3148 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 22 ms 3128 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 21 ms 3184 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 23 ms 3184 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 24 ms 3156 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 3156 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
2 Correct 16 ms 3196 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
3 Correct 29 ms 3184 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
4 Correct 27 ms 3156 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
5 Correct 20 ms 3156 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
6 Correct 18 ms 3156 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
7 Correct 31 ms 3156 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
8 Correct 27 ms 3152 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
9 Correct 23 ms 3184 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
10 Correct 21 ms 3152 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
11 Correct 21 ms 3180 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
12 Correct 20 ms 3164 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
13 Correct 25 ms 3148 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
14 Correct 22 ms 3128 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
15 Correct 21 ms 3184 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
16 Correct 23 ms 3184 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
17 Correct 24 ms 3156 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
18 Correct 15 ms 3120 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
19 Correct 15 ms 3156 KB found '1225.0000000000', expected '1225.0000000000', error '0.0000000000'
20 Correct 28 ms 3172 KB found '1023.0000000000', expected '1023.0000000000', error '0.0000000000'
21 Correct 30 ms 3168 KB found '294.0000000000', expected '294.0000000000', error '0.0000000000'
22 Correct 24 ms 3176 KB found '1087.0000000000', expected '1087.0000000000', error '0.0000000000'
23 Correct 21 ms 3088 KB found '1.5000000000', expected '1.5000000000', error '0.0000000000'
24 Correct 31 ms 3192 KB found '703.0000000000', expected '703.0000000000', error '0.0000000000'
25 Correct 20 ms 3156 KB found '55.5000000000', expected '55.5000000000', error '0.0000000000'
26 Correct 23 ms 3052 KB found '56.0000000000', expected '56.0000000000', error '0.0000000000'
27 Correct 21 ms 3156 KB found '45.0000000000', expected '45.0000000000', error '0.0000000000'
28 Correct 21 ms 3184 KB found '66.5000000000', expected '66.5000000000', error '0.0000000000'
29 Correct 22 ms 3092 KB found '67.0000000000', expected '67.0000000000', error '0.0000000000'
30 Correct 21 ms 3156 KB found '66.0000000000', expected '66.0000000000', error '0.0000000000'
31 Correct 22 ms 3184 KB found '47.0000000000', expected '47.0000000000', error '0.0000000000'
32 Correct 21 ms 3164 KB found '50.0000000000', expected '50.0000000000', error '0.0000000000'
33 Correct 22 ms 3156 KB found '49.0000000000', expected '49.0000000000', error '0.0000000000'
34 Correct 23 ms 3120 KB found '57.0000000000', expected '57.0000000000', error '0.0000000000'
35 Correct 21 ms 4312 KB found '12497500.0000000000', expected '12497500.0000000000', error '0.0000000000'
36 Correct 20 ms 4308 KB found '12495000.5000000000', expected '12495000.5000000000', error '0.0000000000'
37 Correct 102 ms 4416 KB found '12223392.0000000000', expected '12223392.0000000000', error '0.0000000000'
38 Correct 86 ms 4396 KB found '2372500.0000000000', expected '2372500.0000000000', error '0.0000000000'
39 Correct 27 ms 4312 KB found '12475017.5000000000', expected '12475017.5000000000', error '0.0000000000'
40 Correct 69 ms 4400 KB found '10655706.0000000000', expected '10655706.0000000000', error '0.0000000000'
41 Correct 78 ms 4404 KB found '11977895.5000000000', expected '11977895.5000000000', error '0.0000000000'
42 Correct 76 ms 4308 KB found '11977865.0000000000', expected '11977865.0000000000', error '0.0000000000'
43 Correct 85 ms 4364 KB found '11977907.5000000000', expected '11977907.5000000000', error '0.0000000000'
44 Correct 88 ms 4392 KB found '11977808.0000000000', expected '11977808.0000000000', error '0.0000000000'
45 Correct 100 ms 4404 KB found '11977791.0000000000', expected '11977791.0000000000', error '0.0000000000'
46 Correct 76 ms 4404 KB found '11977871.5000000000', expected '11977871.5000000000', error '0.0000000000'

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3284 KB found '100800.5000000000', expected '100800.5000000000', error '0.0000000000'
2 Correct 12 ms 3184 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
3 Correct 13 ms 3184 KB found '0.0000000000', expected '0.0000000000', error '-0.0000000000'
4 Correct 13 ms 3180 KB found '1.0000000000', expected '1.0000000000', error '0.0000000000'
5 Correct 17 ms 3284 KB found '124002.0000000000', expected '124002.0000000000', error '0.0000000000'
6 Correct 29 ms 12776 KB found '772893586.0000000000', expected '772893586.0000000000', error '0.0000000000'
7 Incorrect 29 ms 14740 KB 1st numbers differ - expected: '1100977812.5000000000', found: '-1046505835.5000000000', error = '1.9505240011'
8 Halted 0 ms 0 KB -