oj.uz

Submission #712404

# Submission time Handle Problem Language Result Execution time Memory
712404 2023-03-18T18:25:14 Z Ahmed57 Vještica (COCI16_vjestica) C++14
0 / 160
 20 ms 1368 KB 
#include<bits/stdc++.h>
using namespace std;
long long dp[(1<<16)];
long long c[16][26] = {0};
long long com[(1<<16)];
long long solve(int mask){
    if(dp[mask]!=-1)return dp[mask];
    if(__builtin_popcount(mask)==1)return com[mask];
    long long ans = 1e18;
    for(long long s = mask&(mask-1);s;s=s&(s-1)){
        ans = min(ans,solve(s)+solve(mask^s)-com[mask]);
    }
    return dp[mask] = ans;
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n;cin>>n;
    for(int i = 0;i<n;i++){
        string s;cin>>s;
        for(int j = 0;j<s.size();j++){
            c[i][s[j]-'a']++;
        }
    }
    memset(dp,-1,sizeof dp);
    for(int mask = 1;mask<(1<<n);mask++){
        long long ch[26] = {0};
        for(int j = 0;j<26;j++)ch[j] = 1e9;
        for(int j = 0;j<n;j++){
            if(mask&(1<<j)){
            for(int k = 0;k<26;k++)ch[k]= min(ch[k],c[j][k]);
            }
        }
        for(int j = 0;j<26;j++){
            com[mask]+=ch[j];
        }
    }
    cout<<solve((1<<n)-1)+1<<"\n";
}

Compilation message

vjestica.cpp: In function 'int main()':
vjestica.cpp:20:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for(int j = 0;j<s.size();j++){
      |                       ~^~~~~~~~~

Subtask #1
0 / 160.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 724 KB Output isn't correct
2 Incorrect 1 ms 724 KB Output isn't correct
3 Incorrect 1 ms 724 KB Output isn't correct
4 Incorrect 19 ms 1236 KB Output isn't correct
5 Incorrect 17 ms 1364 KB Output isn't correct
6 Incorrect 18 ms 1328 KB Output isn't correct
7 Incorrect 20 ms 1360 KB Output isn't correct
8 Incorrect 20 ms 1368 KB Output isn't correct
9 Incorrect 19 ms 1344 KB Output isn't correct
10 Incorrect 20 ms 1364 KB Output isn't correct