Submission #946792

#	Time	Username	Problem	Language	Result	Execution time	Memory
946792		vjudge1	Treatment Project (JOI20_treatment)	C++17	0 / 100	39 ms	6356 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

const int INF = 1e18;

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 = INF;
	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(int j = 0;j < line.size();j++){
					if(line[j].ff != 1){
						line[j].ff += res;
					} 
					if(line[j].ss != n){
						line[j].ss -= 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 + 1){
					mxr = max(mxr,r);
				}
			}
		}
		if(mxl == 1 && mxr == n){
			ans = min(ans,sum);
		}
	}
	if(ans == INF){
		ans = -1;
	}
	cout << ans; 	
		
}
 
signed main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	
	int t = 1;
	//~ cin >> t;
	while(t--){
		solve();
	}
}
	

Compilation message (stderr)

treatment.cpp: In function 'void solve()':
treatment.cpp:44:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int j = 0;j < line.size();j++){
      |                   ~~^~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 61