Submission #1076909

#TimeUsernameProblemLanguageResultExecution timeMemory
1076909mickey080929Soccer Stadium (IOI23_soccer)C++17
77.50 / 100
655 ms512892 KiB
#include "soccer.h" #include <bits/stdc++.h> using namespace std; int dx[] = {1, -1, 0, 0}; int dy[] = {0, 0, 1, -1}; int dp[510][510][510]; vector<pair<int,int>> ran[510][510]; int large_case(int N, vector<vector<int>> F) { vector<vector<int>> vis(N, vector<int>(N, 0)); queue<pair<int,int>> q; for (int i=0; i<N; i++) { for (int j=0; j<N; j++) { if (F[i][j] == 0) { vis[i][j] = 1; q.push({i, j}); break; } } if (!q.empty()) break; } while (!q.empty()) { int x = q.front().first; int y = q.front().second; q.pop(); for (int k=0; k<4; k++) { int nx = x + dx[k]; int ny = y + dy[k]; if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue; if (vis[nx][ny]) continue; if (F[nx][ny]) continue; vis[nx][ny] = 1; q.push({nx, ny}); } } for (int i=0; i<N; i++) { for (int j=0; j<N; j++) { if (F[i][j] == 0 && vis[i][j] == 0) { return 0; } } } int tot = 0; bool flag = false; int pl = -1, pr = -1; vector<pair<int,int>> ran; for (int i=0; i<N; i++) { int l = -1, r = -1, cnt = 0; for (int j=0; j<N; j++) { if (F[i][j] == 0) { if (l == -1) l = j; r = j; cnt ++; } } if (cnt == 0) { pl = -1; pr = -1; continue; } ran.push_back({l, r}); if (r - l + 1 != cnt) { return 0; } if (pl != -1) { if (!flag) { if (l <= pl && pr <= r) {} else if (pl <= l && r <= pr) { flag = true; } else return 0; } else { if (pl <= l && r <= pr) {} else return 0; } } pl = l; pr = r; tot += cnt; } sort(ran.begin(), ran.end(), [&](pair<int,int> &u, pair<int,int> &v) { return u.second - u.first < v.second - v.first; }); for (int i=0; i+1<ran.size(); i++) { if (ran[i+1].first <= ran[i].first && ran[i].second <= ran[i+1].second) {} else return 0; } return tot; } int biggest_stadium(int N, vector<vector<int>> F) { int tot = 0; for (int i=0; i<N; i++) { for (int j=0; j<N; j++) { if (F[i][j] == 1) { tot ++; } } } if (tot == 0) return N * N; if (tot == 1) { for (int i=0; i<N; i++) { for (int j=0; j<N; j++) { if (F[i][j] == 1) { return N * N - min(i+1, N-i) * min(j+1, N-j); } } } } if (N > 500) { return large_case(N, F); } for (int i=0; i<N; i++) { vector<int> cnt(N, 0); for (int j=i; j<N; j++) { for (int k=0; k<N; k++) { if (F[j][k] == 0) { cnt[k] ++; } } int l = -1; for (int k=0; k<N; k++) { if (cnt[k] == j-i+1) { if (l == -1) l = k; if (k == N-1 || cnt[k+1] != j-i+1) { ran[i][j].push_back({l, k}); } } else l = -1; } } } int ans = 0; for (int i=0; i<N; i++) { for (int j=0; j<ran[i][i].size(); j++) { dp[i][i][j] = ran[i][i][j].second - ran[i][i][j].first + 1; ans = max(ans, dp[i][i][j]); } } for (int d=1; d<=N-1; d++) { for (int i=0; i<N-d; i++) { int j = i + d; int l = 0; for (int k=0; k<ran[i][j].size(); k++) { while (ran[i][j-1][l].second < ran[i][j][k].first) l ++; dp[i][j][k] = max(dp[i][j][k], dp[i][j-1][l] + ran[i][j][k].second - ran[i][j][k].first + 1); ans = max(ans, dp[i][j][k]); } l = 0; for (int k=0; k<ran[i][j].size(); k++) { while (ran[i+1][j][l].second < ran[i][j][k].first) l ++; dp[i][j][k] = max(dp[i][j][k], dp[i+1][j][l] + ran[i][j][k].second - ran[i][j][k].first + 1); ans = max(ans, dp[i][j][k]); } } } return ans; }

Compilation message (stderr)

soccer.cpp: In function 'int large_case(int, std::vector<std::vector<int> >)':
soccer.cpp:86:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |     for (int i=0; i+1<ran.size(); i++) {
      |                   ~~~^~~~~~~~~~~
soccer.cpp: In function 'int biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:137:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |         for (int j=0; j<ran[i][i].size(); j++) {
      |                       ~^~~~~~~~~~~~~~~~~
soccer.cpp:146:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  146 |             for (int k=0; k<ran[i][j].size(); k++) {
      |                           ~^~~~~~~~~~~~~~~~~
soccer.cpp:153:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |             for (int k=0; k<ran[i][j].size(); k++) {
      |                           ~^~~~~~~~~~~~~~~~~
#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...