Submission #670209

#	Time	Username	Problem	Language	Result	Execution time	Memory
670209		Quan2003	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	783 ms	21000 KiB

dango_maker

#include <bits/stdc++.h>
#include <iostream>
#include<queue>
#include<vector>
#include<utility>
using namespace std;
typedef long long ll;
const int sz=2e5+1;
const int sz1=1e3+10;
const int mod = 2111992;
int n,m;
char g[4000][4001];
char d[3][4001];
int dp[3][4001];
int main(){
     cin>>n>>m;
     for(int i = 0; i < n; i++){
         for(int j = 0; j < m; j++){
              cin>>g[i][j];
         }
     }
     int ans = 0;
     for(int i = 1; i < n + m - 2; i++){
       for(int j = 0; j < 3; j++){
                 for(int k = 0; k < 4000; k++) d[j][k] = '?';
          
       }
       for(int j = 0; j < 3; j++){
                for(int k = 0; k < m; k++){
                      int r = i + j - k - 1;
                      int c = k;
                      if(r < 0 or r>=n) continue;
                      d[j][k] = g[r][c];
                }
        }
        for(int j = 0; j < 3; j++){
               for(int k = 0; k < 4000; k++) dp[j][k] = 0;
        }
        for(int j = 0; j < m; j++){
           for(int k = 0; k < 3; k++){
              dp[0][j + 1] = max(dp[0][j + 1], dp[k][j]);
              if(d[1][j] != 'G') continue;
              if(j > 0 and k!= 1 and d[0][j - 1] == 'R' and d[2][j + 1] == 'W'){
                dp[2][j + 1] = max(dp[2][j + 1],dp[k][j] + 1);
              }
              if(k != 2 and d[0][j] == 'R' and d[2][j] == 'W'){
                dp[1][j + 1] = max(dp[1][j + 1],dp[k][j] + 1);
              }
           }
        }
       ans += max(dp[0][m],max(dp[1][m],dp[2][m]));
    }
    cout<<ans<<endl;
}
       
  

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 67 / 67