Contest Results

Processing math: 100%

(Analysis by Benjamin Qi)

Subtask 1:

We can use bitmask DP and construct the sequence in order. Let $cur$ be the bitmask representing the cows which have already been chosen and let $res[cur]$ be the maximum possible length of the sequence for this state. Furthermore, let $mask[cur]$ be the bitmask representing the pies that are chosen by these cows and $tot[i]$ be the bitmask representing the pies which cow $i$ enjoys. Then we can only add cow $i$ to the sequence if $mask[cur]\neq (mask[cur]\&tot[i])$ .

It's easy to implement a solution that runs in $O(M2^M)$ time.

Subtask 2:

Any reasonable solution which is polynomial in $N$ should pass.

Subtask 3:

We can solve this problem in $O(N^3).$ Let $dp[l][r]$ denote the maximum number of cows such that the set of eaten pies is a subset of the range $l\ldots r.$ Then we can write

$dp[l][r]:=\max_{l\le i<r}(dp[l][i]+dp[i+1][r]).$

Furthermore, suppose that the last cow in the sequence ate pie

$i$ for some

$l\le i\le r.$ Then if there exists an interval

$[a,b]$ such that

$l\le a\le i\le b\le r,$ we can write

$dp[l][r]:=\max(dp[l][r],dp[l][i-1]+dp[i+1][r]+mx[i][l][r]),$

where

$mx[i][l][r]$ is the maximum weight over all cows

$[l_i,r_i]$ satisfying

$l\le l_i\le i\le r_i\le r.$ Our answer will be the value of

$dp[0][N-1].$

This DP can be computed in $O(N^3)$ time.

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

typedef long long ll;
typedef vector<int> vi; 
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
 
template<class T> bool ckmax(T& a, const T& b) { 
	return a < b ? a = b, 1 : 0; }
	
void setIO(string name) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}

const int MX = 300;
 
int N,M,dp[MX][MX];
int mx[MX][MX][MX];
vi w,l,r;
 
int main() {
	setIO("pieaters"); 
	cin >> N >> M;
	w.rsz(M); l.rsz(M), r.rsz(M);
	F0R(i,M) {
		cin >> w[i] >> l[i] >> r[i]; 
		l[i] --,r[i] --;
		FOR(j,l[i],r[i]+1) 
			ckmax(mx[j][l[i]][r[i]],w[i]);
	}
	F0R(i,N) {
		R0F(j,i+1) FOR(k,i,N) {
			if (j) ckmax(mx[i][j-1][k],mx[i][j][k]);
			if (k < N-1) ckmax(mx[i][j][k+1],mx[i][j][k]);
		}
	}
	R0F(a,N) FOR(b,a,N) {
		FOR(c,a,b) ckmax(dp[a][b],dp[a][c]+dp[c+1][b]);
		FOR(c,a,b+1) if (mx[c][a][b]) { // among all those covering c >= a
			int res = mx[c][a][b];
			if (c > a) res += dp[a][c-1];
			if (c < b) res += dp[c+1][b];
			ckmax(dp[a][b],res);
		}
	}
	cout << dp[0][N-1] << "\n";
}