oj.uz

Submission #164525

# Submission time Handle Problem Language Result Execution time Memory
164525 2019-11-21T09:27:17 Z balbit Dango Maker (JOI18_dango_maker) C++14
33 / 100
 3 ms 632 KB 
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define ll long long
#define f first
#define s second
#define FOR(i,a,b) for (int i = a; i<b; i++)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for (int i = n-1; i>=0; i--)
#define SZ(x) (int)(x.size())
#define ALL(x) x.begin(),x.end()
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define pb push_back
#ifdef BALBIT
#define IOS()
#define bug(x) cerr<<__LINE__<<' '<<#x<<": "<<x<<endl
#else
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define endl '\n'
#define bug(x)
#endif

const ll mod = 1e9+7;
const int maxn = 3e3+5;
//const ll INF = 0x3f3f3f3f3f3f3f3f;
const int iinf = 0x3f3f3f3f;


	


char grd[maxn][maxn];

bool up[maxn][maxn];
bool rt[maxn][maxn];
int dp[maxn][maxn][2];



signed main(){
	IOS();
	int n, m; cin>>n>>m;
	
	REP(i,n) REP(j,m) cin>>grd[i][j];
	int nup = 0, nrt = 0;

	REP(i,n)REP(j,m){

		if(grd[i][j]=='G'){
			if (i && i!=n-1 && grd[i-1][j] == 'R' && grd[i+1][j]=='W' ) {
				up[i][j] = 1;
			}
			if (j && j!=m-1 && grd[i][j-1] == 'R' && grd[i][j+1]=='W' ) {
				rt[i][j] = 1;
			}
		}
	}

	vector<pii> st;
	REP(i,n*2) REP(j,m){
		if (i-j < n &&i-j>=0) st.pb({i-j+1,j+1});
	}

	
	ll re = 0;
	for (pii & ele: st){
		int i = ele.f, j = ele.s;
//		cout<<i<<' '<<j<<endl;
		dp[i][j][0] = dp[i][j][1] = max(dp[i+1][j-1][0], dp[i+1][j-1][1]);
		if (up[i-1][j-1]) MX(dp[i][j][0] , 1 + dp[i+1][j-1][0]);
		if (rt[i-1][j-1]) MX(dp[i][j][1] , 1 + dp[i+1][j-1][1]);
		if (i==1 || j == m){
			re += max(dp[i][j][0], dp[i][j][1]);
		}
	}
//	REP(i,n+1) REP(j,m+1){
//		cout<<dp[i][j][0]<<" \n"[j==m];
//	}
	cout<<re<<endl;
	
}

Compilation message

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:46:6: warning: unused variable 'nup' [-Wunused-variable]
  int nup = 0, nrt = 0;
      ^~~
dango_maker.cpp:46:15: warning: unused variable 'nrt' [-Wunused-variable]
  int nup = 0, nrt = 0;
               ^~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 380 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 380 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 508 KB Output is correct
20 Correct 2 ms 504 KB Output is correct
21 Correct 2 ms 504 KB Output is correct
22 Correct 2 ms 504 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 380 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 504 KB Output is correct
28 Correct 2 ms 504 KB Output is correct
29 Correct 2 ms 504 KB Output is correct
30 Correct 2 ms 376 KB Output is correct
31 Correct 2 ms 504 KB Output is correct
32 Correct 2 ms 376 KB Output is correct
33 Correct 2 ms 504 KB Output is correct
34 Correct 2 ms 504 KB Output is correct
35 Correct 2 ms 504 KB Output is correct
36 Correct 2 ms 504 KB Output is correct
37 Correct 2 ms 504 KB Output is correct
38 Correct 2 ms 504 KB Output is correct
39 Correct 2 ms 504 KB Output is correct
40 Correct 2 ms 504 KB Output is correct
41 Correct 2 ms 504 KB Output is correct
42 Correct 2 ms 504 KB Output is correct
43 Correct 2 ms 504 KB Output is correct
44 Correct 2 ms 504 KB Output is correct
45 Correct 2 ms 504 KB Output is correct
46 Correct 2 ms 504 KB Output is correct
47 Correct 2 ms 504 KB Output is correct
48 Correct 2 ms 504 KB Output is correct
49 Correct 2 ms 504 KB Output is correct
50 Correct 2 ms 508 KB Output is correct
51 Correct 2 ms 504 KB Output is correct
52 Correct 3 ms 504 KB Output is correct
53 Correct 2 ms 504 KB Output is correct

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 2 ms 380 KB Output is correct
14 Correct 2 ms 376 KB Output is correct
15 Correct 2 ms 376 KB Output is correct
16 Correct 2 ms 376 KB Output is correct
17 Correct 2 ms 376 KB Output is correct
18 Correct 2 ms 376 KB Output is correct
19 Correct 2 ms 508 KB Output is correct
20 Correct 2 ms 504 KB Output is correct
21 Correct 2 ms 504 KB Output is correct
22 Correct 2 ms 504 KB Output is correct
23 Correct 2 ms 376 KB Output is correct
24 Correct 2 ms 376 KB Output is correct
25 Correct 2 ms 380 KB Output is correct
26 Correct 2 ms 376 KB Output is correct
27 Correct 2 ms 504 KB Output is correct
28 Correct 2 ms 504 KB Output is correct
29 Correct 2 ms 504 KB Output is correct
30 Correct 2 ms 376 KB Output is correct
31 Correct 2 ms 504 KB Output is correct
32 Correct 2 ms 376 KB Output is correct
33 Correct 2 ms 504 KB Output is correct
34 Correct 2 ms 504 KB Output is correct
35 Correct 2 ms 504 KB Output is correct
36 Correct 2 ms 504 KB Output is correct
37 Correct 2 ms 504 KB Output is correct
38 Correct 2 ms 504 KB Output is correct
39 Correct 2 ms 504 KB Output is correct
40 Correct 2 ms 504 KB Output is correct
41 Correct 2 ms 504 KB Output is correct
42 Correct 2 ms 504 KB Output is correct
43 Correct 2 ms 504 KB Output is correct
44 Correct 2 ms 504 KB Output is correct
45 Correct 2 ms 504 KB Output is correct
46 Correct 2 ms 504 KB Output is correct
47 Correct 2 ms 504 KB Output is correct
48 Correct 2 ms 504 KB Output is correct
49 Correct 2 ms 504 KB Output is correct
50 Correct 2 ms 508 KB Output is correct
51 Correct 2 ms 504 KB Output is correct
52 Correct 3 ms 504 KB Output is correct
53 Correct 2 ms 504 KB Output is correct
54 Incorrect 2 ms 376 KB Output isn't correct
55 Halted 0 ms 0 KB -