Submission #946755

#	Time	Username	Problem	Language	Result	Execution time	Memory
946755		vjudge1	Treatment Project (JOI20_treatment)	C++17	0 / 100	42 ms	7624 KiB

treatment

#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
• Subtask 2: 0 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 61