Submission #254091

#TimeUsernameProblemLanguageResultExecution timeMemory
254091ne4eHbKaDomino (COCI15_domino)C++17
80 / 160
1369 ms407312 KiB
//{ <defines> #include <bits/stdc++.h> using namespace std; //#pragma comment(linker, "/stack:200000000") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") //#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,-O3") #define fr(i, n) for(int i = 0; i < n; ++i) #define fo(n) fr(i, n) #define re return #define ef else if #define ifn(x) if(!(x)) #define _ << ' ' << #define ft first #define sd second #define ve vector #define pb push_back #define eb emplace_back #define sz(x) int((x).size()) #define bnd(x) x.begin(), x.end() #define clr(x, y) memset((x), (y), sizeof (x)) typedef long long ll; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; typedef ve<int> vi; inline ll time() {re chrono :: system_clock().now().time_since_epoch().count();} mt19937 rnd(time()); mt19937_64 RND(time()); template<typename t> inline void umin(t &a, t b) {a = min(a, b);} template<typename t> inline void umax(t &a, t b) {a = max(a, b);} int md = 998244353; inline int m_add(int&a, int b) {a += b; if(a < 0) a += md; if(a >= md) a -= md; re a;} inline int m_sum(int a, int b) {a += b; if(a < 0) a += md; if(a >= md) a -= md; re a;} inline int m_mul(int&a, int b) {re a = 1ll * a * b % md;} inline int m_prod(int a, int b) {re 1ll * a * b % md;} int m_bpow(ll A, ll b) { int a = A % md; ll ans = 1; for(ll p = 1ll << 63 - __builtin_clzll(b); p; p >>= 1) { (ans *= ans) %= md; if(p & b) (ans *= a) %= md; } re ans; } //const ld pi = arg(complex<ld>(-1, 0)); //const ld pi2 = pi + pi; const int oo = 2e9; const ll OO = 4e18; //} </defines> const int N = 2e3 + 5; int n, k, a[N][N]; short ans; struct dom { short x, y, v; bool h; dom(int x, int y, bool h): x(x), y(y), h(h), v(a[x][y] + a[x + !h][y + h]) {} bool operator<(const dom &f) const {re v > f.v;} bool operator*(const dom &f) const { pii lt = { x, y}, rt = { x, y}; h ? rt.sd++ : rt.ft++; pii lf = {f.x, f.y}, rf = {f.x, f.y}; f.h ? rf.sd++ : rf.ft++; return lt == lf || rt == rf || lt == rf || rt == lf; } }; void solve() { cin >> n >> k; ll s = 0; fo(n) fr(j, n) cin >> a[i][j], s += a[i][j]; ans = 0; vector<dom> d; fo(n) fr(j, n - 1) d.emplace_back(i, j, true); fo(n - 1) fr(j, n) d.emplace_back(i, j, false); sort(bnd(d)); int t = min(24, sz(d)); vi ms(t); fo(t) { int u = 0; fr(j, t) if(d[i] * d[j]) u |= 1 << j; ms[i] = u; } vector< vector<short> > dp(k + 1, vector<short>(1 << t, -1)); dp[0][0] = 0; ans = 0; for(int i = 0; i <= k; ++i) { if(i == k) { for(int j = 0; j < 1 << t; ++j) umax(ans, dp[i][j]); } else { for(int j = 0; j < 1 << t; ++j) { if(dp[i][j] < 0) continue; for(int f = 0; f < t; ++f) { if(j >> f & 1) continue; umax<short>(dp[i + 1][j | ms[f]], dp[i][j] + d[f].v); } } } } cout << s - ans << endl; } int main() { #ifdef _LOCAL freopen("in.txt", "r", stdin); int tests; cin >> tests; for(int test = 1; test <= tests; ++test) { cerr << "case #" << test << endl; solve(); cerr << endl; } #else // freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0); solve(); #endif return 0; }

Compilation message (stderr)

domino.cpp: In function 'int m_bpow(ll, ll)':
domino.cpp:51:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
     for(ll p = 1ll << 63 - __builtin_clzll(b); p; p >>= 1) {
                       ~~~^~~~~~~~~~~~~~~~~~~~
domino.cpp: In constructor 'dom::dom(int, int, bool)':
domino.cpp:71:10: warning: 'dom::h' will be initialized after [-Wreorder]
     bool h;
          ^
domino.cpp:70:17: warning:   'short int dom::v' [-Wreorder]
     short x, y, v;
                 ^
domino.cpp:72:5: warning:   when initialized here [-Wreorder]
     dom(int x, int y, bool h):
     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...