Submission #889219

#	Time	Username	Problem	Language	Result	Execution time	Memory
889219		Nurislam	Pinball (JOI14_pinball)	C++17	11 / 100	5 ms	600 KiB

pinball

#include <bits/stdc++.h>
using namespace std;/*
<<<<It's never too late for a new beginning in your life>>>>
Today is hard
  tomorrow will worse
  but the day after tomorrow will be the sunshine..
 
HARD WORK BEATS TALENT WHEN TALENT DOESN'T WORK HARD............
Never give up  */
//The most CHALISHKANCHIK
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define int long long
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pair<int,int> > vii;
const int N = 2e5+50, inf = 1e18;
vector<pair<pii, pair<pii, int> > > v;
vector<pair<pii, pii> > re;

int n, m;
bool us[N];
int ch(){
	int ans = 0;
	set<pii> st;
	st.insert({1, n});
	for(int i = 0; i < m; i++){
		if(us[i])continue;
		vii  todel, toins;
		toins.pb({re[i].ss.ss, re[i].ss.ss});
		int l = re[i].ff.ff, r = re[i].ff.ss;
		ans += re[i].ss.ff;
		for(auto [_l, _r]:st){
			if(_l <= l && r <= _r){
				todel.pb({_l, _r});
				if(_l!=l)toins.pb({_l, l-1});
				if(_r!=r)toins.pb({r+1, _r});
			}else if(_l <= l && _r <= r && l <= _r){
				todel.pb({_l, _r});
				if(_l!=l)toins.pb({_l, l-1});
			}else if(_r >= r && _l >= l && _l <= r){
				todel.pb({_l, _r});
				if(_r!=r)toins.pb({r+1, _r});
			}else if(l <= _l && _r <= r){
				todel.pb({_l, _r});
			}
		}
		for(auto x:todel)st.erase(st.find(x));
		for(auto x:toins)st.insert(x);
	}
	return (st.size() == 1 && ans!=0 ? ans : inf);
}
void solve(){
	cin >> m >> n;
	v.resize(m);
	re.resize(m);
	for(int i = 0; i < m; i++){
		cin >> v[i].ss.ff.ff >> v[i].ss.ff.ss >> v[i].ff.ss >> v[i].ff.ff;
		v[i].ss.ss = i;
		re[i] = {v[i].ss.ff, v[i].ff};
	}
	int ans = inf;
	//~ sort(rall(v));
	if(!ch()){
		cout << "-1\n";
		return;
	}
	for(int ms = 0; ms < (1 << m); ms++){
		for(int i = 0; i < m; i++){
			if((ms >> i) & 1){
				us[i] = 1;
			}else us[i] = 0;
		}
		//~ cout << ch() << '\n';
		ans = min(ans, ch());
	}
	cout << (ans == inf ? -1 : ans) << '\n';
}
main(){
  //~ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  int t = 1;
  //~ cin >> t;
  while(t--){
    solve();
  }
}

Compilation message (stderr)

pinball.cpp:82:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   82 | main(){
      | ^~~~

• Subtask 1: 11 / 11
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 49