Submission #1151926

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151926		koukirocks	Dango Maker (JOI18_dango_maker)	C++20	33 / 100	108 ms	9316 KiB

dango_maker

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx,avx2")
//#pragma GCC target("popcnt")
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MAX=2e5+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;
const ldb PI=acos(-1.0);
const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
template<typename T>
using vvector = vector<vector<T>>;

int n,m;
char mp[3010][3010];
int a[6010][3];

int main() {
    speed;
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            cin>>mp[i][j];
        }
    }
    ll ans=0;
    for (int t=3;t<=n+m-1;t++) {
        // vvector<int> a(t+1,vector<int>(3,-INF));
        for (int i=1;i<=t;i++) {
            a[i][0]=-INF;
            a[i][1]=-INF;
            a[i][2]=-INF;
        }
        a[0][0]=a[0][1]=a[0][2]=0;
        for (int i=1;i<=t;i++) {
            a[i][0]=max({a[i-1][0],a[i-1][1],a[i-1][2]});
            int x=i,y=t-i;
            if (1<x and x<n) {
                if (mp[x-1][y]=='R' and mp[x][y]=='G' and mp[x+1][y]=='W') a[i][1]=max(a[i-1][0],a[i-1][1])+1;
            }
            if (1<y and y<m) {
                if (mp[x][y-1]=='R' and mp[x][y]=='G' and mp[x][y+1]=='W') a[i][2]=max(a[i-1][0],a[i-1][2])+1;
            }
        }
        ans+=max({a[t][0],a[t][1],a[t][2]});
    }
    cout<<ans<<"\n";
    return 0;
}

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