結果
問題 |
No.1028 闇討ち
|
ユーザー |
![]() |
提出日時 | 2020-04-20 00:16:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 109 ms / 2,000 ms |
コード長 | 1,220 bytes |
コンパイル時間 | 2,611 ms |
コンパイル使用メモリ | 197,912 KB |
最終ジャッジ日時 | 2025-01-09 21:47:17 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
#include <bits/stdc++.h> using namespace std; struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_; #define FOR(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++) #define IFOR(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--) #define REP(i, n) FOR(i,0,n) #define IREP(i, n) IFOR(i,0,n) template<typename T> bool chmin(T &m, const T q) { if (m > q) {m = q; return true;} else return false; } template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; } int main() { int N; cin >> N; vector A(N, vector<int>(N)); cin >> A; vector i1(N, vector<int>(N)), i2(N, vector<int>(N)); int ret = 0; REP(i, N) REP(j, N) { int k = A[i][j] - 1; ret += j; if (i + j + 1 < N) i1[k][i + j + 1]++; if (i - j - 1 >= 0) i2[k][i - j - 1]++; } REP(_, 2) REP(i, N) REP(j, N - 1) i1[i][j + 1] += i1[i][j]; REP(_, 2) REP(i, N) IREP(j, N - 1) i2[i][j] += i2[i][j + 1]; REP(i, N) { int tmp = 1e9; REP(j, N) chmin(tmp, i1[i][j] + i2[i][j]); ret += tmp; } cout << ret << '\n'; }