oj.uz

Submission #38538

# Submission time Handle Problem Language Result Execution time Memory
38538 2018-01-04T11:49:21 Z kajebiii 매트 (KOI15_mat) C++14
100 / 100
 509 ms 73256 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 72940 KB Output is correct
2 Correct 0 ms 72940 KB Output is correct
3 Correct 0 ms 72940 KB Output is correct
4 Correct 0 ms 72940 KB Output is correct
5 Correct 0 ms 72940 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 72940 KB Output is correct
2 Correct 0 ms 72940 KB Output is correct
3 Correct 0 ms 72940 KB Output is correct
4 Correct 0 ms 72940 KB Output is correct
5 Correct 0 ms 72940 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 72940 KB Output is correct
2 Correct 0 ms 72940 KB Output is correct
3 Correct 0 ms 72940 KB Output is correct
4 Correct 0 ms 72940 KB Output is correct
5 Correct 0 ms 72940 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 353 ms 73112 KB Output is correct
2 Correct 409 ms 73112 KB Output is correct
3 Correct 399 ms 73112 KB Output is correct
4 Correct 409 ms 73112 KB Output is correct
5 Correct 9 ms 73244 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 73112 KB Output is correct
2 Correct 486 ms 73112 KB Output is correct
3 Correct 459 ms 73112 KB Output is correct
4 Correct 509 ms 73112 KB Output is correct
5 Correct 253 ms 73244 KB Output is correct
6 Correct 293 ms 73112 KB Output is correct
7 Correct 296 ms 73244 KB Output is correct
8 Correct 26 ms 73244 KB Output is correct
9 Correct 49 ms 73256 KB Output is correct
10 Correct 33 ms 73244 KB Output is correct