結果
問題 |
No.1028 闇討ち
|
ユーザー |
![]() |
提出日時 | 2020-05-15 20:13:25 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 414 ms / 2,000 ms |
コード長 | 1,403 bytes |
コンパイル時間 | 1,506 ms |
コンパイル使用メモリ | 166,892 KB |
実行使用メモリ | 16,256 KB |
最終ジャッジ日時 | 2024-09-19 06:40:24 |
合計ジャッジ時間 | 6,987 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
/** * @FileName e.cpp * @Author kanpurin * @Created 2020.05.15 20:13:17 **/ #include "bits/stdc++.h" using namespace std; typedef long long ll; int main() { int n; cin >> n; vector< vector< int > > a1(n),a2(n); vector< vector< int > > ans(n, vector< int >(n)); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int b; cin >> b; b--; a1[b].push_back(i - j); a2[b].push_back(i + j); ans[0][b] += max(i,j); } } for (int i = 0; i < n; i++) { sort(a1[i].begin(), a1[i].end()); sort(a2[i].begin(), a2[i].end()); } for (int i = 1; i < n; i++) { for (int j = 0; j < n; j++) { //cout << i << " " << j << " " << (upper_bound(a2[j].begin(), a2[j].end(), i-1) - a2[j].begin()) << endl; //cout << i << " " << j << " " << a1[j].end() - upper_bound(a1[j].begin(), a1[j].end(), i-1) << endl; ans[i][j] = ans[i-1][j] + (upper_bound(a2[j].begin(), a2[j].end(), i-1) - a2[j].begin()) - (a1[j].end() - upper_bound(a1[j].begin(), a1[j].end(), i-1)); } } int res = 0; constexpr int INF = 1e9 + 6; for (int i = 0; i < n; i++) { int m = INF; for (int j = 0; j < n; j++) { m = min(ans[j][i],m); } res += m; } cout << res << endl; return 0; }