Submission #1083771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1083771		vjudge1	Fire (BOI24_fire)	C++17	14 / 100	95 ms	464 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
#define for1(i,x,n) for(int i=x;i<=n;i++)
#define for2(i,x,n) for(int i=x;i>=n;i--)
#define int ll

typedef long long ll;
typedef pair<int,int> pii;

const ll maxn=2e5+69;
const ll mod=1e9+7;
const ll inf=1e18;
int n,m;
pii a[maxn];
void sol()
{
    cin >> n>> m;
    for1(i,1,n)
    {
        cin >>a[i].fi>> a[i].se;
        if (a[i].se<a[i].fi) a[i].se+=m;
//        cerr<<n<< "adsa\n";
    }
    sort(a+1,a+1+n);
    int res=inf;
    for1(mask,1,(1<<n)-1)
    {
        int l=-1,r=-1;
        bool flag=1;
        for1(i,1,n)
        {
            if (mask>>(i-1)&1)
            {
                if (l==-1) l=a[i].fi;
                if (r!=-1 && r<a[i].fi)
                {
                    flag=0;
                    break;
                }
                r=max(r,a[i].se);
            }
            if (flag && r-l>=m)
            {
                res=min(res,(ll)__builtin_popcount(mask));
            }
        }
    }
    if (res==inf) cout << "-1";
    else cout << res;

}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("fire.inp","r",stdin);
//    freopen("fire.ans","w",stdout);
    int t=1;//cin >> t;
    while (t--)
    {
        sol();
    }
}

• Subtask 1: 14 / 14
• Subtask 2: 0 / 17
• Subtask 3: 0 / 9
• Subtask 4: 0 / 13
• Subtask 5: 0 / 21
• Subtask 6: 0 / 26