Submission #72755109

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
using LL = long long;
#define fi first
#define se second
constexpr int MAXN = 3e4 + 5, M = 9, INF = 1e9;
int n, m, c[MAXN], dp[MAXN], pre[MAXN], a[MAXN][M], rev[MAXN][M];
inline void chmax(int &x, int y) { if (x < y) x = y; }
inline int calc(int p, int q) {
	int ret = 0;
	for (int i = 1; i <= m; ++i) {
		for (int j = 1; j <= m; ++j) if (rev[p][i] < rev[p][j] && rev[q][i] > rev[q][j]) ++ret;
	}
	return ret;
}
int main() {
	IOS;
	cin >> n >> m;
	int N = m * (m - 1) / 2;
	iota(rev[0] + 1, rev[0] + 1 + m, 0);
	for (int i = 1; i <= n; ++i) {
		cin >> c[i];
		for (int j = 0; j < m; ++j) cin >> a[i][j], rev[i][a[i][j]] = j;
		dp[i] = -INF;
		if (i > N) dp[i] = pre[i - 1 - N] + c[i];
		for (int j = i - 1; j >= i - N && j >= 0; --j) if (calc(i, j) <= i - j) chmax(dp[i], dp[j] + c[i]);
		pre[i] = dp[i];
		chmax(pre[i], pre[i - 1]);
	}
//	cerr << calc(0, 1) << '\n';
	cout << pre[n] << '\n';
	return 0;
}

Submission Info

Judge Result