Submission #488102

#	Time	Username	Problem	Language	Result	Execution time	Memory
488102		AdamGS	Furniture (JOI20_furniture)	C++14	5 / 100	5076 ms	24936 KiB

furniture

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e3+7, INF=1e9+7;
int T[LIM][LIM], dp[LIM][LIM], uzyte[LIM][LIM], ans[LIM*LIM], n, m;
pair<int,int>P[LIM*LIM];
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	rep(i, n) rep(j, m) {
		T[i][j]=INF;
		int a;
		cin >> a;
		if(a) T[i][j]=-1;
	}
	int q;
	cin >> q;
	rep(i, q) {
		ans[i]=1;
		int a, b;
		cin >> a >> b; --a; --b;
		T[a][b]=i;
		P[i]={a, b};
	}
	rep(i, n+1) dp[i][0]=-1;
	rep(i, m+1) dp[0][i]=-1;
	dp[0][1]=dp[1][0]=INF;
	while(true) {
		rep(i, n) rep(j, m) {
			dp[i+1][j+1]=min(T[i][j], max(dp[i][j+1], dp[i+1][j]));
		}
		if(dp[n][m]==INF) break;
		ans[dp[n][m]]=0;
		T[P[dp[n][m]].st][P[dp[n][m]].nd]=INF;
	}
	rep(i, q) cout << ans[i] << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 0 / 95