# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
955821 | vjudge1 | Pinball (JOI14_pinball) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#define ll long long
int m,n;
bool ok(vector<pair<int,pair<int,pair<int,int>>>> res)
{
int s, f;
s=res[res.size()-1].first;
f=res[res.size()-1].second.first;
res.pop_back();
while (!res.empty())
{
if (s<=res[res.size()-1].second.second.first && res[res.size()-1].second.second.first<=f)
{
s=min(s,res[res.size()-1].first);
f=max(f,res[res.size()-1].second.first);
}
else
return 0;
res.pop_back();
}
if (s==1 && f==n)
return 1;
return 0;
}
int main()
{
ll r=LLONG_MAX;
vector <pair<int,pair<int,pair<int,int>>>> v;
vector<pair<int,pair<int,pair<int,int>>>> res;
cin>>m>>n;
for (int i=0;i<m;i++)
{
int a, b, c, d;
cin>>a>>b>>c>>d;
v.push_back({a,{b,{c,d}}});
}
for (int i=1;i<(int)pow(2,m);i++)
{
res.clear();
int pom=1;
ll p=0;
while (pom<=i)
{
int k=pom&i;
if (k!=0)
{
int c=0;
while (!(k%2))
{
c++;
k/=2;
}
p+=v[c].second.second.second;
res.push_back(v[c]);
}
pom=pom<<1;
}
if (p<r && ok(res))
r=p;
}
if (r==LLONG_MAX)
r=-1;
cout<<r;
return 0;
}