제출 #848623

#제출 시각아이디문제언어결과실행 시간메모리
848623rxlfd314축구 경기장 (IOI23_soccer)C++17
0 / 100
4531 ms491444 KiB
#include "soccer.h" #include <bits/stdc++.h> using namespace std; using ari2 = array<int, 2>; #define vt vector #define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d)) #define FOR(a, b, c) REP(a, b, c, 1) #define ROF(a, b, c) REP(a, b, c, -1) #define chmax(a, b) a = a > (b) ? a : (b) #define chmin(a, b) a = a < (b) ? a : (b) int biggest_stadium(int N, vt<vt<int>> F) { int dp[N][N][N] = {}, psum[N], ret = 1; auto good = [&](int l, int r) { return psum[r] - (l ? psum[l-1] : 0) < 1; }; auto insert = [&](int p, int v, multiset<ari2> &m) { auto it = m.insert({p, v}); if (it != begin(m) && (*prev(it))[1] >= v) m.erase(it); else while (next(it) != end(m) && (*next(it))[1] <= v) m.erase(next(it)); }; FOR(row, 0, N-1) { FOR(i, 0, N-1) psum[i] = F[row][i] + (i ? psum[i-1] : 0); multiset<ari2> best; // r2, value ROF(l, N-1, 0) { FOR(r, l, N-1) { if (row) insert(r, dp[row-1][l][r], best); if (!good(l, r)) continue; auto it = best.lower_bound({r+1, 0}); int &ans = dp[row][l][r]; if (it != begin(best)) { it--; ans = (*it)[1]; } ans += r - l + 1; chmax(ret, ans); } } } int dp2[N][N][N] = {}; ROF(row, N-1, 0) { FOR(i, 0, N-1) psum[i] = F[row][i] + (i ? psum[i-1] : 0); multiset<ari2> best, best2; // r2, value ROF(l, N-1, 0) { FOR(r, l, N-1) { if (row + 1 < N) insert(r, dp2[row+1][l][r], best); if (row) insert(r, dp[row-1][l][r], best2); if (!good(l, r)) continue; auto it = best.lower_bound({r+1, 0}); int &ans = dp2[row][l][r]; if (it != begin(best)) { it--; ans = (*it)[1]; } ans += r - l + 1; it = best2.lower_bound({r+1, 0}); if (it != begin(best2)) { it--; chmax(ret, ans + (*it)[1]); } chmax(ret, ans); } } } return ret; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...