Submission #167347

#TimeUsernameProblemLanguageResultExecution timeMemory
167347cbertramDango Maker (JOI18_dango_maker)C++14
100 / 100
564 ms195340 KiB
#include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef vector<bool> vb; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<pii> vpii; typedef vector<pll> vpll; typedef vector<string> vs; typedef vector<vb> vvb; typedef vector<vi> vvi; typedef vector<vll> vvll; #define all(x) x.begin(), x.end() #define rep(i,a,b) for(int i = a; i < b; i++) int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N, M; cin >> N; cin >> M; vector<string> board(N); rep(n,0,N) cin >> board[n]; vi Ns(N*M); vi Ms(N*M); int i = 0; rep(dist,0,N+M) { for(int m = max(0,dist-N+1); m <= min(dist,M-1); m++, i++) { int n = dist-m; Ns[i] = n; Ms[i] = m; } } vi best(N*M*3); for(i = 0; i < N*M; i++) { int n = Ns[i]; int m = Ms[i]; if(i > 0) { best[i] = best[i-1]; best[i+N*M] = best[i-1]; best[i+2*N*M] = max(best[i-1+N*M], best[i-1+2*N*M]); if(m == 0 || n == N-1) best[i+2*N*M] = max(best[i+2*N*M], best[i-1]); } if(n+2 < N && board[n][m] == 'R' && board[n+1][m] == 'G' && board[n+2][m] == 'W') { // vertical if(i == 0) best[i] = best[i+N*M] = best[i+2*N*M] = 1; if(i-1 >= 0 && (m == 0 || n == N-1)) best[i+2*N*M] = best[i-1]+1; if(i-1 >= 0 && m-1 >= 0 && n+1 < N) best[i+2*N*M] = max(best[i+2*N*M], best[i-1+2*N*M]+1); if(i-2 >= 0 && m-2 >= 0 && n+2 < N) best[i+2*N*M] = max(best[i+2*N*M], best[i-2+N*M]+1); if(i-3 >= 0 && m-3 >= 0 && n+3 < N) best[i+2*N*M] = max(best[i+2*N*M], best[i-3]+1); } if(m+2 < M && board[n][m] == 'R' && board[n][m+1] == 'G' && board[n][m+2] == 'W') { // horizontal if(i == 0) best[i] = 1; else if(m-0 >= 0 && n+0 < N) best[i] = max(best[i], best[i-1]+1); } best[i+N*M] = max(best[i+N*M], best[i+2*N*M]); best[i] = max(best[i], best[i+N*M]); } cout << best[N*M-1] << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...