Submission #1151930

#	Time	Username	Problem	Language	Result	Execution time	Memory
1151930		koukirocks	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	175 ms	9408 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>>;

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

int main() {
    speed;
    // freopen("C:\\Users\\UM3504DA\\Desktop\\statement\\2018-ho-data\\2018-ho-t3\\in\\03-06.txt","r",stdin);
    cin>>n>>m;
    for (ll i=1;i<=n;i++) {
        for (ll j=1;j<=m;j++) {
            cin>>mp[i][j];
        }
    }
    ll ans=0;
    for (ll t=3;t<=n+m-1;t++) {
        for (ll 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;
        int cnt=0;
        for (ll i=max(1ll,t-n);i<=t-1 and i<=m;i++) {
            cnt++;
            a[cnt][0]=max({a[cnt-1][0],a[cnt-1][1],a[cnt-1][2]});
            ll x=t-i,y=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[cnt][1]=max(a[cnt-1][0],a[cnt-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[cnt][2]=max(a[cnt-1][0],a[cnt-1][2])+1;
            }
        }
        ans+=max({a[cnt][0],a[cnt][1],a[cnt][2]});
    }
    cout<<ans<<"\n";
    return 0;
}

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