oj.uz

Submission #897969

# Submission time Handle Problem Language Result Execution time Memory
897969 2024-01-04T06:14:01 Z LCJLY Nautilus (BOI19_nautilus) C++14
66 / 100
 25 ms 9564 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl; 
#define show4(x,y) for(auto it:x) cout << it << " "; cout << #y << endl;
typedef pair<int,int>pii;
typedef pair<pii,pii>pi2;

int n,m,k;
string arr[105];
vector<pii>dir[105];
int memo[105][105][105];

int dp(int index, int pos, int pos2){
	if(index==k) return 1;
	if(memo[index][pos][pos2]!=-1) return memo[index][pos][pos2];
	int ans=0;
	
	for(auto it:dir[index]){
		int newx=pos+it.first;
		int newy=pos2+it.second;
		if(newx<0||newy<0||newx>=n||newy>=m) continue;
		if(arr[newx][newy]=='#') continue;
		ans|=dp(index+1,newx,newy);
	}
	//show3(index,index,pos,pos,pos2,pos2);
	//show(ans,ans);
	return memo[index][pos][pos2]=ans;
}

void solve(){	
	cin >> n >> m >> k;
	
	for(int x=0;x<n;x++){
		cin >> arr[x];
	}
	
	
	string s;
	cin >> s;
	
	reverse(s.begin(),s.end());
	for(int x=0;x<k;x++){
		if(s[x]=='N'){
			dir[x].push_back({1,0});
		}
		else if(s[x]=='S'){
			dir[x].push_back({-1,0});
		}
		else if(s[x]=='W'){
			dir[x].push_back({0,1});
		}
		else if(s[x]=='E'){
			dir[x].push_back({0,-1});
		}
		else{
			dir[x].push_back({1,0});
			dir[x].push_back({-1,0});
			dir[x].push_back({0,1});
			dir[x].push_back({0,-1});
		}
	}
	
	memset(memo,-1,sizeof(memo));
	int counter=0;
	for(int x=0;x<n;x++){
		for(int y=0;y<m;y++){
			if(arr[x][y]=='#') continue;
			int add=dp(0,x,y);
			//show3(x,x,y,y,add,add);
			counter+=add;
		}
	}
	cout << counter;
}
 
int32_t main(){										
	ios::sync_with_stdio(0);	
	cin.tie(0);
	//freopen("redistricting.in", "r", stdin);
	//freopen("redistricting.out", "w", stdout);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}	
}

Subtask #1
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9308 KB Output is correct
2 Correct 3 ms 9436 KB Output is correct
3 Correct 2 ms 9564 KB Output is correct
4 Correct 2 ms 9428 KB Output is correct
5 Correct 2 ms 9308 KB Output is correct
6 Correct 2 ms 9308 KB Output is correct

Subtask #2
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9308 KB Output is correct
2 Correct 3 ms 9436 KB Output is correct
3 Correct 2 ms 9564 KB Output is correct
4 Correct 2 ms 9428 KB Output is correct
5 Correct 2 ms 9308 KB Output is correct
6 Correct 2 ms 9308 KB Output is correct
7 Correct 17 ms 9304 KB Output is correct
8 Correct 5 ms 9304 KB Output is correct
9 Correct 2 ms 9308 KB Output is correct
10 Correct 3 ms 9308 KB Output is correct
11 Correct 2 ms 9332 KB Output is correct
12 Correct 19 ms 9308 KB Output is correct
13 Correct 24 ms 9560 KB Output is correct
14 Correct 17 ms 9308 KB Output is correct
15 Correct 2 ms 9308 KB Output is correct
16 Correct 2 ms 9308 KB Output is correct
17 Correct 22 ms 9564 KB Output is correct
18 Correct 25 ms 9304 KB Output is correct
19 Correct 8 ms 9308 KB Output is correct
20 Correct 4 ms 9308 KB Output is correct
21 Correct 2 ms 9560 KB Output is correct

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9308 KB Output is correct
2 Correct 3 ms 9436 KB Output is correct
3 Correct 2 ms 9564 KB Output is correct
4 Correct 2 ms 9428 KB Output is correct
5 Correct 2 ms 9308 KB Output is correct
6 Correct 2 ms 9308 KB Output is correct
7 Correct 17 ms 9304 KB Output is correct
8 Correct 5 ms 9304 KB Output is correct
9 Correct 2 ms 9308 KB Output is correct
10 Correct 3 ms 9308 KB Output is correct
11 Correct 2 ms 9332 KB Output is correct
12 Correct 19 ms 9308 KB Output is correct
13 Correct 24 ms 9560 KB Output is correct
14 Correct 17 ms 9308 KB Output is correct
15 Correct 2 ms 9308 KB Output is correct
16 Correct 2 ms 9308 KB Output is correct
17 Correct 22 ms 9564 KB Output is correct
18 Correct 25 ms 9304 KB Output is correct
19 Correct 8 ms 9308 KB Output is correct
20 Correct 4 ms 9308 KB Output is correct
21 Correct 2 ms 9560 KB Output is correct
22 Runtime error 1 ms 860 KB Execution killed with signal 11
23 Halted 0 ms 0 KB -