Submission #442782

#	Time	Username	Problem	Language	Result	Execution time	Memory
442782		Fidisk	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	396 ms	262148 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
 
#define oo 1e9
#define fi first
#define se second
#define sp(iiii) setprecision(iiii)
#define IO ios_base::sync_with_stdio(false); cin.tie(0)
#define ms(aaaa,xxxx) memset(aaaa,xxxx,sizeof(aaaa))
#define cntbit(xxxx) __builtin_popcount(xxxx)
#define getbit(xxxx,aaaa) (((xxxx)>>(aaaa-1))&1)
 
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pair<int,int>,int> piii;
typedef pair<pair<int,int>,pair<int,int>> piiii;
typedef pair<long long,long long> pll;
typedef pair<pair<long long,long long>,long long> plll;
typedef pair<pair<long long,long long>,pair<long long,long long>> pllll;
typedef pair<pair<long long,long long>,bool> pllb;
typedef pair<long double,long double> pld;
typedef pair<pair<long double,long double>,long double> plld;
 
const ll base=2e9+4257;
//const ll mod=1e9+7;
const ll mod2=1e9+4233;
const ld eps=1e-12;
const ll maxn=1e16;
const ld pi=acos(-1);
const ll delta=1e5+7;
const int dx[4]={1,-1,0,0};
const int dy[4]={0,0,1,-1};
 
char a[3009][3009];
ll f[3009][3009][4],i,j,n,m,ans;
 
bool check(ll x,ll y) {
    return ((a[x][y]=='G')&&(a[x-1][y]=='R')&&(a[x+1][y]=='W'));
}
 
bool check2(ll x,ll y) {
    return ((a[x][y]=='G')&&(a[x][y-1]=='R')&&(a[x][y+1]=='W'));
}
 
int main(){
    IO;
    cin>>n>>m;
    for (i=1;i<=n;i++) {
        for (j=1;j<=m;j++) {
            cin>>a[i][j];
        }
    }
    for (i=1;i<=n;i++) {
        for (j=1;j<=m;j++) {
            f[i][j][0]=max(f[i][j][0],f[i-1][j+1][0]);
            f[i][j][0]=max(f[i][j][0],f[i-1][j+1][1]);
            f[i][j][0]=max(f[i][j][0],f[i-1][j+1][2]);
            if (check(i,j)) {
                f[i][j][1]=max(f[i-1][j+1][0],f[i-1][j+1][1])+1;
            }
            if (check2(i,j)) {
                f[i][j][2]=max(f[i-1][j+1][0],f[i-1][j+1][2])+1;
            }
        }
    }
    for (i=1;i<=n;i++) {
        ans+=max({f[i][1][0],f[i][1][1],f[i][1][2]});
    }
    for (i=2;i<=m;i++) {
        ans+=max({f[n][i][0],f[n][i][1],f[n][i][2]});
    }
    cout<<ans<<'\n';
}

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