Submission #944367

#	Time	Username	Problem	Language	Result	Execution time	Memory
944367		PaDi	Kronican (COCI16_kronican)	C++14	0 / 100	6 ms	16116 KiB

kronican

#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
#define int long long
#define pb push_back
#define mp make_pair
#define READS(x); string x;cin >> x;
#define READ(x); int x;cin >> x;
#define DOUREAD(x,y); int x,y;cin >> x >> y;
#define TRIREAD(x,y,z); int x,y,z;cin >> x >> y >> z;
int N,K;
const int MAXN = 22;
const int MASK = 2e6+69;
int dp[MASK];
int C[MAXN][MAXN];
int MAXI = 1e9;
namespace sub1{
    void solve(){
        
    }
}
signed main(){fast
    cin >> N >> K;
    for(int i = 1; i <= N ; i++){
        for(int j = 1; j <= N ; j++){
            cin >> C[i][j];
        }
    }
    for(int i = 1; i <= MASK ; i++){
            dp[i] = 1e9;
        }
        int LIM = pow(2,N)-1;
        dp[LIM] = 0;
        for(int mask = pow(2,N)-1; mask >= 0 ; mask--){
            if(__builtin_popcount(mask) >= K){
                for(int i = 0 ; i < N ; i++){
                    int BIT = mask>>i&1;
                    if(BIT == 1){
                        int SUFMASK = (mask)^(1<<i);
                        for(int j = 0; j < N ; j++){
                            int TIB = mask>>j&1;
                            if(TIB == 0){
                                int PREMASK = mask + pow(2,j);
                                //if(dp[mask]+C[i+1][j+1] == 0) cout << i << " " << j << " " << mask << "LOL\n";
                                dp[mask] = min(dp[mask],dp[PREMASK]+C[j+1][i+1]);
                            }
                        }
                    }
                }
                if(__builtin_popcount(mask) == K) MAXI = min(MAXI,dp[mask]);
            }
        }
        cout << MAXI << '\n';
}

Compilation message (stderr)

kronican.cpp: In function 'int main()':
kronican.cpp:39:29: warning: unused variable 'SUFMASK' [-Wunused-variable]
   39 |                         int SUFMASK = (mask)^(1<<i);
      |                             ^~~~~~~
kronican.cpp:30:19: warning: iteration 2000068 invokes undefined behavior [-Waggressive-loop-optimizations]
   30 |             dp[i] = 1e9;
      |             ~~~~~~^~~~~
kronican.cpp:29:22: note: within this loop
   29 |     for(int i = 1; i <= MASK ; i++){
      |                    ~~^~~~~~~

• Subtask 1: 0 / 100