oj.uz

Submission #133428

# Submission time Handle Problem Language Result Execution time Memory
133428 2019-07-20T15:26:48 Z forelax Vještica (COCI16_vjestica) C++14
128 / 160
 90 ms 1144 KB 
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> gl(n);
    vector<vector<int> > v(n,vector<int> (26));
    for(int i = 0 ; i < n ; i ++){
        string g;
        cin>>g;
        gl[i]=g.length();
        for(int j = 0 ; j < g.length() ; j ++)
            v[i][g[j]-'a']++;
    }
    vector<int> dp(1<<n);
    dp[0]=1;
    for(int b = 1 ; b < dp.size() ; b ++){
        vector<int> g;
        vector<int> minTable(26,1e9);
        for(int i = 0 ; i < n ; i ++)
            if(b&(1<<i)){
                g.push_back(i);
                for(int j = 0 ; j < 26 ; j ++)
                    minTable[j]=min(minTable[j],v[i][j]);
            }
        if(g.size()==1){
//            cout<<dp[b-1]<<endl;
            dp[b]=gl[g[0]]+1;
            continue;
        }
        int ml=0;
        for(int i = 0 ; i < 26 ; i ++)
            ml+=minTable[i];
        dp[b]=1e9;
        for(int i = 0 ; i < 26 ; i ++){
            int f=0,s=0;
            for(int j = 0 ; j < g.size() ; j ++){
                if(v[g[j]][i]==minTable[i])
                    f+=(1<<g[j]);
                else
                    s+=(1<<g[j]);
            }
            if(f==0||s==0)continue;
//            cout<<b<<" "<<i<<" "<<f<<" "<<s<<endl;
            dp[b]=min(dp[b],dp[f]+dp[s]-ml-1);
        }
        if(dp[b]==1e9)
            dp[b]=ml+1;
//        cout<<dp[b-1]<<endl;
    }
    cout<<dp[-1+(1<<n)];
}



/***

2
a
ab
abc

**/

Compilation message

vjestica.cpp: In function 'int main()':
vjestica.cpp:12:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0 ; j < g.length() ; j ++)
                         ~~^~~~~~~~~~~~
vjestica.cpp:17:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int b = 1 ; b < dp.size() ; b ++){
                     ~~^~~~~~~~~~~
vjestica.cpp:37:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j = 0 ; j < g.size() ; j ++){
                             ~~^~~~~~~~~~

Subtask #1
128.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Incorrect 3 ms 376 KB Output isn't correct
4 Incorrect 64 ms 632 KB Output isn't correct
5 Correct 67 ms 760 KB Output is correct
6 Correct 77 ms 888 KB Output is correct
7 Correct 86 ms 1144 KB Output is correct
8 Correct 90 ms 1144 KB Output is correct
9 Correct 89 ms 1020 KB Output is correct
10 Correct 88 ms 1116 KB Output is correct