Submission #1207252

#TimeUsernameProblemLanguageResultExecution timeMemory
1207252HappyCapybaraSoccer Stadium (IOI23_soccer)C++17
48 / 100
4600 ms779260 KiB
#include "soccer.h" #include<bits/stdc++.h> using namespace std; int N; vector<vector<int>> F; //vector<vector<vector<vector<vector<vector<int>>>>>> dp; unordered_map<long long,int> dp; long long h(int t, int tl, int tr, int b, int bl, int br){ return t*pow(1000, 5)+tl*pow(1000, 4)+tr*pow(1000, 3)+b*pow(1000, 2)+bl*1000+br; } int solve(int t, int tl, int tr, int b, int bl, int br){ if (tl == -1 || bl == -1) return -pow(10, 9); if (dp.find(h(t, tl, tr, b, bl, br)) != dp.end()) return dp[h(t, tl, tr, b, bl, br)]; int res = 0; if (t > 0){ int l = -1; for (int j=max(tl, bl); j<=min(tr, br)+1; j++){ if (j == min(tr, br)+1 || F[t-1][j]){ res = max(res, j-l+solve(t-1, l, j-1, b, bl, br)); l = -1; } else if (l == -1) l = j; } } if (b < N-1){ int l = -1; for (int j=max(tl, bl); j<=min(tr, br)+1; j++){ if (j == min(tr, br)+1 || F[b+1][j]){ res = max(res, j-l+solve(t, tl, tr, b+1, l, j-1)); l = -1; } else if (l == -1) l = j; } } return dp[h(t, tl, tr, b, bl, br)] = res; } int biggest_stadium(int N, vector<vector<int>> F){ ::N = N; ::F = F; //dp.resize(N, vector<vector<vector<vector<vector<int>>>>>(N, vector<vector<vector<vector<int>>>>(N, vector<vector<vector<int>>>(N, vector<vector<int>>(N, vector<int>(N, -1)))))); int res = 0; for (int i=0; i<N; i++){ int l = -1; for (int j=0; j<=N; j++){ if (j == N || F[i][j]){ res = max(res, j-l+solve(i, l, j-1, i, l, j-1)); l = -1; } else if (l == -1) l = j; } } return 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...
#Verdict Execution timeMemoryGrader output
Fetching results...