Submission #678558

#	Time	Username	Problem	Language	Result	Execution time	Memory
678558		vjudge1	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	888 ms	168980 KiB

dango_maker

/*
	Unknown's C++ Template (v3.2)
*/

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

// #define int long long

using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
using vvi = vector<vi>;
using vvii = vector<vii>;
template <class T> using maxpq = priority_queue<T>;
template <class T> using minpq = priority_queue<T, vector<T>, greater<T>>;

#define pb push_back
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mid ((l+r)>>1)
#define fi first
#define se second

#ifdef LOCAL
	#define debug(x) cout << #x << " = " << x << "\n";
#else
	#define debug(x) ;
#endif

template <class A, class B>
ostream& operator << (ostream& out, pair<A, B> x)
{ out << "(" << x.first << ", " << x.second << ")"; return out; }

template <class T>
ostream& operator << (ostream& out, vector<T> x){
	out << "[";
	for (int i=0; i<sz(x); i++) { out << (i ? ", " : "") << x[i]; }
	out << "]"; return out;
}

template <class T>
istream& operator >> (istream& in, vector<T> &x){
	for (auto &i: x) in >> i;
	return in;
}

const ld PI = acos(-1.0);
const int allmod[3] = {(int)1e9+7, 998244353, (int)1e9+9};
const int mod = allmod[0];
const int maxn = 2e5 + 64;
const ll inf = 1e18;
const ld eps = 1e-6;
const int multitest = 0;

using i16 = int16_t;

i16 dp[3005][3005][3][3];
// 0 -> none, 1 -> down, 2 -> right

void main_program(){
	int n, m; cin >> n >> m;
	vector<string> vs(n); for (auto &i: vs) cin >> i;

	int res = 0;
	for (int sum = 0; sum < n + m - 1; sum++){
		i16 diagonal_max = 0;
		for (int i = 0; i <= sum; i++){
			int j = sum - i;

			if ((i < 0) || (i >= n) || (j < 0) || (j >= m)) continue;

			int pi = i - 1, pj = j + 1;
			bool valid = ((pi >= 0) && (pi < n) && (pj >= 0) && (pj < m));

			for (int m1 = 0; m1 < 3; m1++){
				for (int m2 = 0; m2 < 3; m2++){
					int val = (valid ? dp[pi][pj][m1][m2] : 0);
					// none
					dp[i][j][0][m1] = max(dp[i][j][0][m1], i16(val));
					// down
					bool valid_down = (i+2 >= n) ? false :
						(vs[i][j] == 'R' && vs[i+1][j] == 'G' && vs[i+2][j] == 'W');
					dp[i][j][1][m1] = max(dp[i][j][1][m1], i16(val + valid_down));
					// right
					bool valid_right = (j+2 >= m) ? false :
						(vs[i][j] == 'R' && vs[i][j+1] == 'G' && vs[i][j+2] == 'W');
					if (m1 == 1 || m2 == 1) valid_right = false;
					dp[i][j][2][m1] = max(dp[i][j][2][m1], i16(val + valid_right));

					diagonal_max = max({diagonal_max, dp[i][j][0][m1], dp[i][j][1][m1], dp[i][j][2][m1]});
				}
			}

			// // DEBUG
			// for (int m1 = 0; m1 < 3; m1++){
			// 	for (int m2 = 0; m2 < 3; m2++){
			// 		cout << "dp[" << i << "][" << j << "][" << m1 << "][" << m2 << "] = " << dp[i][j][m1][m2] << "\n";
			// 	}
			// }
		}
		res += diagonal_max;
	}

	cout << res << "\n";
}

void pre_main(){

}

signed main(){
	#ifdef LOCAL
		auto stime = chrono::high_resolution_clock::now();
	#endif
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	#ifndef ONLINE_JUDGE
		if (fopen(".inp", "r")){
			freopen(".inp", "r", stdin);
			freopen(".out", "w", stdout);
		}
	#endif
	int t = 1; if (multitest) cin >> t;
	pre_main();
	while (t--) main_program();
	#ifdef LOCAL
		auto etime = chrono::high_resolution_clock::now();
		auto duration = chrono::duration_cast<chrono::milliseconds>(etime-stime).count();
		cout << "\n[" << duration << "ms]\n";
	#endif
}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:121:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |    freopen(".inp", "r", stdin);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~
dango_maker.cpp:122:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |    freopen(".out", "w", stdout);
      |    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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