제출 #944370

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
944370		PaDi	Kronican (COCI16_kronican)	C++14	90 / 100	2033 ms	4696 KiB

kronican

#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC target("avx","sse2")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#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 >= 1 ; mask--){
            if(mask != LIM) dp[mask] = 1e9;
            if(__builtin_popcount(mask) < K) continue;
            //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';
}

컴파일 시 표준 에러 (stderr) 메시지

kronican.cpp: In function 'int main()':
kronican.cpp:52:29: warning: unused variable 'SUFMASK' [-Wunused-variable]
   52 |                         int SUFMASK = (mask)^(1<<i);
      |                             ^~~~~~~

• Subtask 1: 90 / 100