oj.uz

답안 #678610

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
678610 2023-01-06T08:34:55 Z hotboy2703 Dango Maker (JOI18_dango_maker) C++14
13 / 100
 2 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].first;
    }
    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));
            }
        }
    }
    //cout<<x<<' '<<y<<' '<<res<<'\n';
    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};
            }

        }
        /*for (int i = 1;i <= n;i ++){
            cout<<tmp[i].first<<' '<<tmp[i].second<<'\n';
        }*/

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

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 328 KB Output is correct
18 Correct 0 ms 324 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Incorrect 1 ms 340 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 324 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 324 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 328 KB Output is correct
18 Correct 0 ms 324 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Incorrect 1 ms 340 KB Output isn't correct
21 Halted 0 ms 0 KB -