Submission #95361

#	Time	Username	Problem	Language	Result	Execution time	Memory
95361		KLPP	Pinball (JOI14_pinball)	C++14	29 / 100	96 ms	6136 KiB

pinball

#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
#define INF 1000000000000000
lld DP[600][600];
lld NEXT[600][600];
lld device[100000][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 j=0;j<clr.size();j++){
		for(int k=0;k<clr.size();k++){
			DP[j][k]=INF;
		}
	}
	
	for(int j=0;j<clr.size();j++)DP[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++){
				NEXT[j][k]=INF;	
			}
		}
		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[j][k]!=INF){
					NEXT[j][k]=min(NEXT[j][k],DP[j][k]);
					if(j<=C && C<=k)NEXT[min(j,A)][max(k,B)]=min(NEXT[min(j,A)][max(k,B)],DP[j][k]+D);
				}
			}
		}
		for(int j=0;j<clr.size();j++){
			for(int k=j;k<clr.size();k++){
				DP[j][k]=NEXT[j][k];	
			}
		}
	}
	if(DP[0][clr.size()-1]!=INF)cout<<DP[0][clr.size()-1]<<endl;
	else cout<<-1<<endl;
	return 0;
}

Compilation message (stderr)

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

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