Submission #747715

#	Time	Username	Problem	Language	Result	Execution time	Memory
747715		Sami_Massah	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	671 ms	19468 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;


const long long maxn = 3000 + 12 ;
long long n, m, ans, dp[maxn][4][4];
string s[maxn];
vector <int> nums;
bool val(int a, int b){
    if(a < 0 || a >= n)
        return 0;
    if(b < 0 || b >= m)
        return 0;
    return 1;
}
int get_max(){
  //  for(int i: nums)
    //    cout << i << ' ';
    //cout << endl;
    for(int i = 0; i <= nums.size(); i++)
        for(int j = 0; j < 4; j++)
            for(int c = 0; c < 4; c++)
                dp[i][j][c] = 0;
    for(int i = 3; i < nums.size(); i++){
        for(int j = 0; j < 4; j++)
            for(int c = 0; c < 4; c++){

                if(j & 1)
                    dp[i][c][j] = max(dp[i][c][j], dp[i - 2][nums[i - 2] & 1][nums[i - 3] & 1] + 1 + (c > 0));
                if(j & 2)
                    dp[i][c][j] = max(dp[i][c][j], dp[i - 2][nums[i - 2]][nums[i - 3]] + 1 + ((c & 2) > 0));

                if(c & 2)
                    dp[i][c][j] = max(dp[i][c][j], dp[i - 2][nums[i - 2]][nums[i - 3]] + 1);
                if(c & 1)
                    dp[i][c][j] = max(dp[i][c][j], dp[i - 2][nums[i - 2] & 1][nums[i - 3]] + 1);
                dp[i][c][j] = max(dp[i][c][j], dp[i - 2][nums[i - 2]][nums[i - 3]]);

        }
    //    cout << i - 2 << ' ' << dp[i][nums[i]][nums[i - 1]] << endl;

    }
    int f = nums[nums.size() - 1];
    int s = nums[nums.size() - 2];
    return dp[nums.size() - 1][f][s];


}
int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);

    cin >> n >> m;
    for(int i = 0; i < n; i++)
        cin >> s[i];

    for(int sum = 0; sum <= n + m - 2; sum++){
        nums.push_back(0);
        nums.push_back(0);
        nums.push_back(0);
        for(int j = 0; j < m; j++){
            int i = sum - j;
            if(i < 0 || i >= n)
                continue;
            nums.push_back(0);
            int a = i, b = j;
            if(s[i][j] == 'R' && val(a + 1, b) && s[a + 1][b] == 'G' && val(a + 2, b) && s[a + 2][b] == 'W')
                nums.back() += 1;
            if(s[i][j] == 'R' && val(a, b + 1) && s[a][b + 1] == 'G' && val(a, b + 2) && s[a][b + 2] == 'W')
                nums.back() += 2;

        }
        int x = get_max();
        ans += x;
       // cout << sum << ' ' << x << endl;
        nums.clear();



    }
    cout << ans << endl;


}

Compilation message (stderr)

dango_maker.cpp: In function 'int get_max()':
dango_maker.cpp:20:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i = 0; i <= nums.size(); i++)
      |                    ~~^~~~~~~~~~~~~~
dango_maker.cpp:24:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i = 3; i < nums.size(); i++){
      |                    ~~^~~~~~~~~~~~~

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