#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++){
~^~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
| # |
결과 |
실행 시간 |
메모리 |
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 |
- |
