제출 #95357

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
95357		KLPP	Pinball (JOI14_pinball)	C++14	0 / 100	2 ms	1656 KiB

pinball

#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
#define INF 1000000000000000
lld DP[500][500][500];
lld device[1000000][4];
vector<int> clr;

int main(){
	int m,n;
	cin>>m>>n;
	vector<int> table;
	table.push_back(0);
	table.push_back(n-1);
	for(int i=0;i<m;i++){
		cin>>device[i][0]>>device[i][1]>>device[i][2]>>device[i][3];
		for(int j=0;j<3;j++)device[i][j]--,table.push_back(device[i][j]);
	}
	sort(table.begin(),table.end());
	for(int i=0;i<table.size();i++){
		if(i==table.size()-1 || table[i]!=table[i+1]){
			clr.push_back(table[i]);
		}
	}//cout<<clr.size()<<endl;
	for(int i=0;i<m;i++){
		for(int j=0;j<3;j++){
			int lo,hi;
			lo=0;
			hi=clr.size()-1;
			while(hi-lo>0){
				int mid=(hi+lo)/2;
				if(clr[mid]==device[i][j]){
					hi=lo=mid;
				}
				if(clr[mid]>device[i][j]){
					hi=mid-1;
				}
				if(clr[mid]<device[i][j]){
					lo=mid+1;
				}
			}
			device[i][j]=lo;
			//cout<<lo<<" ";
		}//cout<<endl;
	}
	for(int i=0;i<=m;i++){
		for(int j=0;j<clr.size();j++){
			for(int k=0;k<clr.size();k++){
				DP[i][j][k]=INF;
			}
		}
	}
	for(int j=0;j<clr.size();j++)DP[0][j][j]=0;
	for(int i=0;i<m;i++){
		for(int j=0;j<clr.size();j++){
			for(int k=j;k<clr.size();k++){
				//cout<<DP[i][j][k]<<" "<<i<<" "<<j<<" "<<k<<endl;
				//if(DP[i][j][k]==0)cout<<i<<j<<k<<endl;
				int A,B,C;
				lld D;
				A=device[m-1-i][0];
				B=device[m-1-i][1];
				C=device[m-1-i][2];
				D=device[m-1-i][3];
				if(DP[i][j][k]!=INF){
					DP[i+1][j][k]=min(DP[i+1][j][k],DP[i][j][k]);
					if(j<=C && C<=k)DP[i+1][min(j,A)][max(k,B)]=min(DP[i+1][min(j,A)][max(k,B)],DP[i][j][k]+D);
				}
			}
		}
	}
	cout<<DP[m][0][clr.size()-1]<<endl;
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

pinball.cpp: In function 'int main()':
pinball.cpp:21:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<table.size();i++){
              ~^~~~~~~~~~~~~
pinball.cpp:22:7: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(i==table.size()-1 || table[i]!=table[i+1]){
      ~^~~~~~~~~~~~~~~~
pinball.cpp:48:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<clr.size();j++){
               ~^~~~~~~~~~~
pinball.cpp:49:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=0;k<clr.size();k++){
                ~^~~~~~~~~~~
pinball.cpp:54:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<clr.size();j++)DP[0][j][j]=0;
              ~^~~~~~~~~~~
pinball.cpp:56:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<clr.size();j++){
               ~^~~~~~~~~~~
pinball.cpp:57:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int k=j;k<clr.size();k++){
                ~^~~~~~~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 49