BONUS13 - VOI 2013 - Phần thưởng

Tác giả: ladpro98

Ngôn ngữ: C++

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#include <climits>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define RESET(a, v) memset((a), (v), sizeof((a)))
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int QUEEN = 1;
const int ROOK = 2;
const int BISHOP = 3;
const int KNIGHT = 4;

const int N = 20;
const int gap = 8;

const int dx[] = {-1, -2, -2, -1, 1, 2, 2, 1};
const int dy[] = {-2, -1, 1, 2, 2, 1, -1, -2};

using namespace std;

int nFree, nRes; LL ans;
int val[N][N], cnt[N][N], cntX[N], cntY[N], cntDiag1[N], cntDiag2[N];
II freeCells[N * N], resCells[N * N];

void readInput() {
    ios :: sync_with_stdio(0); cin.tie(0);
    int k, u, v, c;
    cin >> k;
    FOR(i, 0, k) {
        cin >> u >> v >> c;
        val[u][v] = c;
    }
    REP(i, 1, 8) REP(j, 1, 8)
    if (val[i][j] == 0)
        freeCells[nFree++] = MP(i, j);
    else
        resCells[nRes++] = MP(i, j);
}

void update() {
    int x, y; LL sum = 0;
    FOR(i, 0, nRes) {
        x = resCells[i].X, y = resCells[i].Y;
        if (cnt[x][y] || cntX[x] || cntY[y] || cntDiag1[x + y] || cntDiag2[x - y + gap])
            sum += val[x][y];
    }
    ans = max(ans, sum);
}

void put(int type, int x, int y, int v) {
    if (type == QUEEN || type == ROOK)
        cntX[x] += v, cntY[y] += v;
    if (type == QUEEN || type == BISHOP)
        cntDiag1[x + y] += v, cntDiag2[x - y + gap] += v;
    if (type == KNIGHT)
    FOR(i, 0, 8) {
        x += dx[i]; y += dy[i];
        if (0 < x && 0 < y && x < 9 && y < 9)
            cnt[x][y] += v;
        x -= dx[i]; y -= dy[i];
    }
}

bool was[N * N];
void backtrack(int now) {
    if (now > 4) {
        update(); return;
    }
    FOR(i, 0, nFree)
    if (!was[i]) {
        was[i] = 1;
        put(now, freeCells[i].X, freeCells[i].Y, 1);
        backtrack(now + 1);
        was[i] = 0;
        put(now, freeCells[i].X, freeCells[i].Y, -1);
    }
}

int main() {
    readInput();
    backtrack(1);
    cout << ans;
    return 0;
}

Download