Submission #379582

#	Time	Username	Problem	Language	Result	Execution time	Memory
379582		FEDIKUS	Vještica (COCI16_vjestica)	C++17	160 / 160	338 ms	1516 KiB

vjestica

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xx first
#define yy second
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,int) sort(a.begin(),a.end(),greater<int>())
#define lb(a,x) lower_bound(a.begin(),a.end(),x)
#define up(a,x) upper_bound(a.begin(),a.end(),x)
#define fnd(a,x) find(a.begin(),a.end(),x)
#define vstart auto startt=chrono::system_clock::now()
#define vend auto endd=chrono::system_clock::now()
#define vvreme chrono::duration<double> vremee=endd-startt
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,int> pint;
typedef string str;

int dp[(1<<16)];
int n;
int niz[16][26];
int ima[17];

int main()
{
    // valjda ce proci iz 100 pokusaja i posle 200 optimizacija
    ios;
    cin>>n;
    for(int i=0;i<n;i++){
        str a;
        cin>>a;
        for(char j:a) niz[i][j-'a']++;
    }
    //if(n>13) return -1;
    for(int mask=1;mask<(1<<n);mask++){
    	int ret=0;
    	if(__builtin_popcount(mask)==1){
        	int sta=-1;
	        for(int i=0;i<n;i++) if(mask&(1<<i)) sta=i;
    	    for(int i=0;i<26;i++){
	            ret+=niz[sta][i];
        	}
        	dp[mask]=ret;
        	continue;
        	//cout<<bitset<5>(mask)<<" "<<ret<<"\n";
	    }
	    int bitovi=__builtin_popcount(mask);
	    int tren=0;
	    for(int j=0;j<n;j++){
	    	if(mask&(1<<j)){
	    		//cout<<j<<"\n";
    			ima[tren]=j;
    			tren++;
	    	}
    	}
    	for(int i=0;i<26;i++){
        	int koliko=1e6+1;
        	for(int j=0;j<bitovi;j++){
        	    koliko=min(koliko,niz[ima[j]][i]);
    	    }
	        ret+=koliko;
    	}
    	//cout<<"    "<<bitset<5>(mask)<<" "<<ret<<" "<<"\n";
    	//cout<<bitovi<<" "; for(int i:ima) cout<<i<<" "; cout<<"\n";
    	int sta=1e6+1;
    	if(bitovi==2){
            sta=min(sta,dp[(1<<ima[bitovi-2])]+dp[(1<<ima[bitovi-1])]-ret);
    	}
    	for(int i=0;i<(1<<(bitovi-2));i++){
        	int nova1=(1<<ima[bitovi-1]);
        	//cout<<nova1<<"\n";
        	int nova2=0;
        	for(int j=0;j<bitovi-2;j++){
            	if(i&(1<<j)){
                	nova1+=(1<<ima[j]);
            	}else{
                	nova2+=(1<<ima[j]);
            	}
        	}
        	if(i==(1<<bitovi-2)-1){
                sta=min(sta,dp[nova1]+dp[nova2+(1<<ima[bitovi-2])]-ret);
        	}else{
                sta=min(sta,dp[nova1+(1<<ima[bitovi-2])]+dp[nova2]-ret);
                sta=min(sta,dp[nova1]+dp[nova2+(1<<ima[bitovi-2])]-ret);
        	}
        	//cout<<"  "<<bitset<5>(mask)<<" "<<bitset<5>(nova1)<<" "<<bitset<5>(nova2)<<"\n";
    	}
    	//cout<<bitset<5>(mask)<<" "<<sta<<"\n";
    	dp[mask]=sta;
    }
    cout<<dp[(1<<n)-1]+1;
    return 0;
}

Compilation message (stderr)

vjestica.cpp: In function 'int main()':
vjestica.cpp:87:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   87 |          if(i==(1<<bitovi-2)-1){
      |                    ~~~~~~^~

• Subtask 1: 160 / 160