Submission #1180380

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180380		Zbyszek99	Dango Maker (JOI18_dango_maker)	C++20	100 / 100	233 ms	44572 KiB

dango_maker

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ff first
#define ss second
#define vl vector<long long>
#define vi vector<int>
#define pii pair<int,int>
#define pll pair<long long, long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
//mt19937 mt;void random(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll rand(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

int arr[3002][3002];
bool odw[3002][3002];
int dp[3002][2][2];

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //random();
    int n,m;
    cin >> n >> m;
    rep2(i,0,n+1) rep2(j,0,m+1) arr[i][j] = -1;
    rep2(i,1,n) rep2(j,1,m)
    {
        char z;
        cin >> z;
        if(z == 'R') arr[i][j] = 1;
        else if(z == 'G') arr[i][j] = 2;
        else arr[i][j] = 3;
    }
    int ans = 0;
    rep2(i,1,n) rep2(j,1,m)
    {
        if(odw[i][j]) continue;
        int cur = 0;
        while(arr[i+cur][j-cur] == 2)
        {
            odw[i+cur][j-cur] = 1;
            cur++;
        }
        if(cur != 0)
        {
     //       cout << i << " " << j << " " << cur << " dir\n";
            rep(d1,2)
            {
                rep(d2,2)
                {
                    dp[0][d1][d2] = max((arr[i][j-1] == 1 && arr[i][j+1] == 3 && d1 == 0 ? 1 : 0),(arr[i-1][j] == 1 && arr[i+1][j] == 3 && d2 == 0 ? 1 : 0));
                }
            }
            rep2(d,1,cur-1)
            {
                rep(d1,2)
                {
                    rep(d2,2)
                    {
                        dp[d][d1][d2] = max({dp[d-1][0][0],dp[d-1][1][0],dp[d-1][0][1],dp[d-1][1][1]});
                        if(arr[i+d][j-d-1] == 1 && arr[i+d][j-d+1] == 3 && d1 == 0) dp[d][d1][d2] = max({dp[d][d1][d2],dp[d-1][0][1]+1,dp[d-1][1][1]+1});
                        if(arr[i+d-1][j-d] == 1 && arr[i+d+1][j-d] == 3 && d2 == 0) 
                        {
                            //cout << "Xd\n";
                            dp[d][d1][d2] = max({dp[d][d1][d2],dp[d-1][1][0]+1,dp[d-1][1][0]+1});
                        }
                  //      cout << dp[d][d1][d2] << " " << d1 << " " << d2 << " " << d << " dp\n";
                    }
                }
            }
          //  cout << max({dp[cur-1][0][0],dp[cur-1][1][0],dp[cur-1][1][1],dp[cur-1][0][1]}) << " add\n";
            ans += max({dp[cur-1][0][0],dp[cur-1][1][0],dp[cur-1][1][1],dp[cur-1][0][1]});
        }
    }
    cout << ans << "\n";
}

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