oj.uz

Submission #245932

# Submission time Handle Problem Language Result Execution time Memory
245932 2020-07-07T20:47:42 Z ScarletS Vještica (COCI16_vjestica) C++17
160 / 160
 106 ms 1272 KB 
#include <bits/stdc++.h>
#define ll long long
#define sz(x) (int)(x).size()
using namespace std;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//uniform_int_distribution<int>(1000,10000)(rng)

int amounts[16][26],lengths[16],dp[1<<16],cur[26];

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,p,x;
    cin>>n;
    string s;
    for (int i=0;i<n;++i)
    {
        cin>>s;
        for (auto c : s)
            ++amounts[i][c-'a'];
        lengths[i]=sz(s);
    }
    p=(1<<(n));
    for (int i=1;i<p;++i)
    {
        if (__builtin_popcount(i)==1)
        {
            for (int j=0;j<n;++j)
                if ((1<<j)==i)
                    dp[i]=lengths[j];
            //cout<<"dp["<<i<<"] = "<<dp[i]<<"\n";
            continue;
        }
        dp[i]=1000000;
        for (int j=0;j<26;++j)
            cur[j]=1000000;
        for (int j=0;j<n;++j)
            if ((1<<j)&i)
                for (int k=0;k<26;++k)
                    cur[k]=min(cur[k],amounts[j][k]);
        x=0;
        for (int j=0;j<26;++j)
            x+=cur[j];
        for (int j=(i-1)&i;j;j=(j-1)&i)
            dp[i]=min(dp[i],dp[j]+dp[i-j]-x);
        //cout<<"shared = "<<x<<"\n";
        //cout<<"dp["<<i<<"] = "<<dp[i]<<"\n";
    }
    cout<<dp[p-1]+1;
    return 0;
}

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 102 ms 632 KB Output is correct
5 Correct 102 ms 760 KB Output is correct
6 Correct 100 ms 888 KB Output is correct
7 Correct 101 ms 1188 KB Output is correct
8 Correct 106 ms 1144 KB Output is correct
9 Correct 106 ms 1144 KB Output is correct
10 Correct 103 ms 1272 KB Output is correct