番号の小さい順に絵を展示するかどうか決めていく動的計画法を考えます。

\(\text{dp}[i][j] := \) 番号が小さい方から \(i\) 個の絵のみを考える。これらを展示する方法のうち、展示される絵の個数を \(3\) で割ったあまりが \(j\) であるものに対する、得られることが確定する点数の最大値。

「得られることが確定する点数」とは、番号が \(i\) 以下の絵のうち展示すると決めたものに対する \(A_k\) の総和と、\(Q_k - 1 \leq i\) を満たす条件のうち成り立っているものに対する \(P_k\) の総和を足し合わせたものです。

「今までに展示すると決めた絵の個数を \(3\) で割ったあまり」を管理するだけでは、\(R_j\) に関する条件に対応することができません。これは、最終的に展示する絵の個数を \(3\) で割ったあまりを固定し、全て調べることにすると解決します。

計算量は \(O(N + M)\) です。

実装例 (C++)

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

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (auto& x : a) {
        cin >> x;
    }
    array<array<vector<long long>, 3>, 3> add = {};
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            add[i][j].resize(n + 1);
        }
    }
    while (m--) {
        int p, q, l, r;
        cin >> p >> q >> l >> r;
        add[(l + r) % 3][l][q - 1] += p;
    }
    long long ans = 0;
    for (int all = 0; all < 3; ++all) {
        array<long long, 3> dp;
        dp[0] = add[all][0][0];
        dp[1] = dp[2] = numeric_limits<long long>::min();
        for (int i = 0; i < n; ++i) {
            array<long long, 3> next;
            for (int j = 0; j < 3; ++j) {
                next[(j + 1) % 3] = max(dp[(j + 1) % 3], dp[j] + a[i]);
            }
            dp = move(next);
            for (int j = 0; j < 3; ++j) {
                dp[j] += add[all][j][i + 1];
            }
        }
        ans = max(ans, dp[all]);
    }
    cout << ans << '\n';
    return 0;
}