oj.uz

Submission #18076

# Submission time Handle Problem Language Result Execution time Memory
18076 2016-01-19T23:56:05 Z comet 매트 (KOI15_mat) C++
32 / 100
 1000 ms 80808 KB 
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

struct mat{
	int l,r,h,k;
	bool operator<(const mat& r)const{
		return l<r.l;
	}
}a[2][3010];

int N,W;
int sz[2];

int dp[3010][3010];
int opt[3010][3010];
bool opti[3010][3010];

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

int main(){
	memset(opt,-1,sizeof(opt));

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

	for(int i=0;i<2;i++){
		sort(a[i],a[i]+sz[i]);
		a[i][sz[i]]=mat{1e9,1e9,0,0};
	}

	/*for(int i=0;i<2;i++,puts("")){
		for(int j=0;j<=sz[i];j++){
			printf("(%d,%d,%d,%d) ",a[i][j].l,a[i][j].r,a[i][j].h,a[i][j].k);
		}
	}
	puts("-----------------------------------------------------------------------");
*/
	for(int i=0;i<=sz[0];i++){
		for(int j=0;j<=sz[1];j++){

			dp[i][j]=-1e9;
			if(cross(i,j))continue;

			dp[i][j]=a[0][i].k+a[1][j].k;

			for(int k=0;k<i;k++){
				if(a[0][k].r>a[0][i].l)continue;
				if(cross(k,j))continue;

				if(opt[k][j]>=0&&a[opti[k][j]][opt[k][j]].r>a[0][i].l)continue;
				if(dp[i][j]<dp[k][j]+a[0][i].k){
					dp[i][j]=dp[k][j]+a[0][i].k;
					opt[i][j]=k;
					opti[i][j]=0;
				}
			}

			for(int k=0;k<j;k++){
				if(a[1][k].r>a[1][j].l)continue;
				if(cross(i,k))continue;

				if(opt[i][k]>=0&&a[opti[i][k]][opt[i][k]].r>a[1][j].l)continue;
				if(dp[i][j]<dp[i][k]+a[1][j].k){
					dp[i][j]=dp[i][k]+a[1][j].k;
					opt[i][j]=k;
					opti[i][j]=1;
				}
			}

			// apple:

			//printf("%d (%d,%d) ",dp[i][j],opt[i][j],opti[i][j]);

		}
		// puts("");
	}

	printf("%d\n",dp[sz[0]][sz[1]]);
}

Subtask #1
8.0 / 8.0

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

Subtask #2
13.0 / 13.0

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

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 80808 KB Output is correct
2 Correct 4 ms 80808 KB Output is correct
3 Incorrect 8 ms 80808 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 80808 KB Output is correct
2 Correct 24 ms 80808 KB Output is correct
3 Correct 28 ms 80808 KB Output is correct
4 Correct 28 ms 80808 KB Output is correct
5 Correct 32 ms 80808 KB Output is correct

Subtask #5
0.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 80808 KB Output is correct
2 Execution timed out 1000 ms 80804 KB Program timed out
3 Halted 0 ms 0 KB -