oj.uz

Submission #95357

# Submission time Handle Problem Language Result Execution time Memory
95357 2019-01-30T17:24:35 Z KLPP Pinball (JOI14_pinball) C++14
0 / 100
 2 ms 1656 KB 
#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;
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 888 KB Output is correct
3 Correct 2 ms 1272 KB Output is correct
4 Correct 2 ms 1272 KB Output is correct
5 Correct 2 ms 1528 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Incorrect 2 ms 1656 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 888 KB Output is correct
3 Correct 2 ms 1272 KB Output is correct
4 Correct 2 ms 1272 KB Output is correct
5 Correct 2 ms 1528 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Incorrect 2 ms 1656 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 888 KB Output is correct
3 Correct 2 ms 1272 KB Output is correct
4 Correct 2 ms 1272 KB Output is correct
5 Correct 2 ms 1528 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Incorrect 2 ms 1656 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 888 KB Output is correct
3 Correct 2 ms 1272 KB Output is correct
4 Correct 2 ms 1272 KB Output is correct
5 Correct 2 ms 1528 KB Output is correct
6 Correct 2 ms 632 KB Output is correct
7 Incorrect 2 ms 1656 KB Output isn't correct
8 Halted 0 ms 0 KB -