Submission #1076908

#TimeUsernameProblemLanguageResultExecution timeMemory
1076908mickey080929Soccer Stadium (IOI23_soccer)C++17
70 / 100
4602 ms513584 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 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); } } } } 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 biggest_stadium(int, std::vector<std::vector<int> >)':
soccer.cpp:53: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]
   53 |         for (int j=0; j<ran[i][i].size(); j++) {
      |                       ~^~~~~~~~~~~~~~~~~
soccer.cpp:62: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]
   62 |             for (int k=0; k<ran[i][j].size(); k++) {
      |                           ~^~~~~~~~~~~~~~~~~
soccer.cpp:69: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]
   69 |             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...