| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 944372 |
2024-03-12T16:11:14 Z |
PaDi |
Kronican (COCI16_kronican) |
C++14 |
|
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);
| ^~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
