답안 #18083

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
18083	2016-01-20T05:01:08 Z	comet	매트 (KOI15_mat)	C++14	컴파일 오류	0 ms	0 KB

mat

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

using namespace std;
typedef pair<int,int> pp;

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

int N,W;
int sz[2];

int dp[3010][3010];
int opt[2][3010][3010];

priority_queue<pp,vector<pp>,greater<pp>> Qi[3010],Qj[3010];
int Maxi[3010];
int Maxj[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(){
	
	scanf("%d%d",&N,&W);

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

	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<=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;
/*
			while(!Qi[j].empty()&&Qi[j].top().first<=a[0][i].l){
				int k=Qi[j].top().second;
				Qi[j].pop();
				if(dp[Maxi[j]][j]<dp[k][j]){
					Maxi[j]=k;
				}
			}

			while(!Qj[i].empty()&&Qj[i].top().first<=a[1][j].l){
				int k=Qj[i].top().second;
				Qj[i].pop();
				if(dp[i][Maxj[i]]<dp[i][k]){
					Maxj[i]=k;
				}
			}

			if(dp[i][j]<dp[Maxi[j]][j]+a[0][i].k){
				dp[i][j]=dp[Maxi[j]][j]+a[0][i].k;
				opt[0][i][j]=Maxi[j];
				opt[1][i][j]=opt[1][Maxi[j]][j];
			}

			if(dp[i][j]<dp[i][Maxj[i]]+a[1][j].k){
				dp[i][j]=dp[i][Maxj[i]]+a[1][j].k;
				opt[0][i][j]=opt[0][i][Maxj[i]];
				opt[1][i][j]=Maxj[i];
			}
*/

			for(int k=0;k<i;k++){
				if(min(a[0][k].r,a[1][opt[1][k][j]])>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[0][i][j]=k;
					opt[1][i][j]=opt[1][k][j];
				}
			}

			for(int k=0;k<j;k++){
				if(min(a[1][k].r,a[0][opt[0][i][k]])>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[1][i][j]=k;
					opt[0][i][j]=opt[0][i][k];
				}
			}

			// Qi[j].push(pp(max(a[0][i].r,a[1][opt[1][i][j]].r),i));
			// Qj[i].push(pp(max(a[1][j].r,a[0][opt[0][i][j]].r),j));
			
		}
	}

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

	return 0;
}

Compilation message

mat.cpp: In function ‘int main()’:
mat.cpp:50:30: warning: narrowing conversion of ‘1.0e+9’ from ‘double’ to ‘int’ inside { } [-Wnarrowing]
   a[i][sz[i]]=mat{1e9,1e9,0,0};
                              ^
mat.cpp:50:30: warning: narrowing conversion of ‘1.0e+9’ from ‘double’ to ‘int’ inside { } [-Wnarrowing]
mat.cpp:92:40: error: no matching function for call to ‘min(int&, mat&)’
     if(min(a[0][k].r,a[1][opt[1][k][j]])>a[0][i].l)continue;
                                        ^
mat.cpp:92:40: note: candidates are:
In file included from /usr/include/c++/4.9/algorithm:61:0,
                 from mat.cpp:2:
/usr/include/c++/4.9/bits/stl_algobase.h:194:5: note: template<class _Tp> const _Tp& std::min(const _Tp&, const _Tp&)
     min(const _Tp& __a, const _Tp& __b)
     ^
/usr/include/c++/4.9/bits/stl_algobase.h:194:5: note:   template argument deduction/substitution failed:
mat.cpp:92:40: note:   deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘mat’)
     if(min(a[0][k].r,a[1][opt[1][k][j]])>a[0][i].l)continue;
                                        ^
In file included from /usr/include/c++/4.9/algorithm:61:0,
                 from mat.cpp:2:
/usr/include/c++/4.9/bits/stl_algobase.h:240:5: note: template<class _Tp, class _Compare> const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^
/usr/include/c++/4.9/bits/stl_algobase.h:240:5: note:   template argument deduction/substitution failed:
mat.cpp:92:40: note:   deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘mat’)
     if(min(a[0][k].r,a[1][opt[1][k][j]])>a[0][i].l)continue;
                                        ^
In file included from /usr/include/c++/4.9/algorithm:62:0,
                 from mat.cpp:2:
/usr/include/c++/4.9/bits/stl_algo.h:3439:5: note: template<class _Tp> _Tp std::min(std::initializer_list<_Tp>)
     min(initializer_list<_Tp> __l)
     ^
/usr/include/c++/4.9/bits/stl_algo.h:3439:5: note:   template argument deduction/substitution failed:
mat.cpp:92:40: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
     if(min(a[0][k].r,a[1][opt[1][k][j]])>a[0][i].l)continue;
                                        ^
In file included from /usr/include/c++/4.9/algorithm:62:0,
                 from mat.cpp:2:
/usr/include/c++/4.9/bits/stl_algo.h:3444:5: note: template<class _Tp, class _Compare> _Tp std::min(std::initializer_list<_Tp>, _Compare)
     min(initializer_list<_Tp> __l, _Compare __comp)
     ^
/usr/include/c++/4.9/bits/stl_algo.h:3444:5: note:   template argument deduction/substitution failed:
mat.cpp:92:40: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
     if(min(a[0][k].r,a[1][opt[1][k][j]])>a[0][i].l)continue;
                                        ^
mat.cpp:101:40: error: no matching function for call to ‘min(int&, mat&)’
     if(min(a[1][k].r,a[0][opt[0][i][k]])>a[1][j].l)continue;
                                        ^
mat.cpp:101:40: note: candidates are:
In file included from /usr/include/c++/4.9/algorithm:61:0,
                 from mat.cpp:2:
/usr/include/c++/4.9/bits/stl_algobase.h:194:5: note: template<class _Tp> const _Tp& std::min(const _Tp&, const _Tp&)
     min(const _Tp& __a, const _Tp& __b)
     ^
/usr/include/c++/4.9/bits/stl_algobase.h:194:5: note:   template argument deduction/substitution failed:
mat.cpp:101:40: note:   deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘mat’)
     if(min(a[1][k].r,a[0][opt[0][i][k]])>a[1][j].l)continue;
                                        ^
In file included from /usr/include/c++/4.9/algorithm:61:0,
                 from mat.cpp:2:
/usr/include/c++/4.9/bits/stl_algobase.h:240:5: note: template<class _Tp, class _Compare> const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^
/usr/include/c++/4.9/bits/stl_algobase.h:240:5: note:   template argument deduction/substitution failed:
mat.cpp:101:40: note:   deduced conflicting types for parameter ‘const _Tp’ (‘int’ and ‘mat’)
     if(min(a[1][k].r,a[0][opt[0][i][k]])>a[1][j].l)continue;
                                        ^
In file included from /usr/include/c++/4.9/algorithm:62:0,
                 from mat.cpp:2:
/usr/include/c++/4.9/bits/stl_algo.h:3439:5: note: template<class _Tp> _Tp std::min(std::initializer_list<_Tp>)
     min(initializer_list<_Tp> __l)
     ^
/usr/include/c++/4.9/bits/stl_algo.h:3439:5: note:   template argument deduction/substitution failed:
mat.cpp:101:40: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
     if(min(a[1][k].r,a[0][opt[0][i][k]])>a[1][j].l)continue;
                                        ^
In file included from /usr/include/c++/4.9/algorithm:62:0,
                 from mat.cpp:2:
/usr/include/c++/4.9/bits/stl_algo.h:3444:5: note: template<class _Tp, class _Compare> _Tp std::min(std::initializer_list<_Tp>, _Compare)
     min(initializer_list<_Tp> __l, _Compare __comp)
     ^
/usr/include/c++/4.9/bits/stl_algo.h:3444:5: note:   template argument deduction/substitution failed:
mat.cpp:101:40: note:   mismatched types ‘std::initializer_list<_Tp>’ and ‘int’
     if(min(a[1][k].r,a[0][opt[0][i][k]])>a[1][j].l)continue;
                                        ^
mat.cpp:36:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&N,&W);
                     ^
mat.cpp:44:37: 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);
                                     ^