제출 #544126

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
544126		Cookie197	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	708 ms	44548 KiB

dango_maker

// Cookie197 
// the people who invented competitive programming must be ******* crazy
// why am i still here suffering while i can do something else more valuable?
// WHY???
//#pragma GCC optimize("O4,unroll-loops,no-stack-protector")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<iomanip>
#include<math.h>
#include<unordered_map>
#include<numeric>
#include<random>
using namespace std;
#define Why_does_competitive_programming_even_exist ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define pii pair<ll,ll>
#define pdd pair<double ,double>
#define mp make_pair
//#define mod 998244353
#define mod 1000000007
#define endl "\n"
#define inf (ll)5e18
#define out(x) cout << #x << " = " << x <<endl;
#define out2(a,b) cout<< #a << "[" << b << "]" << " = " << a[b] << endl;
#define outp(x) cout << #x << " first = " << x.first << "  second = " << x.second << endl

// 以斜排來看，不論怎麼選，RGW都是「第i斜排，第i+1斜排，第i+2斜排」
// 所以，不同斜排（不同i）的串，是完全獨立的
// 對每個斜排，都做一個dp，再把每一斜排的答案加起來

// 對每個斜排，由左下到右上，考慮G
// 每個G可以選擇：不選(0) 選上下i-1,i,i+1(1) 選左右j-1,j,j+1(2)
int dp[3005][3];
int arr[3005][3005];
int n,m,rcnt;
vector<pii> R;
int ans;

signed main(){
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++){
            char c; cin>>c;
            if (c=='R') arr[i][j] = 1;
            if (c=='G') arr[i][j] = 2;
            if (c=='W') arr[i][j] = 3;
        }
    }

    for (int z=2;z<=n+m;z++){
        int now = 0;
        for (int i=1;i<=n;i++) dp[i][0] = dp[i][1] = dp[i][2] = 0;
        for (int i=1;i<=n;i++){
            int j = z-i;
            if (j<=0 || j>m) continue;

            dp[i][0] = max(dp[i-1][0], max(dp[i-1][1], dp[i-1][2]));
            if (arr[i][j] == 2 && arr[i-1][j] == 1 && arr[i+1][j] == 3){
                dp[i][1] = max(dp[i-1][0], dp[i-1][1]) + 1;
            }
            if (arr[i][j] == 2 && arr[i][j-1] == 1 && arr[i][j+1] == 3){
                dp[i][2] = max(dp[i-1][0], dp[i-1][2]) + 1;
            }

            now = max(now, max(max(dp[i][0], dp[i][1]),dp[i][2]));
        }
        ans += now;
    }

    cout<<ans<<endl;
}

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