oj.uz

답안 #255370

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
255370 2020-07-31T20:10:06 Z VEGAnn Domino (COCI15_domino) C++14
160 / 160
 508 ms 114584 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
#define PB push_back
#define i2 array<int,2>
#define sz(x) ((int)x.size())
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
const int N = 2010;
const int oo = 2e9;
const int cnst = 50;
vector<i2> who[N];
ll glob = 0;
int n, k, a[N][N], S, T, GO[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int dst[N * N], pre[N * N];
bool good[N][N];

struct edge{
    int a, b, cap, flow, cost;

    edge(): a(0), b(0), cap(0), flow(0), cost(0) {}
    edge(int _a, int _b, int c, int f, int co): a(_a), b(_b), cap(c), flow(f), cost(co) {}
};

vector<edge> edges;
gp_hash_table<int, vector<int> > g;

void add_edge(int a, int b, int cst){
    g[a].PB(sz(edges));
    edges.PB(edge(a, b, 1, 0, cst));

    g[b].PB(sz(edges));
    edges.PB(edge(b, a, 0, 0, -cst));
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n >> k;

    for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
        cin >> a[i][j];
        glob += a[i][j];
    }

    S = n * n;
    T = n * n + 1;

    for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++){
        if (i > 0)
            who[a[i][j] + a[i - 1][j]].PB({i * n + j, (i - 1) * n + j});

        if (j > 0)
            who[a[i][j] + a[i][j - 1]].PB({i * n + j, i * n + j - 1});
    }

    int rem = cnst;

    for (int i = N - 1; i >= 0 && rem > 0; i--)
    for (int itr = 0; itr < sz(who[i]) && rem > 0; itr++){
        i2 cur = who[i][itr];

        good[cur[0] / n][cur[0] % n] = 1;
        good[cur[1] / n][cur[1] % n] = 1;

        rem--;
    }

    for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        if ((i + j) & 1){
            if (good[i][j])
                add_edge(i * n + j, T, 0);
        } else {
            if (!good[i][j]) continue;

            add_edge(S, i * n + j, 0);

            for (int it = 0; it < 4; it++){
                int x = i + GO[it][0];
                int y = j + GO[it][1];

                if (x < 0 || x >= n || y < 0 || y >= n || !good[x][y]) continue;

                add_edge(i * n + j, x * n + y, -(a[i][j] + a[x][y]));
            }
        }

    ll cost = 0;

    for (int itr = 0; itr < k; itr++){
        fill(dst, dst + T + 1, oo);

        dst[S] = 0;

        for (int nit = 0; nit < 2 * cnst; nit++){
            for (int idx = 0; idx < sz(edges); idx++) {
                edge cr = edges[idx];

                if (dst[cr.a] < oo && cr.flow < cr.cap && dst[cr.b] > dst[cr.a] + cr.cost) {
                    dst[cr.b] = dst[cr.a] + cr.cost;
                    pre[cr.b] = idx;
                }
            }
        }

        cost += dst[T];

        int pos = T;

        while (pos != S){
            int id = pre[pos];

            edges[id].flow++;
            edges[id ^ 1].flow--;

            pos = edges[id].a;
        }
    }

    cout << glob + cost;

    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 10616 KB Output is correct
2 Correct 30 ms 8432 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 896 KB Output is correct
2 Correct 1 ms 768 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 464 ms 114144 KB Output is correct
2 Correct 508 ms 94572 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 512 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 259 ms 70904 KB Output is correct
2 Correct 272 ms 78108 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 118 ms 34936 KB Output is correct
2 Correct 135 ms 28124 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 465 ms 114168 KB Output is correct
2 Correct 440 ms 94656 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 768 KB Output is correct
2 Correct 2 ms 768 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 481 ms 114296 KB Output is correct
2 Correct 448 ms 94832 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 1536 KB Output is correct
2 Correct 2 ms 1280 KB Output is correct

Subtask #11
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #12
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 458 ms 113728 KB Output is correct
2 Correct 472 ms 94680 KB Output is correct

Subtask #13
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1024 KB Output is correct
2 Correct 2 ms 1024 KB Output is correct

Subtask #14
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 125 ms 34504 KB Output is correct
2 Correct 120 ms 28124 KB Output is correct

Subtask #15
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #16
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 492 ms 114584 KB Output is correct
2 Correct 479 ms 94768 KB Output is correct