oj.uz

Submission #1038902

# Submission time Handle Problem Language Result Execution time Memory
1038902 2024-07-30T08:50:43 Z vjudge1 Domino (COCI15_domino) C++17
30 / 160
 2270 ms 361964 KB 
#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second

typedef long long ll;
typedef pair<ll, ll> pii;

const ll N = 2e3 + 10, K = 8;
ll n, k, mat[N][N], exist[N][N], mark[N][N];
vector<pii> cells, my_cells;

ll dx[4] = {0, 1, 0, -1};
ll dy[4] = {1, 0, -1, 0};

bool done;

long long ans, total;

void dfs(ll i){
    if (i >= my_cells.size()){
        done = 1;
        return;
    }
    auto p = my_cells[i];
    if (mark[p.F][p.S]){
        dfs(i + 1);
        return;
    }

    mark[p.F][p.S] = 1;
    for (ll i = 0; i < 4; i ++){
        ll nx = p.F + dx[i];
        ll ny = p.S + dy[i];

        if (!exist[nx][ny]) continue;
        if (mark[nx][ny]) continue;

        mark[nx][ny] = 1;
        dfs(i + 1);        
        mark[nx][ny] = 0;
    }
    mark[p.F][p.S] = 0;
}

int main(){
    cin >> n >> k;
    for (ll i = 1; i <= n; i ++)
        for (ll j = 1; j <= n; j ++)
            cin >> mat[i][j], total += mat[i][j];

    vector<pair<ll, pair<pii, pii>>> vec;
    for (ll i = 1; i <= n; i ++){
        for (ll j = 1; j <= n; j ++){
            if (j + 1 <= n)
                vec.push_back({mat[i][j] + mat[i][j + 1], {{i, j}, {i, j + 1}}});
            if (i + 1 <= n)
                vec.push_back({mat[i][j] + mat[i + 1][j], {{i, j}, {i + 1, j}}});
        }
    }
    sort(vec.begin(), vec.end());

    ll mn = 3 * k;
    set<pii> st;
    while (vec.size() and st.size() < mn){
        st.insert((vec.back()).S.F);
        st.insert((vec.back()).S.S);
        vec.pop_back();
    }

    for (auto p : st){
        cells.push_back(p);
    }

    ans = total;
    ll sz = cells.size();
    for (ll mask = 0; mask < (1 << sz); mask ++){
        ll c = __builtin_popcount(mask);
        if (c != 2 * k) continue;

        my_cells.clear();
        long long sm = 0;
        for (ll i = 0; i < sz; i ++){
            if ((1 << i) & mask){
                my_cells.push_back(cells[i]);
                sm += mat[cells[i].F][cells[i].S];
            }
        }

        for (auto p : my_cells)
            exist[p.F][p.S] = 1;

        done = 0;
        dfs(0);

        for (auto p : my_cells)
            exist[p.F][p.S] = 0;

        if (done)
            ans = min(ans, total - sm);
    }

    cout << ans << endl;
}

Compilation message

domino.cpp: In function 'void dfs(ll)':
domino.cpp:22:11: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     if (i >= my_cells.size()){
      |         ~~^~~~~~~~~~~~~~~~~~
domino.cpp: In function 'int main()':
domino.cpp:66:37: warning: comparison of integer expressions of different signedness: 'std::set<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   66 |     while (vec.size() and st.size() < mn){
      |                           ~~~~~~~~~~^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 35232 KB Output is correct
2 Correct 82 ms 32164 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6808 KB Output is correct
2 Incorrect 2 ms 6808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1685 ms 361904 KB Output is correct
2 Incorrect 1406 ms 361724 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 1 ms 4444 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 975 ms 355528 KB Output is correct
2 Incorrect 1057 ms 355528 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 101020 KB Output is correct
2 Incorrect 412 ms 101024 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1734 ms 361884 KB Output is correct
2 Incorrect 1945 ms 361900 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6808 KB Output is correct
2 Incorrect 6 ms 6808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1707 ms 361748 KB Output is correct
2 Incorrect 1803 ms 361652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 7372 KB Output is correct
2 Incorrect 21 ms 7376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
10.0 / 10.0

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

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1743 ms 361724 KB Output is correct
2 Incorrect 2040 ms 361864 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 7236 KB Output is correct
2 Incorrect 118 ms 6992 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 101024 KB Output is correct
2 Incorrect 550 ms 101020 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 4568 KB Output is correct
2 Correct 259 ms 4440 KB Output is correct

Subtask #16
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1917 ms 361964 KB Output is correct
2 Incorrect 2270 ms 361760 KB Output isn't correct
3 Halted 0 ms 0 KB -