Submission #1111891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111891		nhanhoang510	Domino (COCI15_domino)	C++14	150 / 160	353 ms	194120 KiB

domino

#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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 0 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10
• Subtask 12: 10 / 10
• Subtask 13: 10 / 10
• Subtask 14: 10 / 10
• Subtask 15: 10 / 10
• Subtask 16: 10 / 10