#450628 (C++14) No.1028 闇討ち

• 問題: No.1028 闇討ち
• ユーザー: Thistle
• 提出日時: 2020-03-28 18:29:20
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 111 ms / 2,000 ms
• コード長: 1,192 bytes
• コンパイル時間: 683 ms
• コンパイル使用メモリ: 68,144 KB
• 実行使用メモリ: 22,516 KB
• 最終ジャッジ日時: 2023-10-25 23:41:32
• 合計ジャッジ時間: 4,195 ms
• ジャッジサーバーID （参考情報）: judge15 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,644 KB
testcase_01	AC	2 ms; 5,656 KB
testcase_02	AC	2 ms; 5,660 KB
testcase_03	AC	2 ms; 5,648 KB
testcase_04	AC	2 ms; 5,652 KB
testcase_05	AC	2 ms; 5,776 KB
testcase_06	AC	3 ms; 7,860 KB
testcase_07	AC	2 ms; 5,708 KB
testcase_08	AC	2 ms; 5,760 KB
testcase_09	AC	7 ms; 9,956 KB
testcase_10	AC	8 ms; 9,976 KB
testcase_11	AC	26 ms; 14,152 KB
testcase_12	AC	101 ms; 22,508 KB
testcase_13	AC	100 ms; 22,504 KB
testcase_14	AC	54 ms; 18,328 KB
testcase_15	AC	19 ms; 12,084 KB
testcase_16	AC	108 ms; 22,516 KB
testcase_17	AC	108 ms; 22,516 KB
testcase_18	AC	111 ms; 22,516 KB
testcase_19	AC	110 ms; 22,516 KB
testcase_20	AC	109 ms; 22,516 KB
testcase_21	AC	107 ms; 22,516 KB

ソースコード

#include<iostream>
#include<string>
#include<algorithm>
#include<cassert>

using namespace std;
using ll = int_fast64_t;
#define int ll
#define rep(i,n) for(int (i) = 0 ; (i) < (n) ; (i)++)
#define rng(i,s,n) for(int (i) = (s) ; (i) < (n) ; (i)++)
template<class T>bool chmax(T & a, const T & b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T & a, const T & b) { if (b < a) { a = b; return 1; } return 0; }
ll read() { ll u, k = scanf("%lld", &u); return u; }

int n;
int a[2000][2000];
int b[2000];//現在のコスト
int ans[2000];//答えのコスト
int c[2000][2];
void solve() {
	cin >> n;
	rep(i, n)rep(j, n) {
		a[i][j] = read() - 1;
		b[a[i][j]] += i + j - min(i, j);
		if (j < i) c[a[i][j]][1]++;
	}
	assert(1 <= n && n <= 1000);
	rep(i, n)rep(j, n) {
		assert(0 <= a[i][j] && a[i][j] < n);
	}
	rep(i, n) {
		ans[i] = b[i];
	}
	rep(i, n) {
		for (int j = 0; i - j >= 0; j++) {
			c[a[i - j][j]][0]++;
		}
		rep(j, n) {
			b[j] += c[j][0] - c[j][1];
		}
		rep(j, n) chmin(ans[j], b[j]);
		for (int j = 0; i + j + 1 < n; j++) {
			c[a[i + j + 1][j]][1]--;
		}
	}
	int sum = 0;
	rep(i, n) sum += ans[i];
	cout << sum << endl;
}
signed main() {
	solve();
}