oj.uz

Submission #133434

# Submission time Handle Problem Language Result Execution time Memory
133434 2019-07-20T16:40:25 Z forelax Vještica (COCI16_vjestica) C++14
160 / 160
 153 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){
            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 sb=b&-b ; b-sb ; sb=b&(sb-b)){
            int dp1=dp[sb];
            int dp2=dp[b^sb];
            dp[b]=min(dp[b],dp1+dp2-ml-1);
        }
    }
    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 ++){
                     ~~^~~~~~~~~~~

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 256 KB Output is correct
2 Correct 3 ms 256 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 123 ms 632 KB Output is correct
5 Correct 128 ms 760 KB Output is correct
6 Correct 138 ms 888 KB Output is correct
7 Correct 148 ms 1016 KB Output is correct
8 Correct 153 ms 1144 KB Output is correct
9 Correct 151 ms 1016 KB Output is correct
10 Correct 149 ms 1016 KB Output is correct