oj.uz

Submission #233679

# Submission time Handle Problem Language Result Execution time Memory
233679 2020-05-21T10:59:22 Z Coroian_David Dango Maker (JOI18_dango_maker) C++11
13 / 100
 5 ms 512 KB 
#include <bits/stdc++.h>

#define MAX_N 3000
#define MAX_M 3000

using namespace std;

char a[MAX_N + 1][MAX_M + 1];
short lin[MAX_N + 1][MAX_M + 1];
short lin3[MAX_N + 1][MAX_M + 1];
short col[MAX_N + 1][MAX_M + 1];
short col3[MAX_N + 1][MAX_M + 1];
int dp[MAX_N + 1][MAX_M + 1];
short tmp[MAX_N + 1][MAX_M + 1];

int n, m;
int rez;

string s;

int max(short a, int b)
{
    return (a > b ? a : b);
}

void readFile()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> s;
        for(int j = 1; j <= m; j ++)
            a[i][j] = (s[j - 1] == 'R' ? 0 : (s[j - 1] == 'G' ? 1 : 2));
    }


}

void getLin()
{
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 3; j <= m; j ++)
        {
            lin[i][j] = lin[i][j - 1];
            if(a[i][j - 2] == 0 && a[i][j - 1] == 1 && a[i][j] == 2)
                lin[i][j] = max(lin[i][j], lin[i][j - 3] + 1);
        }
    }
}

void getCol()
{
    for(int j = 1; j <= m; j ++)
    {
        for(int i = 3; i <= n; i ++)
        {
            col[i][j] = col[i - 1][j];
            if(a[i - 2][j] == 0 && a[i - 1][j] == 1 && a[i][j] == 2)
                col[i][j] = max(col[i][j], col[i - 3][j] + 1);
        }
    }
}

void getLin3(int c)
{
    for(int i = c; i <= c + 2; i ++)
    {
        for(int j = 1; j <= m; j ++)
            tmp[i][j] = 0;
    }

    for(int j = 1; j <= m; j ++)
        tmp[c][j] = lin[c][j];

    tmp[c + 2][1] = (a[c][1] == 0 && a[c + 1][1] == 1 && a[c + 2][1] == 2);

    for(int i = c; i <= c + 2; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            if(i + 1 <= c + 2)
                tmp[i + 1][j] = max(tmp[i + 1][j], tmp[i][j] + lin[i + 1][j]);

            if(j + 1 <= m)
                tmp[i][j + 1] = max(tmp[i][j + 1], tmp[i][j] + col[i][j + 1]);
        }
    }

    for(int i = 1; i <= n; i ++)
        lin3[i][c + 2] = tmp[i][c + 2];
}

void getCol3(int c)
{
    for(int i = 1; i <= n; i ++)
    {
        for(int j = c; j <= c + 2; j ++)
            tmp[i][j] = 0;
    }

    for(int i = 1; i <= n; i ++)
        tmp[i][c] = col[i][c];

    tmp[1][c + 2] = (a[1][c] == 0 && a[1][c + 1] == 1 && a[1][c + 2] == 2);

    for(int i = 1; i <= n; i ++)
    {
        for(int j = c; j <= c + 2; j ++)
        {
            if(i + 1 <= n)
                tmp[i + 1][j] = max(tmp[i + 1][j], tmp[i][j] + lin[i + 1][j]);

            if(j + 1 <= c + 2)
                tmp[i][j + 1] = max(tmp[i][j + 1], tmp[i][j] + col[i][j + 1]);
        }
    }

    for(int i = 1; i <= n; i ++)
        col3[i][c + 2] = tmp[i][c + 2];
}

void getDp()
{
    for(int i = 1; i <= n; i ++)
        dp[i][1] = col[i][1];

    for(int j = 1; j <= m; j ++)
        dp[1][j] = lin[1][j];

    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            if(i + 1 <= n)
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j] + lin[i + 1][j]);

            if(j + 1 <= m)
                dp[i][j + 1] = max(dp[i][j + 1], dp[i][j] + col[i][j + 1]);

            if(i + 3 <= n)
                dp[i + 3][j] = max(dp[i + 3][j], dp[i][j] + lin3[i + 3][j]);

            if(j + 3 <= m)
                dp[i][j + 3] = max(dp[i][j + 3], dp[i][j] + col3[i][j + 3]);
        }
    }

    rez = dp[n][m];
}

void solve()
{
    getLin();

    getCol();

    for(int j = 1; j + 2 <= m; j ++)
        getCol3(j);

    for(int i = 1; i + 2 <= n; i ++)
        getLin3(i);

    getDp();
}

void printFile()
{
    cout << rez << "\n";
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 4 ms 512 KB Output is correct
13 Correct 5 ms 512 KB Output is correct
14 Correct 5 ms 512 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 5 ms 512 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 4 ms 512 KB Output is correct
13 Correct 5 ms 512 KB Output is correct
14 Correct 5 ms 512 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 5 ms 512 KB Output is correct
17 Correct 4 ms 512 KB Output is correct
18 Correct 5 ms 512 KB Output is correct
19 Incorrect 5 ms 512 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 5 ms 512 KB Output is correct
12 Correct 4 ms 512 KB Output is correct
13 Correct 5 ms 512 KB Output is correct
14 Correct 5 ms 512 KB Output is correct
15 Correct 4 ms 384 KB Output is correct
16 Correct 5 ms 512 KB Output is correct
17 Correct 4 ms 512 KB Output is correct
18 Correct 5 ms 512 KB Output is correct
19 Incorrect 5 ms 512 KB Output isn't correct
20 Halted 0 ms 0 KB -