제출 #300456

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
300456		CSQ31	Dango Maker (JOI18_dango_maker)	C++14	100 / 100	234 ms	18168 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
const int MAXN = 3005;

int n, m;
char str[MAXN][MAXN];

int R[MAXN], W[MAXN];
int dR[MAXN], dW[MAXN];

int solve(int n){
	for(int i=1; i<=n; i++){
		dR[i] = dR[i-1];
		dW[i] = dW[i-1];
		if(i > 1){
			dR[i] = max(dR[i], dW[i-2]);
			dW[i] = max(dW[i], dR[i-2]);
		}
		if(R[i-1] && W[i]) dR[i]++;
		if(W[i-1] && R[i]) dW[i]++;
	}
	return max(dR[n], dW[n]);
}
bool okR(int x, int y){ return x >= 0 && x < n && y >= 0 && y < m && str[x][y] == 'R'; }
bool okW(int x, int y){ return x >= 0 && x < n && y >= 0 && y < m && str[x][y] == 'W'; }
bool okG(int x, int y){ return x >= 0 && x < n && y >= 0 && y < m && str[x][y] == 'G'; }

int main(){
	scanf("%d %d",&n,&m);
	for(int i=0; i<n; i++) scanf("%s", str[i]);
	int ans = 0;
	for(int i=0; i<n+m-1; i++){
		vector<pi> v;
		for(int j=0; j<=i; j++){
			if(okG(j, i-j)) v.push_back(pi(j, i-j));
		}
		for(int i=0; i<v.size(); ){
			int e = i;
			while(e < v.size() && v[e].first - v[i].first == e - i) e++;
			R[0] = okR(v[i].first - 1, v[i].second);
			W[0] = okW(v[i].first, v[i].second + 1);
			for(int j=i; j<e; j++){
				R[j-i+1] = okR(v[j].first, v[j].second-1);
				W[j-i+1] = okW(v[j].first + 1, v[j].second);
			}
			ans += solve(e - i);
			i = e;
		}
	}
	cout << ans << endl;
}

컴파일 시 표준 에러 (stderr) 메시지

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:38:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for(int i=0; i<v.size(); ){
      |                ~^~~~~~~~~
dango_maker.cpp:40:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |    while(e < v.size() && v[e].first - v[i].first == e - i) e++;
      |          ~~^~~~~~~~~~
dango_maker.cpp:30:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   30 |  scanf("%d %d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~
dango_maker.cpp:31:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |  for(int i=0; i<n; i++) scanf("%s", str[i]);
      |                         ~~~~~^~~~~~~~~~~~~~

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