Submission #520860

---

Source Code Expand

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long int ll;

const int DEBUG = 0;

struct mov {
	int m, s, e;
};

istream &operator>>(istream &os, mov &m) {
	os >> m.m >> m.s >> m.e;
	return os;
}

bool mov_cmp(const mov &m1, const mov &m2) {
	return m1.s < m2.s;
}

int solve(vector<int> &h, vector<mov> &ms) {
	int n = h.size();
	vector<vector<int> > dp(n);
	vector<int> dpm(n, -1);
	REP(i, 0, n) {
		dp[i] = vector<int>(n, -1);
	}
	REP(i, 0, n) {
		REP(j, 0, n) {
			int ma = -1;
			REP(k, 0, i) {
				if (ms[k].e > ms[i].s) {
					continue;
				}
				if (j == 0) {
					if (dpm[k] >= 0) {
						ma = max(ma, dpm[k] + h[0]);
					}
				} else {
					if (ms[k].m == ms[i].m && dp[k][j - 1] >= 0) {
						ma = max(ma, dp[k][j - 1] + h[j]);
					}
				}
			}
			if (j == 0) {
				ma = max(ma, h[0]);
			}
			dp[i][j] = ma;
			dpm[i] = max(dpm[i], ma);
		}
	}
	int ma = 0;
	REP(i, 0, n) {
		ma = max(ma, dpm[i]);
	}
	return ma;
}

int main(void) {
	int n;
	cin >> n;
	vector<int> h(n);
	vector<mov> ms(n);
	REP(i, 0, n) {
		cin >> h[i];
	}
	REP(i, 0, n) {
		cin >> ms[i];
	}
	assert (n <= 1000);
	sort(ms.begin(), ms.end(), mov_cmp);
	cout << solve(h, ms) << endl;
}

Submission Info

Judge Result