oj.uz

Submission #960008

# Submission time Handle Problem Language Result Execution time Memory
960008 2024-04-09T12:49:16 Z LCJLY Pinball (JOI14_pinball) C++14
29 / 100
 233 ms 12284 KB 
#include <bits/stdc++.h>
using namespace std;	
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<long long,int>pii;
//typedef pair<pii,pii>pi2;
typedef array<int,3>pi2;

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,m;
array<int,4>arr[1005]; //l r to cost
int dp[2][605][605];
int sz;

void solve(){
	cin >> n >> m;
	
	vector<int>v;
	for(int x=0;x<n;x++){
		cin >> arr[x][0] >> arr[x][1] >> arr[x][2] >> arr[x][3];
		v.push_back(arr[x][0]);
		v.push_back(arr[x][1]);
		v.push_back(arr[x][2]);
	}
	v.push_back(1);
	v.push_back(m);
	
	sort(v.begin(),v.end());
	v.resize(unique(v.begin(),v.end())-v.begin());
	
	for(int x=0;x<n;x++){
		arr[x][0]=lower_bound(v.begin(),v.end(),arr[x][0])-v.begin()+1;
		arr[x][1]=lower_bound(v.begin(),v.end(),arr[x][1])-v.begin()+1;
		arr[x][2]=lower_bound(v.begin(),v.end(),arr[x][2])-v.begin()+1;
	}
	
	sz=lower_bound(v.begin(),v.end(),m)-v.begin()+1;
	
	
	for(int x=0;x<605;x++){
		for(int y=0;y<605;y++){
			dp[0][x][y]=1e15;
			dp[1][x][y]=1e15;
		}
	}
	
	dp[0][1][0]=0;
	for(int x=n-1;x>=0;x--){
		for(int l=1;l<=sz;l++){
			for(int r=0;r<=sz;r++){
				dp[1][l][r]=min(dp[1][l][r],dp[0][l][r]);
				
				int a=arr[x][0];
				int b=arr[x][1];
				int k=arr[x][2];
				int cost=arr[x][3];
				
				if(r<l){
					dp[1][a][b]=min(dp[1][a][b],dp[0][l][r]+cost);
				}
				if(k>=l&&k<=r){
					dp[1][min(a,l)][max(b,r)]=min(dp[1][min(a,l)][max(b,r)],dp[0][l][r]+cost);
				}
			}
		}
		
		for(int l=1;l<=sz;l++){
			for(int r=0;r<=sz;r++){
				dp[0][l][r]=dp[1][l][r];
				dp[1][l][r]=1e15;
			}
		}
	}
	
	int hold=dp[0][1][sz];
	if(hold>=1e15){
		cout << -1;
	}
	else cout << hold;
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5976 KB Output is correct
2 Correct 2 ms 6096 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Correct 4 ms 6236 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Correct 2 ms 5980 KB Output is correct
8 Correct 2 ms 5980 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5976 KB Output is correct
2 Correct 2 ms 6096 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Correct 4 ms 6236 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Correct 2 ms 5980 KB Output is correct
8 Correct 2 ms 5980 KB Output is correct
9 Correct 5 ms 5980 KB Output is correct
10 Correct 26 ms 5980 KB Output is correct
11 Correct 44 ms 5980 KB Output is correct
12 Correct 198 ms 6200 KB Output is correct
13 Correct 233 ms 6200 KB Output is correct
14 Correct 229 ms 6196 KB Output is correct

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5976 KB Output is correct
2 Correct 2 ms 6096 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Correct 4 ms 6236 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Correct 2 ms 5980 KB Output is correct
8 Correct 2 ms 5980 KB Output is correct
9 Correct 5 ms 5980 KB Output is correct
10 Correct 26 ms 5980 KB Output is correct
11 Correct 44 ms 5980 KB Output is correct
12 Correct 198 ms 6200 KB Output is correct
13 Correct 233 ms 6200 KB Output is correct
14 Correct 229 ms 6196 KB Output is correct
15 Correct 5 ms 5980 KB Output is correct
16 Runtime error 7 ms 12284 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5976 KB Output is correct
2 Correct 2 ms 6096 KB Output is correct
3 Correct 2 ms 5980 KB Output is correct
4 Correct 2 ms 5980 KB Output is correct
5 Correct 4 ms 6236 KB Output is correct
6 Correct 2 ms 5980 KB Output is correct
7 Correct 2 ms 5980 KB Output is correct
8 Correct 2 ms 5980 KB Output is correct
9 Correct 5 ms 5980 KB Output is correct
10 Correct 26 ms 5980 KB Output is correct
11 Correct 44 ms 5980 KB Output is correct
12 Correct 198 ms 6200 KB Output is correct
13 Correct 233 ms 6200 KB Output is correct
14 Correct 229 ms 6196 KB Output is correct
15 Correct 5 ms 5980 KB Output is correct
16 Runtime error 7 ms 12284 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -