#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
pinball.cpp:82:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
82 | main(){
| ^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
504 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
440 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
504 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
440 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Incorrect |
5 ms |
600 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
504 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
440 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Incorrect |
5 ms |
600 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
504 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
3 |
Correct |
1 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
440 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
1 ms |
348 KB |
Output is correct |
7 |
Correct |
1 ms |
348 KB |
Output is correct |
8 |
Correct |
1 ms |
348 KB |
Output is correct |
9 |
Incorrect |
5 ms |
600 KB |
Output isn't correct |
10 |
Halted |
0 ms |
0 KB |
- |