This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |