제출 #18078

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
18078		comet	매트 (KOI15_mat)	C++98	21 / 100	10 ms	1212 KiB

mat

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

int N,W;
struct mat{
	int p,l,r,h,k;
}a[100];

bool cross(int x,int y){
	if(a[x].r<=a[y].l)return 0;
	if(a[x].l>=a[y].r)return 0;
	if(a[x].p==a[y].p)return 1;
	if(a[x].h+a[y].h<=W)return 0;
	return 1;
}

int main(){

	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[i]=mat{p,l,r,h,k};
	}

	int ans=0;
	for(int i=(1<<N)-1;i>0;i--){
		vector<int> s;
		int sum=0;
		for(int j=0;j<N;j++){
			if(i>>j&1){
				s.push_back(j);
				sum+=a[j].k;
			}
		}
		bool ok=true;
		for(int j=0;j<s.size();j++){
			for(int k=j+1;k<s.size();k++){
				if(cross(s[j],s[k])){
					ok=false;
					goto apple;
				}
			}
		}
		ans=max(ans,sum);
		apple:;
	}

	printf("%d\n",ans);

	return 0;
}

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