oj.uz

Submission #892904

# Submission time Handle Problem Language Result Execution time Memory
892904 2023-12-26T06:56:29 Z Hhw48 Trampoline (info1cup20_trampoline) C++14
23 / 100
 2000 ms 286036 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
int r,c,n;
int arr[3000][3000];
int dp[3000][3000];
int memo(int y, int x, int t_y, int t_x){
	if(x>t_x)return 0;
	if(y>t_y)return 0;
	if(x<1||y<1)return 0;
	if(dp[y][x] != -1)return dp[y][x];
	if(y==t_y && x==t_x){
		return 1;
	}
	else{
		if(arr[y][x]==1){
			dp[y][x]=max(memo(y,x+1,t_y,t_x),memo(y+1,x,t_y,t_x));
			return dp[y][x];
		}
		else{
			dp[y][x]=memo(y,x+1,t_y,t_x);
			return dp[y][x];
		}
	}
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>r>>c>>n;
	memset(arr,0,sizeof(arr));
	memset(dp,-1,sizeof(dp));
	for(int i=1; i<=n; i++){
		int x,y;
		cin>>y>>x;
		arr[y][x]=1;
	}
	int t;
	cin>>t;
	while(t--){
		memset(dp,-1,sizeof(dp));
		int sy,sx,ey,ex;
		cin>>sy>>sx>>ey>>ex;
		/*
		bool flag=true;
		if(sy==r){
			cout<<"No\n";
			continue;
		}
		for(int i=sx; i<=c; i++){
			if(arr[sy][i]==1 && i<=ex){
				cout<<"Yes\n";
				flag=false;
				break;
			}
		}
		if(flag==true)cout<<"No\n
		*/
		if(memo(sy,sx,ey,ex)==1){
			cout<<"Yes\n";
		}
		else{
			cout<<"No\n";
		}
	}
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 947 ms 141396 KB 200 token(s): yes count is 21, no count is 179
2 Correct 950 ms 141392 KB 200 token(s): yes count is 70, no count is 130
3 Correct 934 ms 141504 KB 197 token(s): yes count is 25, no count is 172

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2052 ms 141460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 126 ms 286036 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 121 ms 286036 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 122 ms 286032 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -