Submission #254630

#	Time	Username	Problem	Language	Result	Execution time	Memory
254630		Atill83	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	294 ms	27004 KiB

dango_maker

#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 3e3+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll n, m;
char gr[MAXN][MAXN];

vector<int> adj[MAXN];
bool done[MAXN][MAXN];
int lst[3][2];


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n>>m;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin>>gr[i][j];
            if(gr[i][j] != 'G') done[i][j] = 1;
        }
    }
    int cnt = 0;

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(done[i][j] == 1) continue;
            if(gr[i][j] == 'G'){
                int curi = i, curj = j;
                while(curj > 1 && curi < n && gr[curi + 1][curj - 1] == 'G'){
                    curj--;
                    curi++;
                }
                int idx = 0;
                memset(lst, 0, sizeof(lst));
                while(curj <= m && curi >= 1 && gr[curi][curj] == 'G'){
                    done[curi][curj] = 1;
                    
                    lst[idx][0] = max(lst[(idx + 1) % 3][1], lst[(idx + 2) % 3][0]);
                    if(gr[curi - 1][curj] == 'R' && gr[curi + 1][curj] == 'W'){
                        lst[idx][0]++;
                    }

                    lst[idx][1] = max(lst[(idx + 1) % 3][0], lst[(idx + 2) % 3][1]);

                    if(gr[curi][curj - 1] == 'R' && gr[curi][curj + 1] == 'W') 
                        lst[idx][1]++;
                    curj++;
                    curi--;
                    idx ++;
                    idx %= 3;
                }
                idx = (idx + 2) % 3;

                cnt += max(lst[idx][0], lst[idx][1]);

            }else{
                done[i][j] = 1;
            }

        }
    }
    


    cout<<cnt<<endl;





    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

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