# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
132078 | 2019-07-18T09:36:40 Z | youssefbou62 | Nautilus (BOI19_nautilus) | C++14 | 266 ms | 158840 KB |
#pragma GCC optimize("Ofast") #pragma GCC target("sse4") #include <bits/stdc++.h> using namespace std; #define mp make_pair #define fi first #define se second #define all(v) v.begin(),v.end() #define allarr(a) a , a + n #define ll long long #define ull unsigned long long #define pb push_back #define fastio ios_base::sync_with_stdio(false) ; cin.tie(NULL); cout.tie(NULL) typedef pair<int, int> pi; typedef pair<ll,ll> pll; typedef pair<int,pi> trp ; typedef vector<pi> vpi; typedef vector<pll> vpll ; // int ab (int x ) { return (x>0?x:-x); } const int N = 505 , M = 5005 ; int R , C , m ; bitset<N> dp[M][N] , a[N]; string seq ; void direction(int& i, int& j , char c ){ if( c =='N'){ i-- ; }else if( c =='S'){ i++; }else if( c =='E'){ j++ ; }else if( c =='W'){ j--; } } bool valid (int i , int j ){ return ( i >= 0 && j >= 0 && i < R && j < C && a[i][j]!='#') ; } int main(){ scanf("%d%d%d\n",&R,&C,&m); for(int i = 0 ; i < R ; i++ ){ for(int j = 0 ; j < C ; j++ ){ char c ; scanf(" %c",&c); a[i][j] = (c=='.') ; } } for(int i = 0 ; i < R ; i++ ){ for(int j = 0 ; j < C ; j++ ) dp[0][i][j] = a[i][j]; } cin >> seq ; string dir = "NSWE"; for(int moves = 0 ; moves < m ; moves++){ for(int i=0 ; i < R ; i++ ){ char c = seq[moves] ; if( (c=='N' || c=='?') && i ){ dp[moves+1][i-1] = (dp[moves][i]|dp[moves+1][i-1])&a[i-1]; }if(c=='S'|| c=='?'){ dp[moves+1][i+1] = (dp[moves][i]|dp[moves+1][i+1])&a[i+1]; }if(c=='E'|| c=='?'){ dp[moves+1][i] = (dp[moves+1][i]|(dp[moves][i]<<1))&a[i]; }if( c=='W' || c=='?'){ dp[moves+1][i] = (dp[moves+1][i]|(dp[moves][i]>>1))&a[i]; } } } int ans = 0 ; for(int i = 0 ; i < R ; i++ )ans += dp[m][i].count(); cout << ans << endl ; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1400 KB | Output is correct |
2 | Correct | 4 ms | 1400 KB | Output is correct |
3 | Correct | 4 ms | 1400 KB | Output is correct |
4 | Correct | 4 ms | 1400 KB | Output is correct |
5 | Correct | 4 ms | 1400 KB | Output is correct |
6 | Correct | 4 ms | 1400 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1400 KB | Output is correct |
2 | Correct | 4 ms | 1400 KB | Output is correct |
3 | Correct | 4 ms | 1400 KB | Output is correct |
4 | Correct | 4 ms | 1400 KB | Output is correct |
5 | Correct | 4 ms | 1400 KB | Output is correct |
6 | Correct | 4 ms | 1400 KB | Output is correct |
7 | Correct | 4 ms | 1400 KB | Output is correct |
8 | Correct | 4 ms | 1400 KB | Output is correct |
9 | Correct | 4 ms | 1400 KB | Output is correct |
10 | Correct | 4 ms | 1400 KB | Output is correct |
11 | Correct | 4 ms | 1400 KB | Output is correct |
12 | Correct | 5 ms | 1400 KB | Output is correct |
13 | Correct | 4 ms | 1400 KB | Output is correct |
14 | Correct | 4 ms | 1400 KB | Output is correct |
15 | Correct | 4 ms | 1332 KB | Output is correct |
16 | Correct | 4 ms | 1400 KB | Output is correct |
17 | Correct | 4 ms | 1400 KB | Output is correct |
18 | Correct | 4 ms | 1400 KB | Output is correct |
19 | Correct | 4 ms | 1400 KB | Output is correct |
20 | Correct | 4 ms | 1400 KB | Output is correct |
21 | Correct | 5 ms | 1400 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 1400 KB | Output is correct |
2 | Correct | 4 ms | 1400 KB | Output is correct |
3 | Correct | 4 ms | 1400 KB | Output is correct |
4 | Correct | 4 ms | 1400 KB | Output is correct |
5 | Correct | 4 ms | 1400 KB | Output is correct |
6 | Correct | 4 ms | 1400 KB | Output is correct |
7 | Correct | 4 ms | 1400 KB | Output is correct |
8 | Correct | 4 ms | 1400 KB | Output is correct |
9 | Correct | 4 ms | 1400 KB | Output is correct |
10 | Correct | 4 ms | 1400 KB | Output is correct |
11 | Correct | 4 ms | 1400 KB | Output is correct |
12 | Correct | 5 ms | 1400 KB | Output is correct |
13 | Correct | 4 ms | 1400 KB | Output is correct |
14 | Correct | 4 ms | 1400 KB | Output is correct |
15 | Correct | 4 ms | 1332 KB | Output is correct |
16 | Correct | 4 ms | 1400 KB | Output is correct |
17 | Correct | 4 ms | 1400 KB | Output is correct |
18 | Correct | 4 ms | 1400 KB | Output is correct |
19 | Correct | 4 ms | 1400 KB | Output is correct |
20 | Correct | 4 ms | 1400 KB | Output is correct |
21 | Correct | 5 ms | 1400 KB | Output is correct |
22 | Correct | 243 ms | 158812 KB | Output is correct |
23 | Correct | 232 ms | 158812 KB | Output is correct |
24 | Correct | 231 ms | 158708 KB | Output is correct |
25 | Correct | 241 ms | 158840 KB | Output is correct |
26 | Correct | 246 ms | 158760 KB | Output is correct |
27 | Correct | 255 ms | 158748 KB | Output is correct |
28 | Correct | 250 ms | 158752 KB | Output is correct |
29 | Correct | 251 ms | 158680 KB | Output is correct |
30 | Correct | 249 ms | 158712 KB | Output is correct |
31 | Correct | 250 ms | 158712 KB | Output is correct |
32 | Correct | 263 ms | 158712 KB | Output is correct |
33 | Correct | 264 ms | 158712 KB | Output is correct |
34 | Correct | 266 ms | 158716 KB | Output is correct |
35 | Correct | 262 ms | 158708 KB | Output is correct |
36 | Correct | 263 ms | 158788 KB | Output is correct |