Submission #1020011

#TimeUsernameProblemLanguageResultExecution timeMemory
1020011AndreyGarden (JOI23_garden)C++14
100 / 100
1990 ms201044 KiB
#include<bits/stdc++.h> using namespace std; vector<bool> red(5001); vector<bool> col(5001); int haha[5001][5001]; int bruh[5001][5001]; int ans; int d; void calc(int a) { vector<int> l(5001); vector<int> r(5001); deque<pair<int,int>> idk; for(int i = 0; i < d; i++) { idk.push_back({bruh[a][i],i}); } for(int i = 0; i < d; i++) { if(idk[0].second == i) { idk.pop_front(); } while(!idk.empty() && idk[idk.size()-1].first >= bruh[a][i]) { idk.pop_back(); } if(idk.empty()) { l[i] = d-1; } else { l[i] = (i-idk[idk.size()-1].second+d)%d; } idk.push_back({bruh[a][i],i}); } idk.clear(); for(int i = d-1; i >= 0; i--) { idk.push_back({bruh[a][i],i}); } for(int i = d-1; i >= 0; i--) { if(idk[0].second == i) { idk.pop_front(); } while(!idk.empty() && idk[idk.size()-1].first >= bruh[a][i]) { idk.pop_back(); } if(idk.empty()) { r[i] = d-1; } else { r[i] = (idk[idk.size()-1].second-i+d)%d; } idk.push_back({bruh[a][i],i}); } for(int i = 0; i < d; i++) { int c = min(d-1,l[i]+r[i]-1); if(bruh[a][i] > 0) { ans = min(ans,(d-bruh[a][i])*(d-c)); } } } int main() { ios_base::sync_with_stdio(NULL); cin.tie(NULL); cout.tie(NULL); int n,m,a,b; cin >> n >> m >> d; for(int i = 0; i < d; i++) { for(int j = 0; j < d; j++) { haha[i][j] = 0; } } for(int i = 0; i < n; i++) { cin >> a >> b; red[a] = true; col[b] = true; } for(int i = 0; i < m; i++) { cin >> a >> b; haha[a][b] = 1; } for(int i = 0; i < d; i++) { if(red[i]) { for(int j = 0; j < d; j++) { haha[i][j] = 1; } } if(col[i]) { for(int j = 0; j < d; j++) { haha[j][i] = 1; } } } ans = d*d; for(int j = 0; j < d; j++) { int br = 0; for(int i = 0; i < d; i++) { if(haha[i][j] == 1) { br = 0; } else { br++; } bruh[i][j] = br; } for(int i = 0; i < d; i++) { if(haha[i][j] == 1) { br = 0; } else { br++; } bruh[i][j] = min(d-1,br); } } int br = 0,sm = 0; for(int i = 0; i < d; i++) { if(red[i] == 0) { br++; } else { br = 0; } sm = max(sm,br); } for(int i = 0; i < d; i++) { if(red[i] == 0) { br++; } else { br = 0; } sm = max(sm,br); } br = 0; for(int i = 0; i < d; i++) { if(col[i] == 0) { br++; } else { br = 0; } sm = max(sm,br); } for(int i = 0; i < d; i++) { if(col[i] == 0) { br++; } else { br = 0; } sm = max(sm,br); } ans = d*(d-sm); for(int i = 0; i < d; i++) { calc(i); } cout << ans; return 0; }
#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...