oj.uz

답안 #306039

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
306039 2020-09-24T10:55:59 Z TadijaSebez Furniture (JOI20_furniture) C++11
100 / 100
 3753 ms 28280 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
void ckmx(int&x,int y){x=max(x,y);}
void ckmn(int&x,int y){x=min(x,y);}
const int N=1050;
const int inf=1e9+7;
int c[N][N],dp1[N][N],dp2[N][N],ans[N*N];
void Solve(int x1,int y1,int x2,int y2,int t){
	if(x1==x2&&y1==y2)return;
	if(x1==x2){
		for(int i=y1+1;i<y2;i++)if(c[x1][i]!=inf)ans[c[x1][i]]=0;
		return;
	}
	if(y1==y2){
		for(int i=x1+1;i<x2;i++)if(c[i][y1]!=inf)ans[c[i][y1]]=0;
		return;
	}
	int mx=0,x,y;
	if(t==1){
		dp1[x1][y1]=inf;
		for(int i=x1;i<=x2;++i)for(int j=y1;j<=y2;++j)if(i!=x1||j!=y1){
			dp1[i][j]=0;
			if(i!=x1)ckmx(dp1[i][j],dp1[i-1][j]);
			if(j!=y1)ckmx(dp1[i][j],dp1[i][j-1]);
			ckmn(dp1[i][j],c[i][j]);
			int now=min(dp1[i][j],dp2[i][j]);
			if(now!=c[i][j]||(i==x2&&j==y2))continue;
			if(now>mx)mx=now,x=i,y=j;
		}
	}
	if(t==0){
		dp2[x2][y2]=inf;
		for(int i=x2;i>=x1;--i)for(int j=y2;j>=y1;--j)if(i!=x2||j!=y2){
			dp2[i][j]=0;
			if(i!=x2)ckmx(dp2[i][j],dp2[i+1][j]);
			if(j!=y2)ckmx(dp2[i][j],dp2[i][j+1]);
			ckmn(dp2[i][j],c[i][j]);
			int now=min(dp1[i][j],dp2[i][j]);
			if(now!=c[i][j]||(i==x1&&j==y1))continue;
			if(now>mx)mx=now,x=i,y=j;
		}
	}
	if(mx==0||mx==inf)return;
	ans[c[x][y]]=0;
	c[x][y]=inf;
	Solve(x1,y1,x,y,0);
	Solve(x,y,x2,y2,1);
}
int main(){
	int n,m,q;
	scanf("%i %i",&n,&m);
	for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
		scanf("%i",&c[i][j]);
		if(c[i][j])c[i][j]=0;
		else c[i][j]=inf;
	}
	scanf("%i",&q);
	for(int i=1,x,y;i<=q;i++){
		scanf("%i %i",&x,&y);
		c[x][y]=i;
		ans[i]=1;
	}
	dp1[1][1]=inf;
	for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)if(i!=1||j!=1){
		dp1[i][j]=0;
		if(i!=1)ckmx(dp1[i][j],dp1[i-1][j]);
		if(j!=1)ckmx(dp1[i][j],dp1[i][j-1]);
		ckmn(dp1[i][j],c[i][j]);
	}
	Solve(1,1,n,m,0);
	for(int i=1;i<=q;i++)printf("%i\n",ans[i]);
	return 0;
}

Compilation message

furniture.cpp: In function 'int main()':
furniture.cpp:53:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |  scanf("%i %i",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~
furniture.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   55 |   scanf("%i",&c[i][j]);
      |   ~~~~~^~~~~~~~~~~~~~~
furniture.cpp:59:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   59 |  scanf("%i",&q);
      |  ~~~~~^~~~~~~~~
furniture.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   61 |   scanf("%i %i",&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~
furniture.cpp: In function 'void Solve(int, int, int, int, int)':
furniture.cpp:16:2: warning: 'y' may be used uninitialized in this function [-Wmaybe-uninitialized]
   16 |  if(y1==y2){
      |  ^~
furniture.cpp:12:2: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
   12 |  if(x1==x2){
      |  ^~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1280 KB Output is correct
2 Correct 3 ms 1664 KB Output is correct
3 Correct 4 ms 1536 KB Output is correct
4 Correct 5 ms 1664 KB Output is correct
5 Correct 5 ms 1664 KB Output is correct
6 Correct 7 ms 1664 KB Output is correct
7 Correct 5 ms 1664 KB Output is correct
8 Correct 5 ms 1664 KB Output is correct
9 Correct 5 ms 1664 KB Output is correct

Subtask #2
95.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 1280 KB Output is correct
2 Correct 3 ms 1664 KB Output is correct
3 Correct 4 ms 1536 KB Output is correct
4 Correct 5 ms 1664 KB Output is correct
5 Correct 5 ms 1664 KB Output is correct
6 Correct 7 ms 1664 KB Output is correct
7 Correct 5 ms 1664 KB Output is correct
8 Correct 5 ms 1664 KB Output is correct
9 Correct 5 ms 1664 KB Output is correct
10 Correct 15 ms 1536 KB Output is correct
11 Correct 4 ms 1024 KB Output is correct
12 Correct 239 ms 18296 KB Output is correct
13 Correct 109 ms 14072 KB Output is correct
14 Correct 452 ms 24568 KB Output is correct
15 Correct 473 ms 25080 KB Output is correct
16 Correct 3430 ms 26332 KB Output is correct
17 Correct 3753 ms 27932 KB Output is correct
18 Correct 1226 ms 27260 KB Output is correct
19 Correct 504 ms 28152 KB Output is correct
20 Correct 416 ms 28152 KB Output is correct
21 Correct 481 ms 28280 KB Output is correct