結果
問題 |
No.1028 闇討ち
|
ユーザー |
![]() |
提出日時 | 2020-04-19 02:33:32 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 106 ms / 2,000 ms |
コード長 | 1,610 bytes |
コンパイル時間 | 985 ms |
コンパイル使用メモリ | 94,548 KB |
実行使用メモリ | 11,520 KB |
最終ジャッジ日時 | 2024-10-04 00:43:18 |
合計ジャッジ時間 | 2,859 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
/* -*- coding: utf-8 -*- * * 1028.cc: No.1028 闇討ち - yukicoder */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<functional> using namespace std; /* constant */ const int MAX_N = 1000; const int INF = 1 << 30; /* typedef */ /* global variables */ int xs[MAX_N][MAX_N], ys[MAX_N][MAX_N], cs[MAX_N]; int decs[MAX_N + 1], incs[MAX_N + 1]; /* subroutines */ inline int dist(int dx, int dy) { return max(abs(dx), dy); } /* main */ int main() { int n; scanf("%d", &n); for (int y = 0; y < n; y++) for (int x = 0; x < n; x++) { int a; scanf("%d", &a); a--; xs[a][cs[a]] = x; ys[a][cs[a]] = y; cs[a]++; } int sum = 0; for (int i = 0; i < n; i++) { memset(decs, 0, sizeof(decs)); memset(incs, 0, sizeof(incs)); for (int j = 0; j < n; j++) { int y0 = ys[i][j] - xs[i][j], y1 = ys[i][j] + xs[i][j]; if (y0 > 0) decs[0]++, decs[y0]--; if (y1 + 1 < n) incs[y1 + 1]++, incs[n]--; } for (int y = 0; y < n; y++) decs[y + 1] += decs[y], incs[y + 1] += incs[y]; int s = 0; for (int j = 0; j < n; j++) s += dist(xs[i][j], ys[i][j]); int mins = s; for (int y = 1; y < n; y++) { s += incs[y] - decs[y - 1]; if (mins > s) mins = s; } sum += mins; //printf("%d: %d\n", i, mins); } printf("%d\n", sum); return 0; }