Submission #880768

#	Time	Username	Problem	Language	Result	Execution time	Memory
880768		niter	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	614 ms	142044 KiB

dango_maker

#include <bits/stdc++.h>
#define loop(i,a,b) for(int i = (a); i < (b); i ++)
#define pb push_back
#define ins insert
#define pii pair<int,int>
#define ff first
#define ss second
#define op(x) cerr << #x << " = " << x << endl;
#define opa(x) cerr << #x << " = " << x << ", ";
#define ops(x) cerr << x;
#define entr cerr << endl;
#define spac cerr << ' ';
#define STL(x) cerr << #x << " : "; for(auto &qwe:x) cerr << qwe << ' '; cerr << endl;
#define ARR(x, nnn) cerr << #x <<  " : "; loop(qwe,0,nnn) cerr << x[qwe] << ' '; cerr << endl;
#define BAE(x) x.begin(), x.end()
#define unilize(x) x.resize(unique(BAE(x)) - x.begin())
#define unisort(x) sort(BAE(x)); unilize(x);
using namespace std;
typedef long long ll;

const int mxn = 3010;
char c[mxn][mxn];
bool canr[mxn][mxn], cand[mxn][mxn];
int dpr[mxn][mxn], dpd[mxn][mxn], dp[mxn][mxn];

int n, m;
inline bool check(int i, int j){
    return i >= 0 && i < n && j >= 0 && j < m;
}
int main(){
//    freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    loop(i,0,n){
        loop(j,0,m){
            cin >> c[i][j];
        }
    }
    int now = 0;
    loop(i,0,n){
        loop(j,0,m){
            if(check(i, j - 1))
            if(c[i][j-1] == 'R' && c[i][j] == 'G' && c[i][j+1] == 'W'){
                canr[i][j] = true;
            }
            if(check(i-1, j))
            if(c[i-1][j] == 'R' && c[i][j] == 'G' && c[i+1][j] == 'W'){
                cand[i][j] = true;
            }
        }
    }
    int ans = 0;
    loop(k,0,n){
        for(int i = k, j = 0; i >= 0 && j < m; i --, j++){
            if(canr[i][j]){
                if(check(i + 1, j - 1)){
                    dpr[i][j] = max(dpr[i+1][j-1], dp[i+1][j-1]);
                }
                dpr[i][j]++;
            }
            if(cand[i][j]){
                if(check(i + 1, j - 1)){
                    dpd[i][j] = max(dpd[i+1][j-1], dp[i+1][j-1]);
                }
                dpd[i][j]++;
            }
            if(check(i + 1, j - 1)){
                dp[i][j] = max({dpd[i+1][j-1], dp[i+1][j-1], dpr[i+1][j-1]});
            }
        }
    }
    loop(k,1,m){
        for(int i = n - 1, j = k; i >= 0 && j < m; i --, j++){
            if(canr[i][j]){
                if(check(i + 1, j - 1)){
                    dpr[i][j] = max(dpr[i+1][j-1], dp[i+1][j-1]);
                }
                dpr[i][j]++;
            }
            if(cand[i][j]){
                if(check(i + 1, j - 1)){
                    dpd[i][j] = max(dpd[i+1][j-1], dp[i+1][j-1]);
                }
                dpd[i][j]++;
            }
            if(check(i + 1, j - 1)){
                dp[i][j] = max({dpd[i+1][j-1], dp[i+1][j-1], dpr[i+1][j-1]});
            }
        }
    }
    loop(j,0,m){
        ans += max({dp[0][j], dpr[0][j], dpd[0][j]});
    }
    loop(i,1,n){
        ans += max({dp[i][m-1], dpr[i][m-1], dpd[i][m-1]});
    }
//    loop(i,0,n){
//        loop(j,0,m){
//            ops("(") ops(dp[i][j]) ops(", ")
//            ops(dpd[i][j]) ops(", ")
//            ops(dpr[i][j]) ops(") ")
//        } entr
//    }
    cout << ans << '\n';
}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:39:9: warning: unused variable 'now' [-Wunused-variable]
   39 |     int now = 0;
      |         ^~~

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