Submission #1138667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138667		adiyer	September (APIO24_september)	C++20	30 / 100	1078 ms	1816 KiB

september

#include <bits/stdc++.h>
#include "september.h"	

using namespace std;

const int MAXN = 1e3 + 11;

int p[MAXN];
int id[7][MAXN], dp[MAXN];

bool mrk[7][MAXN], can[MAXN][MAXN];

set < int > st;

void up(int v, int k){
	if(v == 0 || mrk[k][v]) return;
	// cout << "Bad parent: " << v << ' ' << id[k][v] << '\n';
	st.insert(id[k][v]), mrk[k][v] = 1;
	up(p[v], k);
}

int solve(int N, int M, vector<int> F, vector<vector<int>> S) {
	for(int i = 0; i < N; i++) p[i] = F[i], dp[i] = 0;
	for(int i = 0; i < M; i++)
		for(int j = 0; j < N - 1; j++)
			id[i][S[i][j]] = j;
	for(int i = 0; i < N - 1; i++){
		st.clear();
		for(int i = 0; i < M; i++)
			for(int j = 0; j < N; j++)
				mrk[i][j] = 0;
		for(int j = N - 2; j >= i; j--){
			auto it = st.lower_bound(i);
			// if(it != st.end()) cout << *it << ' ' << "Sigma\n";
			if(it == st.end() || *it > j) can[i][j] = 1;
			else can[i][j] = 0;
			// if(can[i][j]) cout << "Good: " << i << ' ' << j << '\n';
			// for(auto it : st) cout << it << ' ';
			// cout << '\n';
			for(int k = 0; k < M; k++) up(S[k][j], k);
		}
	}
	for(int i = 0; i < N - 1; i++)
		if(can[0][i])
			dp[i] = 1;
	for(int i = 0; i < N - 1; i++)
		for(int j = 0; j < i; j++)
			if(dp[j] && can[j + 1][i]) 
				dp[i] = max(dp[i], dp[j] + 1);
	return dp[N - 2];
}

/*
void taskcase() {
	int N, M;
	assert(2 == scanf("%d%d", &N, &M));
	std::vector<int> F(N);
	F[0] = -1;
	for (int i = 1; i < N; ++i)
  		assert(1 == scanf("%d", &F[i]));
	vector<vector<int>> S((M), vector<int>(N - 1));
	for (int i = 0; i < M; ++i){
		for (int j = 0; j < N - 1; ++j)
  			scanf("%d", &S[i][j]);
	}
	printf("%d\n", solve(N, M, F, S));
}

int main() {
	int T;
	scanf("%d", &T);
	while(T--) taskcase();
	return 0;
}
*/

• Subtask 1: 11 / 11
• Subtask 2: 0 / 14
• Subtask 3: 5 / 5
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 0 / 11
• Subtask 7: 0 / 9
• Subtask 8: 0 / 11
• Subtask 9: 0 / 9
• Subtask 10: 0 / 16