結果
問題 | No.1028 闇討ち |
ユーザー |
![]() |
提出日時 | 2020-04-17 22:01:32 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 191 ms / 2,000 ms |
コード長 | 1,808 bytes |
コンパイル時間 | 1,107 ms |
コンパイル使用メモリ | 105,896 KB |
実行使用メモリ | 19,072 KB |
最終ジャッジ日時 | 2024-10-03 12:55:34 |
合計ジャッジ時間 | 4,023 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 20 |
ソースコード
// #define _GLIBCXX_DEBUG // for STL debug (optional) #include <iostream> #include <iomanip> #include <cstdio> #include <string> #include <cstring> #include <deque> #include <list> #include <queue> #include <stack> #include <vector> #include <utility> #include <algorithm> #include <map> #include <set> #include <complex> #include <cmath> #include <limits> #include <cfloat> #include <climits> #include <ctime> #include <cassert> #include <numeric> #include <fstream> #include <functional> #include <bitset> using namespace std; using ll = long long int; using int64 = long long int; template<typename T> void chmax(T &a, T b) {a = max(a, b);} template<typename T> void chmin(T &a, T b) {a = min(a, b);} template<typename T> void chadd(T &a, T b) {a = a + b;} int dx[] = {0, 0, 1, -1}; int dy[] = {1, -1, 0, 0}; const int INF = 1LL << 29; const ll LONGINF = 1LL << 60; const ll MOD = 1000000007LL; int dist(int a, int b, int x, int y) { return max(abs(a - x), abs(b - y)); } int main() { // 距離: min(a-x, b-y) int N; scanf("%d", &N); vector<ll> sum(N), acc(N), ans(N, LONGINF); vector< vector<ll> > inc(N, vector<ll>(N)), dec(N, vector<ll>(N)); for(int i=0; i<N; i++) { for(int j=0; j<N; j++) { int v; scanf("%d", &v); v--; int d = dist(0, 0, i, j); int p1 = max(i - j, 0); int p2 = min(i + j, N - 1); sum[v] += d; inc[p1][v]++; inc[p2][v]++; dec[0][v]++; } } for(int r=0; r<N; r++) { for(int v=0; v<N; v++) { chmin(ans[v], sum[v]); acc[v] += inc[r][v] - dec[r][v]; sum[v] += acc[v]; } } ll res = accumulate(ans.begin(), ans.end(), 0LL); cout << res << endl; return 0; }