oj.uz

Submission #254084

# Submission time Handle Problem Language Result Execution time Memory
254084 2020-07-29T10:46:46 Z ne4eHbKa Domino (COCI15_domino) C++17
30 / 160
 1064 ms 99208 KB 
//{ <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(20, min(4 * k, 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

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):
     ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 7668 KB Output is correct
2 Correct 40 ms 7668 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1022 ms 81984 KB Output is correct
2 Correct 656 ms 81952 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 574 ms 78144 KB Output is correct
2 Incorrect 397 ms 78108 KB Output isn't correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 24932 KB Output is correct
2 Incorrect 164 ms 24932 KB Output isn't correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1025 ms 93144 KB Output is correct
2 Incorrect 681 ms 93016 KB Output isn't correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 17152 KB Output is correct
2 Incorrect 22 ms 17152 KB Output isn't correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1064 ms 95192 KB Output is correct
2 Incorrect 683 ms 95192 KB Output isn't correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 19584 KB Output is correct
2 Incorrect 24 ms 19584 KB Output isn't correct

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 18816 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1060 ms 97448 KB Output is correct
2 Incorrect 702 ms 97392 KB Output isn't correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 21376 KB Output is correct
2 Incorrect 26 ms 21376 KB Output isn't correct

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 281 ms 44480 KB Output is correct
2 Incorrect 185 ms 44480 KB Output isn't correct

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 20864 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #16
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1050 ms 99192 KB Output is correct
2 Incorrect 773 ms 99208 KB Output isn't correct