oj.uz

Submission #946760

# Submission time Handle Problem Language Result Execution time Memory
946760 2024-03-15T03:48:30 Z huyboy Treatment Project (JOI20_treatment) C++17
0 / 100
 41 ms 4936 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(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 == INT_MAX){
		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

treatment.cpp: In function 'void solve()':
treatment.cpp:42: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]
   42 |     for(int j = 0;j < line.size();j++){
      |                   ~~^~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 41 ms 4936 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 348 KB Output is correct
2 Correct 27 ms 448 KB Output is correct
3 Correct 27 ms 348 KB Output is correct
4 Incorrect 27 ms 448 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

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

Subtask #4
0 / 61.0

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