oj.uz

Submission #38448

# Submission time Handle Problem Language Result Execution time Memory
38448 2018-01-04T08:00:21 Z kajebiii 매트 (KOI15_mat) C++14
19 / 100
 563 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();
		Rl[Rs[i].r].push_back(Rs[i]);
	}
	int ans = 0;
	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[i][rt.l] + rt.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\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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 72940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 72940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 73112 KB Output is correct
2 Correct 443 ms 73112 KB Output is correct
3 Correct 453 ms 73112 KB Output is correct
4 Correct 489 ms 73112 KB Output is correct
5 Correct 16 ms 73256 KB Output is correct

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 73112 KB Output is correct
2 Incorrect 563 ms 73112 KB Output isn't correct
3 Halted 0 ms 0 KB -