제출 #356674

#제출 시각아이디문제언어결과실행 시간메모리
356674hamerin웜뱃 (IOI13_wombats)C++17
100 / 100
11630 ms197764 KiB
#include "wombats.h" #include <bits/stdc++.h> #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") using namespace std; using i64 = long long; using d64 = long double; using pi = pair<int, int>; using pli = pair<i64, i64>; using ti = tuple<int, int, int>; using tli = tuple<i64, i64, i64>; #define iterall(cont) cont.begin(), cont.end() #define prec(n) setprecision(n) << fixed const int L = 15; const int pinf = numeric_limits<int>::max() / 2; const int ninf = numeric_limits<int>::min() / 2; int R, C; vector<vector<int>> H, V; namespace DPHelper { vector<vector<int>> base_get(int r) { vector<vector<int>> ret(C, vector<int>(C, pinf)); for (int k = 0; k < C; k++) { for (int i = 0; i < C - k; i++) { if (k == 0) ret[i][i] = 0; else ret[i][i + k] = ret[i + k][i] = ret[i + 1][i + k] + H[r][i]; } } if (r != R - 1) { for (int i = 0; i < C; i++) for (int j = 0; j < C; j++) ret[i][j] += V[r][j]; } return ret; } vector<vector<int>> mer(const vector<vector<int>>& lhs, const vector<vector<int>>& rhs) { vector<vector<int>> ret(C, vector<int>(C, pinf)); vector<vector<int>> opt(C, vector<int>(C)); for (int k = 0; k < C; k++) { for (int i = 0; i < C - k; i++) { if (k == 0) { for (int j = 0; j < C; j++) { if (ret[i][i] > lhs[i][j] + rhs[j][i]) { ret[i][i] = lhs[i][j] + rhs[j][i]; opt[i][i] = j; } } } else { for (int j = opt[i][i + k - 1]; j <= opt[i + 1][i + k]; j++) { if (ret[i][i + k] > lhs[i][j] + rhs[j][i + k]) { ret[i][i + k] = lhs[i][j] + rhs[j][i + k]; opt[i][i + k] = j; } } for (int j = opt[i + k - 1][i]; j <= opt[i + k][i + 1]; j++) { if (ret[i + k][i] > lhs[i + k][j] + rhs[j][i]) { ret[i + k][i] = lhs[i + k][j] + rhs[j][i]; opt[i + k][i] = j; } } } } } return ret; } vector<vector<int>> base_solve(int s, int e) { auto ret = base_get(s); for (int r = s + 1; r <= e; r++) ret = mer(ret, base_get(r)); return ret; } }; // namespace DPHelper class SegTree { public: int N{}; vector<vector<vector<int>>> vl; SegTree() = default; SegTree(int N) { this->N = N; vl.resize(N << 2); } void init(int s, int e, int n) { if (e - s < L) { vl[n] = DPHelper::base_solve(s, e); return; } int m = (s + e) >> 1, k = n << 1; init(s, m, k); init(m + 1, e, k | 1); vl[n] = DPHelper::mer(vl[k], vl[k | 1]); } inline void init() { init(0, N - 1, 1); } void update(int s, int e, int n, int p) { if (e < p || p < s) return; if (e - s < L) { vl[n] = DPHelper::base_solve(s, e); return; } int m = (s + e) >> 1, k = n << 1; update(s, m, k, p); update(m + 1, e, k | 1, p); vl[n] = DPHelper::mer(vl[k], vl[k | 1]); } inline void update(int p) { update(0, N - 1, 1, p); } int query(int V1, int V2) { return vl[1][V1][V2]; } }; SegTree ST; void init(int r, int c, int h[5000][200], int v[5000][200]) { R = r, C = c; H.resize(R); V.resize(R - 1); for (int i = 0; i < R; i++) copy(h[i], h[i] + C - 1, back_inserter(H[i])); for (int i = 0; i < R - 1; i++) copy(v[i], v[i] + C, back_inserter(V[i])); ST = SegTree(R); ST.init(); } void changeH(int P, int Q, int W) { H[P][Q] = W; ST.update(P); } void changeV(int P, int Q, int W) { V[P][Q] = W; ST.update(P); } int escape(int V1, int V2) { return ST.query(V1, V2); }

컴파일 시 표준 에러 (stderr) 메시지

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...