oj.uz

Submission #944369

# Submission time Handle Problem Language Result Execution time Memory
944369 2024-03-12T16:08:26 Z PaDi Kronican (COCI16_kronican) C++14
90 / 100
 2000 ms 4688 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 = 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(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';
}

Compilation message

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 16 ms 516 KB Output is correct
6 Correct 36 ms 344 KB Output is correct
7 Correct 86 ms 2580 KB Output is correct
8 Correct 206 ms 2488 KB Output is correct
9 Execution timed out 2016 ms 4688 KB Time limit exceeded
10 Correct 254 ms 4540 KB Output is correct