Submission #362220

#	Time	Username	Problem	Language	Result	Execution time	Memory
362220		Sparky_09	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	522 ms	141672 KiB

dango_maker

#include "bits/stdc++.h"
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;

void usaco(string s){
  freopen((s+".in").c_str(), "r", stdin);
  freopen((s+".out").c_str(), "w", stdout);
}

struct UF {
	vi e;
	UF(int n) : e(n, -1) {}
	bool sameSet(int a, int b) { return find(a) == find(b); }
	int size(int x) { return -e[find(x)]; }
	int find(int x) { return e[x] < 0 ? x : e[x] = find(e[x]); }
	bool join(int a, int b) {
		a = find(a), b = find(b);
		if (a == b) return false;
		if (e[a] > e[b]) swap(a, b);
		e[a] += e[b]; e[b] = a;
		return true;
	}
};

const int MN = 3e3+5, MOD = 1e9+7;
char grid[MN][MN]; 
bool ver[MN][MN], hor[MN][MN]; 
int dp[MN][MN][3];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
#ifdef LOCAL_DEFINE
	freopen("input.txt", "r", stdin);
#endif
/*
  int n, m;
  cin >> n >> m;
  memset(vis, 0, sizeof vis);
  for(int i = 0; i < n+10; i++) for(int j = 0; j < m+10; j++) grid[i][j] = '-';
  for(int i = 3; i < n+3; i++) for(int j = 3; j < m+3; j++) cin >> grid[i][j];
  vector<pair<int, int>> adj;
  for(int i = 3; i < n+3; i++){
    for(int j = 3; j < n+3; j++){
      if(grid[i][j] == 'R'){
        adj.push_back({i, j});  
      }
    }
  }
  UF uf1, uf2;
  for(auto i: adj){
  	//process the connected components
  	vector<int>().swap(proc);
    if(!vis[i.first][i.second]){
      dfs(i);
    }
    for(auto j: proc){
      int x = j[0], y = j[1], dir = j[2];
      if(
    }
  }
  */
 	int n,m,ret = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> (grid[i] + 1);
		for (int j = 1; j <= m-2; j++) if (grid[i][j] == 'R' && grid[i][j+1] == 'G' && grid[i][j+2] == 'W') {
			hor[i][j+1] = 1;
		}
	}
	for (int j = 1; j <= m; j++) 
		for (int i = 1; i <= n-2; i++) if (grid[i][j] == 'R' && grid[i+1][j] == 'G' && grid[i+2][j] == 'W') 
			ver[i+1][j] = 1;
	for (int v = 2; v <= n+m; v++){
		int add = 0;
		for (int i = 1; i <= n; i++){
			int j = v - i;
			if (1 <= j && j <= m) {
				dp[i][j][0] = max({dp[i-1][j+1][0],dp[i-1][j+1][1],dp[i-1][j+1][2]});
				if (hor[i][j]) 
					dp[i][j][1] = max(dp[i-1][j+1][0],dp[i-1][j+1][1]) + 1; 
				if (ver[i][j]) 
					dp[i][j][2] = max(dp[i-1][j+1][0],dp[i-1][j+1][2]) + 1;
				add = max({add,dp[i][j][0],dp[i][j][1],dp[i][j][2]});
			}
		}
		ret += add;
	}	
	cout << ret << '\n';
	return 0;
}

Compilation message (stderr)

dango_maker.cpp: In function 'void usaco(std::string)':
dango_maker.cpp:13:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   13 |   freopen((s+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dango_maker.cpp:14:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   14 |   freopen((s+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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