oj.uz

Submission #1111891

# Submission time Handle Problem Language Result Execution time Memory
1111891 2024-11-13T09:43:17 Z nhanhoang510 Domino (COCI15_domino) C++14
150 / 160
 353 ms 194120 KB 
#include <bits/stdc++.h>
#define F first
#define S second

using namespace std;

const int maxn = 2000 + 7;
const int LOG = 20;
const long long MOD = (long long)(1e9) + 7;
const long long base = 311;
const int ALP_BET = 26;

typedef pair<int, int> ii;
typedef pair<int, long long> il;
typedef pair<long long, int> li;
typedef pair<long long, long long> ll;

const int maxN = 100000 + 7;
int dx4[4] = {0, 0, -1, +1};
int dy4[4] = {-1, +1, 0, 0};

struct EDGE{
    int x, y;
    int u, v;
    int val;
};

bool cmp(EDGE a, EDGE b){
    return a.val > b.val;
}

int n, k;
int arr[maxn][maxn];

bool avail[maxn][maxn];

int m;
EDGE e[2 * maxn * maxn];

int ans;

int cnt[maxN];
int pos[maxN];

void count_sort(){
    memset(cnt, 0, sizeof(cnt));
    memset(pos, 0, sizeof(pos));
    for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= n; ++j){
        if(i < n){
            cnt[arr[i][j] + arr[i + 1][j]]++;
        }
        if(j < n){
            cnt[arr[i][j] + arr[i][j + 1]]++;
        }
    }
    int pre = 0;
    for(int i = 0; i < maxN; ++i){
        pos[i] = pre + 1;
        pre = pre + cnt[i];
    }
    m = pre;
    for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= n; ++j){
        if(i < n){
            int val = arr[i][j] + arr[i + 1][j];
            int id = pos[val];
            e[id] = {i, j, i + 1, j, val};
            pos[val]++;
        }
        if(j < n){
            int val = arr[i][j] + arr[i][j + 1];
            int id = pos[val];
            e[id] = {i, j, i, j + 1, val};
            pos[val]++;
        }
    }
    reverse(e + 1, e + m + 1);
    return;
}

bool check_avail(int id){
    int x = e[id].x;
    int y = e[id].y;
    int u = e[id].u;
    int v = e[id].v;
    if(avail[x][y] == false)
        return false;
    if(avail[u][v] == false)
        return false;
    return true;
}

void dq(int num, int sum, int id){
    if(num > k){
        return;
    }
    if(num == k){
        ans = max(ans, sum);
        return;
    }
    while(id <= m && check_avail(id) == false)
        ++id;
    if(id > m){
        return;
    }
    int x = e[id].x;
    int y = e[id].y;
    int u = e[id].u;
    int v = e[id].v;
    avail[x][y] = avail[u][v] = false;
    dq(num + 1, sum + e[id].val, id);
    for(int op_1 = 0; op_1 < 4; ++op_1)
    for(int op_2 = 0; op_2 < 4; ++op_2){
        int X = x + dx4[op_1];
        int Y = y + dy4[op_1];
        int U = u + dx4[op_2];
        int V = v + dy4[op_2];
        if(avail[X][Y] == false || avail[U][V] == false)
            continue;
        if(abs(U - X) + abs(V - Y) == 1)
            continue;
        int new_sum = sum + e[id].val + arr[X][Y] + arr[U][V];
        avail[X][Y] = avail[U][V] = false;
        dq(num + 2, new_sum, id);
        avail[X][Y] = avail[U][V] = true;
    }
    avail[x][y] = avail[u][v] = true;
    return;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= n; ++j)
        cin >> arr[i][j];
    memset(avail, true, sizeof(avail));
    ans = 0;
    for(int i = 0; i <= n + 1; ++i){
        avail[0][i] = false;
        avail[i][0] = false;
        avail[n + 1][i] = false;
        avail[i][n + 1] = false;
    }
    count_sort();

    dq(0, 0, 1);

    // ANS
    int sum_all = 0;
    for(int i = 1; i <= n; ++i)
    for(int j = 1; j <= n; ++j)
        sum_all = sum_all + arr[i][j];
    cout << sum_all - ans << "\n";
//    cout << sum_all << " " << ans << "\n";
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 22096 KB Output is correct
2 Correct 15 ms 22096 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 278 ms 193608 KB Output is correct
2 Correct 311 ms 193484 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 185 ms 115804 KB Output is correct
2 Correct 135 ms 113848 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 57672 KB Output is correct
2 Correct 71 ms 57664 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 192832 KB Output is correct
2 Correct 266 ms 190056 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 8684 KB Output is correct
2 Correct 3 ms 8784 KB Output is correct

Subtask #9
0 / 10.0

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

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8672 KB Output is correct
2 Correct 3 ms 8784 KB Output is correct

Subtask #11
10.0 / 10.0

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

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 192840 KB Output is correct
2 Correct 305 ms 194004 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8784 KB Output is correct
2 Correct 3 ms 8668 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 57672 KB Output is correct
2 Correct 62 ms 57676 KB Output is correct

Subtask #15
10.0 / 10.0

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

Subtask #16
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 339 ms 192708 KB Output is correct
2 Correct 288 ms 194120 KB Output is correct