oj.uz

Submission #946755

# Submission time Handle Problem Language Result Execution time Memory
946755 2024-03-15T03:29:28 Z vjudge1 Treatment Project (JOI20_treatment) C++17
0 / 100
 42 ms 7624 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
#define ff first
#define ss second
#define rep(i,s,f) for(int i = s;i < f;i++)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define pb push_back

void solve(){
	
	int n,m;
	cin >> n >> m;
	vector<array<int,4>> a;
	for(int i = 0;i < m;i++){
		int t,l,r,c;
		cin >> t >> l >> r >> c;
		a.pb({t,l,r,c});
	}
	sort(all(a));
	int ans = INT_MAX;
	for(int mask = 0;mask < (1 << m);mask++){
		vector<array<int,4>> v; 
		for(int i = 0;i < m;i++){
			if(mask >> i & 1){
				v.pb(a[i]);
			}
		}
		int sum = 0;
		vector<pair<int,int>> line;
		int lst = -1; 
		for(auto[t,l,r,c] : v){
			sum += c;
			if(lst == -1){
				line.pb({l,r});
				lst = t;
			} else{
				int res = t - lst;
				for(auto[l1,r1] : line){
					if(l1 != 1){
						l1 += res;
					}
					if(r1 != n){
						r1 -= res;
					}
				}
				lst = t;
				line.pb({l,r});
			}
		}
		vector<pair<int,int>> nw;
		for(auto [l,r] : line){
			if(l <= r){
				nw.pb({l,r});
			}
		}
		sort(all(nw));
		int mxl = -1,mxr = -1;
		for(auto [l,r] : nw){
			if(mxl == -1){
				mxl = l;
				mxr = r;
			} else{
				if(l <= mxr){
					mxr = max(mxr,r);
				}
			}
		}
		if(mxl == 1 && mxr == n){
			ans = min(ans,sum);
		}
	}
	cout << ans;
		
}
 
signed main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	int t = 1;
	//~ cin >> t;
	while(t--){
		solve();
	}
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 7624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 30 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 30 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 42 ms 7624 KB Output isn't correct
2 Halted 0 ms 0 KB -