oj.uz

답안 #944372

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
944372 2024-03-12T16:11:14 Z PaDi Kronican (COCI16_kronican) C++14
0 / 100
 3 ms 4700 KB 
#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 = 1<<22;
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 = (1<<N)-1;
        dp[LIM] = 0;
        for(int mask = (1<<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 + 1<<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

kronican.cpp: In function 'int main()':
kronican.cpp:56:52: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   56 |                                 int PREMASK = mask + 1<<j;
      |                                               ~~~~~^~~
kronican.cpp:52:29: warning: unused variable 'SUFMASK' [-Wunused-variable]
   52 |                         int SUFMASK = (mask)^(1<<i);
      |                             ^~~~~~~

Subtask #1
0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Runtime error 1 ms 600 KB Execution killed with signal 11
6 Runtime error 1 ms 600 KB Execution killed with signal 11
7 Runtime error 3 ms 4700 KB Execution killed with signal 11
8 Runtime error 3 ms 4700 KB Execution killed with signal 11
9 Runtime error 2 ms 4700 KB Execution killed with signal 11
10 Runtime error 3 ms 4700 KB Execution killed with signal 11