oj.uz

Submission #95361

# Submission time Handle Problem Language Result Execution time Memory
95361 2019-01-30T17:37:26 Z KLPP Pinball (JOI14_pinball) C++14
29 / 100
 96 ms 6136 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 376 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 5 ms 1016 KB Output is correct
10 Correct 15 ms 2168 KB Output is correct
11 Correct 25 ms 2812 KB Output is correct
12 Correct 92 ms 5880 KB Output is correct
13 Correct 89 ms 6008 KB Output is correct
14 Correct 96 ms 6020 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 5 ms 1016 KB Output is correct
10 Correct 15 ms 2168 KB Output is correct
11 Correct 25 ms 2812 KB Output is correct
12 Correct 92 ms 5880 KB Output is correct
13 Correct 89 ms 6008 KB Output is correct
14 Correct 96 ms 6020 KB Output is correct
15 Correct 4 ms 1144 KB Output is correct
16 Runtime error 8 ms 6136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 632 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 5 ms 1016 KB Output is correct
10 Correct 15 ms 2168 KB Output is correct
11 Correct 25 ms 2812 KB Output is correct
12 Correct 92 ms 5880 KB Output is correct
13 Correct 89 ms 6008 KB Output is correct
14 Correct 96 ms 6020 KB Output is correct
15 Correct 4 ms 1144 KB Output is correct
16 Runtime error 8 ms 6136 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -