Submission #38538

#	Time	Username	Problem	Language	Result	Execution time	Memory
38538		kajebiii	매트 (KOI15_mat)	C++14	100 / 100	509 ms	73256 KiB

mat

#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

struct RT{
	int p, l, r, h, k, ix;
	RT() {}
	RT(int pp, int ll, int rr, int hh, int kk, int ii) : p(pp), l(ll), r(rr), h(hh), k(kk), ix(ii) {}
};

const int MAX_N = 3e3 + 10, MAX_L = 2 * MAX_N;

int N, W;
vector<int> Cs;
vector<RT> Rs, Rl[MAX_L];
int Dy[MAX_N][MAX_L];
int main() {
	cin >> N >> W;
	for(int i=0; i<N; i++) {
		int p, l, r, h, k; scanf("%d%d%d%d%d", &p, &l, &r, &h, &k);
		Rs.emplace_back(p, l, r, h, k, i);
		Cs.push_back(l); Cs.push_back(r);
	}
	Cs.push_back(0);
	sort(ALL(Cs)); Cs.erase(unique(ALL(Cs)), Cs.end());
	for(int i=0; i<N; i++) {
		Rs[i].l = lower_bound(ALL(Cs), Rs[i].l) - Cs.begin();
		Rs[i].r = lower_bound(ALL(Cs), Rs[i].r) - Cs.begin();
	}
	sort(ALL(Rs), [&](RT &a, RT &b) {return a.r < b.r;});
	for(int i=0; i<N; i++) {
		Rs[i].ix = i;
		Rl[Rs[i].r].push_back(Rs[i]);
	}
	int ans = 0;
//	for(int i=0; i<N; i++) printf("%d %d %d %d %d\n", Rs[i].p, Rs[i].l, Rs[i].r, Rs[i].h, Rs[i].k);
	for(int l=0; l<SZ(Cs); l++) {
		for(int i=0; i<N; i++) {
			if(Rs[i].r < l) continue;
			int &res = Dy[i][l];
			res = max(res, Rs[i].k);
			if(l) res = max(res, Dy[i][l-1]);
			for(RT &rt : Rl[l]) {
				if(l <= Rs[i].l) {
					res = max(res, Dy[rt.ix][l] + Rs[i].k);
				}else if(Rs[i].p != rt.p && Rs[i].h + rt.h <= W) {
					res = max(res, Dy[rt.ix][Rs[i].l] + Rs[i].k);
					res = max(res, Dy[i][rt.l] + rt.k);
				}
			}
			ans = max(ans, res);
//			printf("%d %d : %d\n", i, l, res);
		}
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

mat.cpp: In function 'int main()':
mat.cpp:29:61: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int p, l, r, h, k; scanf("%d%d%d%d%d", &p, &l, &r, &h, &k);
                                                             ^

• Subtask 1: 8 / 8
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 11 / 11
• Subtask 5: 43 / 43