제출 #1332877

#제출 시각아이디문제언어결과실행 시간메모리
1332877blackscreen1Dango Maker (JOI18_dango_maker)C++20
100 / 100
332 ms141688 KiB
#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
             tree_order_statistics_node_update>
    ordered_multiset;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define pll pair<ll, ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
ll n, m, a[3005][3005], b[3005][3005];
char c;
pll tmp;
ll ans = 0;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> m;
	iloop(0, n) jloop(0, m) {
		cin >> c;
		if (c == 'R') a[i][j] = 0;
		else if (c == 'G') a[i][j] = 1;
		else a[i][j] = 2;
	}
	iloop(0, n) jloop(0, m) if (a[i][j] == 1) {
		if (i && i < n-1 && a[i-1][j] == 0 && a[i+1][j] == 2) b[i][j]++;
		if (j && j < m-1 && a[i][j-1] == 0 && a[i][j+1] == 2) b[i][j] += 2;
	}
	iloop(1LL, n + m - 2) {
		vector<pll> dp;
		dp.push_back({0, 0});
		ll ci = min(i, m-1);
		while (ci >= 0 && i - ci <= n-1) {
			tmp = {max(dp.back().second, dp.back().first + (b[i - ci][ci]&1)), max(dp.back().first, dp.back().second + (b[i - ci][ci]&2)/2)};
			dp.push_back(tmp);
			ci--;
		}
		//for (auto it : dp) cout << it.first << " " << it.second << "\n";
		//cout << "\n";
		ans += max(dp.back().first, dp.back().second);
	}
	cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...