제출 #841078

#제출 시각아이디문제언어결과실행 시간메모리
841078Lucpp축구 경기장 (IOI23_soccer)C++17
64 / 100
4567 ms63336 KiB
#include <bits/stdc++.h> #include "soccer.h" using namespace std; int biggest_stadium(int N, vector<vector<int>> F){ int ans = 0; for(int k = 0; k < N; k++){ vector<int> l(N, k), r(N, k); for(int i = 0; i < N; i++){ if(F[i][k]) continue; while(l[i] > 0 && F[i][l[i]-1] == 0) l[i]--; while(r[i] < N && F[i][r[i]] == 0) r[i]++; } vector<vector<int>> score(N, vector<int>(N)); for(int i = 0; i < N; i++){ int mal = 0, mir = N; for(int j = i; j < N; j++){ mal = max(mal, l[j]); mir = min(mir, r[j]); score[i][j] = max(0, mir-mal); } } vector<vector<int>> dp(N, vector<int>(N)); for(int d = N-1; d >= 0; d--){ for(int i = 0; i+d < N; i++){ int j = i+d; int res = 0; if(i > 0) res = dp[i-1][j] + score[i-1][j]; if(j < N-1) res = max(res, dp[i][j+1] + score[i][j+1]); dp[i][j] = res; } } for(int i = 0; i < N; i++) ans = max(ans, dp[i][i]+score[i][i]); } return ans; }
#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...