Submission #1264548

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264548		pudelos	Dango Maker (JOI18_dango_maker)	C++20	33 / 100	563 ms	266008 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, a, b) for(int i=a; i<=b; ++i)
#define sz(A) (int)(A.size())
#define ll long long
#define eb emplace_back
#define pb push_back
#define pi pair<int, int>
#define f first
#define s second
#define rs resize
#define V vector

const int maxn=3e3+3;

int n, m;
int A[maxn][maxn];
bool poz[maxn][maxn], pio[maxn][maxn];
V<pi> wspol[2*maxn];
int dp[maxn][3];

signed main() {
  cin.tie(0) -> ios_base::sync_with_stdio(0);
  cin >> n >> m;
  FOR(i, 1, n) {
    FOR(j, 1, m) {
      wspol[i+j].pb({i, j});
      char typ;
      cin >> typ;
      int a=0;
      if(typ=='R') a=1;
      if(typ=='G') a=2;
      if(typ=='W') a=3;
      A[i][j]=a;
    }
  }
  FOR(i, 1, 2*maxn-1) reverse(wspol[i].begin(), wspol[i].end());

  FOR(i, 1, n) FOR(j, 1, m) {
    if(A[i][j]!=2) continue;
    if(A[i][j-1]==1 && A[i][j+1]==3) poz[i][j]=1;
    if(A[i-1][j]==1 && A[i+1][j]==3) pio[i][j]=1;
  }

  int odp=0;
  FOR(S, 2, n+m) {
    if(sz(wspol[S])==0) continue;
    FOR(i, 0, maxn-1) FOR(j, 0, 2) dp[i][j]=0;
    int w=0;
    FOR(i, 1, sz(wspol[S])) {
      auto [ii, jj] = wspol[S][i-1];
      dp[i][0]=max({dp[i-1][0], dp[i-1][1], dp[i-1][2]});
      if(pio[ii][jj]) dp[i][1]=max(dp[i-1][0], dp[i-1][1])+1;
      if(poz[ii][jj]) dp[i][2]=max(dp[i-1][0], dp[i-1][2])+1;
      w=max({w, dp[i][0], dp[i][1], dp[i][2]});
    }
    odp+=w;
  }
  cout << odp << '\n';
}

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