Submission #1090830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090830		ivan_alexeev	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	575 ms	45120 KiB

dango_maker

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;

#ifdef lisie_bimbi
#else
#define endl '\n'
#endif
typedef long long ll;

const ll inf = 1'000'000'000'000'000'000;

using namespace std;

#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,bmi2,fma,popcnt")


//#define int long long
int n, m;
vector<vector<int>> z;

bool get(int x, int y, bool f){
    if((x >= 0) && (x < n) && (y >= 0) && (y < m)){

    }else{
        return 0;
    }
    if(f){
        if(x + 2 < n){
            return ((z[x][y] == 0) && (z[x + 1][y] == 1) && (z[x + 2][y] == 2));
        }else{
            return 0;
        }
    }else{
        if(y + 2 < m){
            return ((z[x][y] == 0) && (z[x][y + 1] == 1) && (z[x][y + 2] == 2));
        }else{
            return 0;
        }
    }
}

int solve1(vector<int> a, vector<int> b){
    /*
    for(auto i : a){
        cout << i << " ";
    }
    cout << endl;
    for(auto i : b){
        cout << i << " ";
    }
    cout << endl;
    cout << endl;
     */
    int n = a.size();
    vector<vector<int>> dp(n + 1, vector<int>(3));
    dp[0] = {0, 0, 0};
    for(int i = 0; i < n; i++){
        dp[i + 1][0] = dp[i][0];
        dp[i + 1][1] = dp[i][0];
        dp[i + 1][2] = dp[i][1];
        if(b[i]){
            dp[i + 1][0] = max(dp[i + 1][0], dp[i][0] + 1);
        }
        if(a[i]){
            dp[i + 1][0] = max(dp[i + 1][0], dp[i][2] + 1);
            dp[i + 1][1] = max(dp[i + 1][1], dp[i][2] + 1);
            dp[i + 1][2] = max(dp[i + 1][2], dp[i][2] + 1);
        }
    }
    return dp.back()[0];
}

void solve(){
    cin >> n >> m;
    z.resize(n, vector<int>(m));
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        for(int j = 0; j < m; j++){
            if(s[j] == 'R'){
                z[i][j] = 0;
            }else if(s[j] == 'G'){
                z[i][j] = 1;
            }else{
                z[i][j] = 2;
            }
        }
    }
    int ans = 0;
    for(int sum = 0; sum < n + m - 1; sum++){
        vector<int> a, b;
        for(int j = 0; j < m; j++){
            int i = sum - j;
            if((i >= 0) && (i < n)){
                a.push_back(get(i, j, 1));
                b.push_back(get(i, j, 0));
            }
        }
        ans += solve1(a, b);
    }
    cout << ans << endl;
}

signed main(){
#ifdef lisie_bimbi
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    cin.tie(nullptr)->sync_with_stdio(false);
#endif
    cout << setprecision(5) << fixed;
    int _ = 1;
    //cin >> t;
    while(_--){
        solve();
    }
    return 0;
}

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