Submission #442700

#	Time	Username	Problem	Language	Result	Execution time	Memory
442700		penguinhacker	Jetpack (COCI16_jetpack)	C++14	80 / 80	16 ms	10572 KiB

jetpack

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

#define ll long long
#define ar array

const int mxN=1e5;
int n;
string g[10];
ar<int, 2> dp[mxN][10];
vector<bool> ans;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i=9; ~i; --i)
		cin >> g[i];
	memset(dp, -1, sizeof(dp));
	dp[0][0]={};
	for (int i=0; i+1<n; ++i) {
		for (int j=0; j<10; ++j) {
			if (dp[i][j][0]==-1)
				continue;
			if (j&&g[j-1][i+1]=='.')
				dp[i+1][j-1]={j, 0};
			else if (j==0&&g[j][i+1]=='.')
				dp[i+1][j]={j, 0};
			if (j+1<10&&g[j+1][i+1]=='.')
				dp[i+1][j+1]={j, 1};
			else if (j==9&&g[j][i+1]=='.')
				dp[i+1][j]={j, 1};
		}
	}
	int j=-1;
	for (int i=0; i<10; ++i)
		if (dp[n-1][i][0]^-1)
			j=i;
	assert(j^-1);
	for (int i=n-1; i; --i) {
		assert(dp[i][j][0]^-1);
		ans.push_back(dp[i][j][1]);
		j=dp[i][j][0];
	}
	reverse(ans.begin(), ans.end());
	vector<ar<int, 2>> ans2;
	for (int i=0; i<n-1; ++i) {
		if (!ans[i])
			continue;
		for (j=i; j+1<n-1&&ans[j+1]; ++j);
		ans2.push_back({i, j-i+1});
		i=j;
	}
	cout << ans2.size() << "\n";
	for (ar<int, 2> a : ans2)
		cout << a[0] << " " << a[1] << "\n";
	return 0;
}

• Subtask 1: 80 / 80