oj.uz

Submission #678599

# Submission time Handle Problem Language Result Execution time Memory
678599 2023-01-06T08:20:02 Z vjudge1 Dango Maker (JOI18_dango_maker) C++17
0 / 100
 1 ms 340 KB 
#include<bits/stdc++.h>
using namespace std;
int dp[3010][5];
pair <bool,bool>  tmp[3010];    int n,m;
int get(int x,int y){
    if (x < 0)x = 0;
    if (y < 0)y = 0;
    if (x <= 0 && y <= 0)return 0;
    int res = -1;int r = x - y + 2;
    if (dp[x][r] != -1)return dp[x][r];
    if (x <= 0){
        res = get(x,y-1) + tmp[y].second;
    }
    else if (y <= 0){
        res = get(x-1,y) + tmp[x].second;
    }
    else{
        if (x >= y){
            res = get(x-1,y);
            if (tmp[x].first){
                res = max(res,1 + get(x-1,y-3));
            }
        }
        else{
            res = get(x,y-1);
            if (tmp[y].second){
                res = max(res,1 + get(x-3,y-1));
            }
        }
    }
    dp[x][r] = res;
    return res;
}
int solve(){
    memset(dp,-1,sizeof dp);
    return get(n,n);
}
char a[3010][3010];
int main(){

    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>m;
    for (int i = 1;i <= n;i ++){
        string s;
        cin>>s;
        for (int j = 1;j <= m;j ++){
            a[i][j] = s[j-1];
        }
    }
    int ans = 0;
    for (int k = 2;k <= n + m;k ++){
        for (int i =1 ;i <= n;i ++){
            int j = k - i;
            if (1 <= j && j <= m){
                tmp[i].first = (a[i][j] == 'R' && a[i][j+1] == 'G' && a[i][j+2] == 'W');
                tmp[i].second = (a[i][j] == 'R' && a[i+1][j] == 'G' && a[i+2][j] == 'W');
            }
            else{
                tmp[i] = {0,0};
            }

        }
        ans += solve();
    }
    cout<<ans<<'\n';
    return 0;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Incorrect 0 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Incorrect 0 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Incorrect 0 ms 340 KB Output isn't correct
7 Halted 0 ms 0 KB -