oj.uz

답안 #484497

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
484497 2021-11-03T19:08:36 Z MilosMilutinovic Nautilus (BOI19_nautilus) C++14
66 / 100
 1000 ms 141712 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

const int N=505;
int n,m,k,g[N][N];
char s[N],pt[N*10];
map<int,bool> dp[N][N];
bool valid(int x,int y) {
	return x>=1&&x<=n&&y>=1&&y<=m;
}
bool gao(int i,int j,int x) {
	if (!valid(i,j)||g[i][j]==0) return false;
	if (x==0) { return true; }
	if (dp[i][j].count(x)) return dp[i][j][x];
	bool ok=false;
	if (pt[x]=='N'||pt[x]=='?') ok|=gao(i+1,j,x-1);
	if (pt[x]=='S'||pt[x]=='?') ok|=gao(i-1,j,x-1);
	if (pt[x]=='W'||pt[x]=='?') ok|=gao(i,j+1,x-1);
	if (pt[x]=='E'||pt[x]=='?') ok|=gao(i,j-1,x-1);
	dp[i][j][x]=ok;
	return ok;
}
int main() {
	scanf("%d%d%d",&n,&m,&k);
	rep(i,1,n+1) {
		scanf("%s",s+1);
		rep(j,1,m+1) g[i][j]=(s[j]=='.'?1:0);
	}
	scanf("%s",pt+1);
	int ans=0;
	rep(i,1,n+1) rep(j,1,m+1) ans+=(gao(i,j,k)?1:0);
	printf("%d",ans);
}

Compilation message

nautilus.cpp: In function 'int main()':
nautilus.cpp:42:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |  scanf("%d%d%d",&n,&m,&k);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
nautilus.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |   scanf("%s",s+1);
      |   ~~~~~^~~~~~~~~~
nautilus.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  scanf("%s",pt+1);
      |  ~~~~~^~~~~~~~~~~

Subtask #1
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 54332 KB Output is correct
2 Correct 17 ms 16716 KB Output is correct
3 Correct 10 ms 14072 KB Output is correct
4 Correct 7 ms 12748 KB Output is correct
5 Correct 7 ms 12596 KB Output is correct
6 Correct 6 ms 12492 KB Output is correct

Subtask #2
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 54332 KB Output is correct
2 Correct 17 ms 16716 KB Output is correct
3 Correct 10 ms 14072 KB Output is correct
4 Correct 7 ms 12748 KB Output is correct
5 Correct 7 ms 12596 KB Output is correct
6 Correct 6 ms 12492 KB Output is correct
7 Correct 235 ms 58308 KB Output is correct
8 Correct 35 ms 19256 KB Output is correct
9 Correct 9 ms 13456 KB Output is correct
10 Correct 7 ms 12844 KB Output is correct
11 Correct 6 ms 12492 KB Output is correct
12 Correct 407 ms 59296 KB Output is correct
13 Correct 222 ms 46964 KB Output is correct
14 Correct 116 ms 33960 KB Output is correct
15 Correct 11 ms 13644 KB Output is correct
16 Correct 6 ms 12620 KB Output is correct
17 Correct 475 ms 59540 KB Output is correct
18 Correct 255 ms 50240 KB Output is correct
19 Correct 72 ms 28932 KB Output is correct
20 Correct 25 ms 18148 KB Output is correct
21 Correct 7 ms 12620 KB Output is correct

Subtask #3
0 / 34.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 54332 KB Output is correct
2 Correct 17 ms 16716 KB Output is correct
3 Correct 10 ms 14072 KB Output is correct
4 Correct 7 ms 12748 KB Output is correct
5 Correct 7 ms 12596 KB Output is correct
6 Correct 6 ms 12492 KB Output is correct
7 Correct 235 ms 58308 KB Output is correct
8 Correct 35 ms 19256 KB Output is correct
9 Correct 9 ms 13456 KB Output is correct
10 Correct 7 ms 12844 KB Output is correct
11 Correct 6 ms 12492 KB Output is correct
12 Correct 407 ms 59296 KB Output is correct
13 Correct 222 ms 46964 KB Output is correct
14 Correct 116 ms 33960 KB Output is correct
15 Correct 11 ms 13644 KB Output is correct
16 Correct 6 ms 12620 KB Output is correct
17 Correct 475 ms 59540 KB Output is correct
18 Correct 255 ms 50240 KB Output is correct
19 Correct 72 ms 28932 KB Output is correct
20 Correct 25 ms 18148 KB Output is correct
21 Correct 7 ms 12620 KB Output is correct
22 Execution timed out 1087 ms 141712 KB Time limit exceeded
23 Halted 0 ms 0 KB -