oj.uz

Submission #18078

# Submission time Handle Problem Language Result Execution time Memory
18078 2016-01-20T03:48:47 Z comet 매트 (KOI15_mat) C++
21 / 100
 10 ms 1212 KB 
#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.0 / 8.0

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

Subtask #2
13.0 / 13.0

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

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 1208 KB futex (syscall #202) was called by the program (disallowed syscall)
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 1208 KB SIGSEGV Segmentation fault
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 43.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1208 KB futex (syscall #202) was called by the program (disallowed syscall)
2 Halted 0 ms 0 KB -