まずは少し単純化した次のような問題を考えます。

単純化した問題：元の問題の点数の付け方のうち、「\(Q_i\) 以上」に関する条件を満たしていなくても「\(Q_i\) 未満」に関する条件さえ満たしていれば \(P_i\) 点もらえるとする。このときの点数の最大値は？

この単純化した問題は
DP[ i ][ j ] = \(i\) 番目までの絵画だけを考えて、展示する個数を \(3\) で割ったあまりが \(j\) になるときの得点の最大値
とするDPで求めることができます。（ここで、「\(x\) 番目までの絵画だけを考える」とは、\(i<x\) の範囲の \(A_i\) と、\(Q_i<x\) の範囲の \(P_i\) だけを考慮する、という意味です）

元の問題に戻ります。元の問題で同様のDPをしようとすると、\(P_i\) 点もらえるかどうかが \(i\) 番目より後の絵画を選ぶ個数に依存しているように見えます。しかし、先に「展示する絵画の個数を \(3\) で割ったあまり」を決めてしまえば、先述のDPテーブルが持つ情報だけで \(P_i\) 点もらえるかどうかを判定することができます。

よって、「展示する絵画の個数を \(3\) で割ったあまり」を決め打ってからDPすることを 3 回繰り返すことでこの問題を解くことができます。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll INF=(ll)1e18;
#define rep(i,l,r)for(int i=(l);i<(r);i++)

int main(){
	int n,m;
	cin >> n >> m;
	vector<ll>a(n);
	rep(i,0,n)cin >> a[i];
	vector<vector<array<ll,3>>>q(n+1);
	rep(i,0,m){
		int x,y,l,r;
		cin >> x >> y >> l >> r;
		q[y-1].push_back({x,l,r});
	}

	ll ans=0;
	//「展示する絵画の個数を3で割ったあまりk」を3通り全探索
	rep(k,0,3){
		vector<array<ll,3>>dp(n+1,{-INF,-INF,-INF});
		//dp[i][j]= i 番目までの絵画だけを考えて、展示する個数を 3 で割ったあまりが j になるときの得点の最大値
		dp[0][0]=0;
		for(auto[p,l,r]:q[0])if(l==0&&(l+r)%3==k)dp[0][0]+=p;
		rep(i,1,n+1){
			rep(j,0,3){
				//もらうDP
				dp[i][j]=max(dp[i-1][(j-1+3)%3]+a[i-1],dp[i-1][j]);
				for(auto[p,l,r]:q[i])if(l==j&&(l+r)%3==k)dp[i][j]+=p;
			}
		}
		// 辻褄が合う結果だけ考慮する (展示する絵画の個数を3で割ったあまりが実際に k になっている)
		ans=max(ans,dp[n][k]);
	}
	cout << ans << endl;
}

使われた典型

• 区間に関する条件は、いま注目している範囲に完全に含まれるもののみを考慮する（類題：EDPC W、ARC074E、ARC119E）
• 条件をうちいくつかを決め打ってから探索を始め、最終的にその条件を満たしている結果だけを考慮する（類題：ABC251E、ABC229F）