oj.uz

답안 #57294

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
57294 2018-07-14T13:57:08 Z leejseo 매트 (KOI15_mat) C++
32 / 100
 315 ms 72444 KB 
#include <bits/stdc++.h>
using namespace std;

int N, W, ans = 0;

typedef 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{
		if (x != other.x) return x < other.x;
		return ((int) r) * i > ((int) other.r) * other.i;
	}
} cor;


typedef 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{
		if (R != MT.R) return R < MT.R;
		return L > MT.L;
	}
} MAT;

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

void input(){
	scanf("%d%d", &N, &W);
	int P, L, R, H, K;
	for (int i=0; i<N; i++){
		scanf("%d%d%d%d%d", &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++){
		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 i=0; i<N; i++){
		for (int j=0; j<N; j++){
			if (A[i].meet(A[j])) M[i][j] = 1;
		}
		for (int j=0; j<2*N; j++){
			if (B[j].i == i){
				if (!B[j].r) Left[i] = j;
			}
		}
	}
}

void DP(){
	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(!M[i][k]){
					if (A[k].L < A[i].L){
						D[i][j] = max(D[i][j], D[k][Left[i]] + A[i].K);
					}
					else{
						D[i][j] = max(D[i][j], D[i][Left[k]] + A[k].K);
					}
				}
			}
			ans = max(ans, D[i][j]);
		}
	}
}

int main(void){
	input();
	init();
	DP();
	printf("%d\n", ans);
}

Compilation message

mat.cpp: In function 'void input()':
mat.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &W);
  ~~~~~^~~~~~~~~~~~~~~~
mat.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d%d", &P, &L, &R, &H, &K);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 540 KB Output is correct
4 Correct 2 ms 540 KB Output is correct
5 Correct 2 ms 540 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 540 KB Output is correct
2 Correct 2 ms 712 KB Output is correct
3 Correct 2 ms 712 KB Output is correct
4 Correct 2 ms 712 KB Output is correct
5 Correct 2 ms 712 KB Output is correct

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 2128 KB Output is correct
2 Correct 4 ms 2152 KB Output is correct
3 Correct 5 ms 2152 KB Output is correct
4 Incorrect 4 ms 2152 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 176 ms 66720 KB Output is correct
2 Correct 185 ms 66720 KB Output is correct
3 Correct 189 ms 66920 KB Output is correct
4 Correct 176 ms 66920 KB Output is correct
5 Correct 150 ms 71016 KB Output is correct

Subtask #5
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 199 ms 72444 KB Output is correct
2 Correct 281 ms 72444 KB Output is correct
3 Correct 251 ms 72444 KB Output is correct
4 Correct 292 ms 72444 KB Output is correct
5 Correct 315 ms 72444 KB Output is correct
6 Correct 145 ms 72444 KB Output is correct
7 Correct 292 ms 72444 KB Output is correct
8 Incorrect 238 ms 72444 KB Output isn't correct
9 Halted 0 ms 0 KB -