oj.uz

Submission #82895

# Submission time Handle Problem Language Result Execution time Memory
82895 2018-11-02T16:09:56 Z leejseo 매트 (KOI15_mat) C++11
100 / 100
 260 ms 71444 KB 
#include <bits/stdc++.h>
using namespace std;

int N, W, ans;

int value[3001];

struct cor{
	int x, i;
	bool r;
	cor(int i_, int x_, bool r_){
		i = i_, x = x_;
		r = r_;
	}
	bool operator < (const cor &other) const{
		return x < other.x;		
	}
};

struct MAT{
	int P, L, R, H, K;
	MAT(int P_, int L_, int R_, int H_, int K_){
		P = P_, L = L_, R = R_, H = H_, K = K_;
	}
	bool meet(const MAT &MT) const{
		if (R <= MT.L || L >= MT.R) return false;
		if (P == MT.P) return true;
		return ((MT.H) + H) > W;
	}
	bool operator < (const MAT &MT) const{
		return R != MT.R ? R < MT.R : L < MT.L;
	}
};

vector<MAT> A;
vector<cor> B;
int D[3001][6001], Left[3001];

void input(){
	cin >> N >> W;
	int P, L, R, H, K;
	for (int i=0; i<N; i++){
		cin >> P >> L >> R >> H >> K;
		A.push_back(MAT(P, L, R, H, K));
	}
}

void init(){
	sort(A.begin(), A.end());
	for (int i=0; i<N; i++){
		value[i] = A[i].K;
		B.push_back(cor(i, A[i].L, false));
		B.push_back(cor(i, A[i].R, true));
	}
	sort(B.begin(), B.end());
	for (int j=0; j<2*N; j++){
		if (B[j].r) continue;
		Left[B[j].i] = j;
	}
}

void solve(){
	for (int i=0; i<N; i++){
		for (int j=0; j<2*N; j++){
			if (A[i].R < B[j].x) break;
			D[i][j] = A[i].K;
			if (j > 0) D[i][j] = max(D[i][j], D[i][j-1]);
			if (B[j].r){
				int k = B[j].i;
				if (A[k].R <= A[i].L){
					D[i][j] = max(D[i][j], D[k][j] + A[i].K);
				}
				else if (!A[i].meet(A[k])){
					if (A[k].L < A[i].L){
						int h = upper_bound(B.begin(), B.end(), cor(-1, A[i].L, 0)) - B.begin();
						D[i][j] = max(D[i][j], D[k][h-1] + A[i].K);
					}
					else{
						int h = upper_bound(B.begin(), B.end(), cor(-1, A[k].L, 0)) - B.begin();
						D[i][j] = max(D[i][j], D[i][h-1] + A[k].K);
					}
				}
			}
			ans = max(ans, D[i][j]);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	input();
	init();
	solve();
	cout << ans << endl;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 440 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 2 ms 488 KB Output is correct

Subtask #2
13.0 / 13.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1604 KB Output is correct
2 Correct 3 ms 1616 KB Output is correct
3 Correct 3 ms 1616 KB Output is correct
4 Correct 3 ms 1616 KB Output is correct
5 Correct 3 ms 1744 KB Output is correct

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 57992 KB Output is correct
2 Correct 113 ms 57992 KB Output is correct
3 Correct 113 ms 58244 KB Output is correct
4 Correct 109 ms 58244 KB Output is correct
5 Correct 107 ms 62244 KB Output is correct

Subtask #5
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 63748 KB Output is correct
2 Correct 246 ms 63748 KB Output is correct
3 Correct 260 ms 63748 KB Output is correct
4 Correct 233 ms 63748 KB Output is correct
5 Correct 224 ms 63748 KB Output is correct
6 Correct 109 ms 63748 KB Output is correct
7 Correct 253 ms 63748 KB Output is correct
8 Correct 213 ms 63748 KB Output is correct
9 Correct 231 ms 71444 KB Output is correct
10 Correct 215 ms 71444 KB Output is correct