Submission #1272471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272471		crispxx	Chess Rush (CEOI20_chessrush)	C++20	0 / 100	147 ms	12248 KiB

chessrush

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

#include "arithmetics.h"
// #include "arithmetics.cpp"

// #define int long long
#define all(x) x.begin(), x.end()
#define pb push_back
#define ar array
#define nl '\n'

template <typename A, typename B>
bool chmin(A &a, const B &b) {
	if(a > b) {
		return a = b, true;
	}
	return false;
}

template <typename A, typename B>
bool chmax(A &a, const B &b) {
	if(a < b) {
		return a = b, true;
	}
	return false;
}

vector<int> dp[100][100][100];
int sdist[100][100];

void solve() {
	int r, c, Q; cin >> r >> c >> Q;
	
	for(int c1 = 0; c1 < c; c1++) {
		deque<ar<int, 3>> q;
		
		int dist[r][c];
		
		memset(dist, -1, sizeof(dist));
		
		q.push_back({0, c1, -1});
		
		dist[0][c1] = 0;
		
		while(!q.empty()) {
			auto [x, y, dir] = q.front();
			q.pop_front();
			
			if( x + 1 < r && y - 1 >= 0 && dist[x + 1][y - 1] == -1 ) {
				if(dir == 1) {
					dist[x + 1][y - 1] = dist[x][y];
					q.push_front( {x + 1, y - 1, dir} );
				} else {
					dist[x + 1][y - 1] = dist[x][y] + 1;
					q.push_back( {x + 1, y - 1, 1} );
				}
			}
			
			if( x + 1 < r && y + 1 < c && dist[x + 1][y + 1] == -1 ) {
				if(dir == 2) {
					dist[x + 1][y + 1] = dist[x][y];
					q.push_front( {x + 1, y + 1, dir} );
				} else {
					dist[x + 1][y + 1] = dist[x][y] + 1;
					q.push_back( {x + 1, y + 1, 2} );
				}
			}
		}
		
		int K = 0;
		
		for(int cr = 0; cr < c; cr++) {
			sdist[c1][cr] = dist[r - 1][cr];
			chmax(K, sdist[c1][cr]);
		}
		
		dp[c1][0][c1].resize(K + 1);
		dp[c1][0][c1][0] = 1;
		
		for(int i = 0; i < r; i++) {
			for(int j = 0; j < c; j++) {
				dp[c1][i][j].resize(K + 1);
				for(int k = 1; k <= K; k++) {
					int x = i, y1 = j, y2 = j;
					while( x - 1 >= 0 && (y1 - 1 >= 0 || y2 + 1 < c) ) {
						x--;
						if(y1 - 1 >= 0) {
							y1--;
							dp[c1][i][j][k] = Add(dp[c1][i][j][k], dp[c1][x][y1][k - 1]);
						}
						if(y2 + 1 < c) {
							y2++;
							dp[c1][i][j][k] = Add(dp[c1][i][j][k], dp[c1][x][y2][k - 1]);
						}
					}
				}
			}
		}
	}
	
	while(Q--) {
		char T; int c1, cr;
		cin >> T >> c1 >> cr;
		c1--, cr--;
		
		if(T == 'B') {
			cout << sdist[c1][cr] << ' ' << dp[c1][r - 1][cr][ sdist[c1][cr] ] << nl;
			continue;
		}
		
		cout << "nan" << nl;
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	solve();
}

• Subtask 1: 0 / 0
• Subtask 2: 0 / 8
• Subtask 3: 0 / 15
• Subtask 4: 0 / 22
• Subtask 5: 0 / 5
• Subtask 6: 0 / 8
• Subtask 7: 0 / 15
• Subtask 8: 0 / 20
• Subtask 9: 0 / 7