Submission #244879

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <ctime>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <functional>
#include <fstream>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <cstring>
#include <numeric>
#include <cassert>
using namespace std;
static const double EPS = 1e-10;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(int)(n);(i)++)
#define rev(i,n) for(int i=(n)-1;(i)>=0;(i)--)
#define all(a) a.begin(),a.end()
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define SS stringstream
#define DBG1(a) rep(_X,sz(a)){printf("%d ",a[_X]);}puts("");
#define DBG2(a) rep(_X,sz(a)){rep(_Y,sz(a[_X]))printf("%d ",a[_X][_Y]);puts("");}
#define bitcount(b) __builtin_popcountll(b)
#define gcd(a,b) (__gcd((a),(b)))
#define lcm(a,b) ( (a) / gcd((a),(b)) * (b) )
template<typename T, typename S> vector<T>& operator<<(vector<T>& a, S b) { a.push_back(b); return a; }
template<typename T> void operator>>(vector<T>& a, int b) {while(b--)if(!a.empty())a.pop_back();}
bool isprime(int n){ if(n<2)return false;  for(int i=2;i*i<=n;i++)if(n%i==0)return false;  return true;} 
 
const long long mod = 1000000007ll;
ll b_pow(ll x,ll n){return n ? b_pow(x*x%mod,n/2)*(n%2?x:1)%mod : 1ll;}
string itos(int n){stringstream ss;ss << n;return ss.str();}
 
long long in(){
	long long x; cin >> x;
	return x;
}
 
 
int A[3010];
 
int P[3010];
#define st first.first
#define en first.second
#define stat second
vector< pair<pair<int,int>,int > > v;

int next[3010];
int N;
int dp[3010];
int dfs(int x){
	
	if( x == N ) return 0;
	if( dp[x] != -1 ) return dp[x];
	// no choice
	int ans = dfs(x+1);
	// choice
	vector< pair<pair<int,int>,int> > item;
	for(int j = x ; j < v.size() ; j++){
		if( v[j].stat == v[x].stat  ){
			item.push_back(mp(mp(v[j].en,v[j].st),j));
		}
	}
	sort(item.begin(),item.end());
	int cur = -1;
	int sum = 0;
	int k = 0;
	for(int i = 0 ; i < item.size() ; i++){
		int e = item[i].first.first;
		int s = item[i].first.second;
		if( s >= cur ){
			cur = e;
			sum += A[k++];
			ans = max( dfs(next[item[i].second]) + sum , ans );
		}
	}
	return dp[x] = ans;
}
int dp2[3010][3010];
int next2[3010];

int main(){
	memset(dp,-1,sizeof(dp));
	cin >> N ;
	for(int i = 0 ; i < N ; i++) cin >> A[i];
	for(int i = 0 ; i < N ; i++){
		int id,s,e;
		cin >> id >> s >> e;
		v.push_back(make_pair(make_pair(s,e),id));
	}
	sort(v.begin(),v.end());
	for(int i = 0 ; i < N ; i++){
		next[i] = N;
		for(int j = i + 1 ; j < N ; j++){
			if( v[j].st >= v[i].en ){
				next[i] = j;
				break;
			}
		}
	}
	for(int i = 0 ; i < N ; i++){
		next2[i] = N;
		for(int j = i + 1 ; j < N ; j++){
			if( v[j].st >= v[i].en && v[j].stat == v[i].stat ){
				next2[i] = j;
				break;
			}
		}
	}
	cout << dfs(0) << endl;
}
 

Submission Info

Judge Result