Submission #43433715

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const int MAXN = 4010,INF = 1e9;

void tomin(int& x,int y){
	x=min(x,y);
}

int n,q;

int cnt[MAXN];

int dp[MAXN][MAXN][2];

int main(){
	cin>>n>>q;
	rep(i,1,q){
		int l,r;cin>>l>>r;
		if(l>1)cnt[l-1]++;
		if(r<n)cnt[r]++;
	}
	int num = 0;
	rep(i,1,n-1){
		num += (cnt[i] != 0);
	}	

	if(!num){
		printf("0 %d\n",q);
		exit(0);
	}

	int d = 1;
	while((1<<d)-1 < num)d++;

	//

	int rest = num - ((1<<(d-1))-1);

	rep(i,0,n)rep(j,0,n)rep(k,0,1)dp[i][j][k] = INF;

	dp[0][0][0] = 0;

	rep(i,0,n-1)rep(j,0,n)rep(k,0,1)if(dp[i][j][k] != INF){
		int val = dp[i][j][k];

		if(!cnt[i+1]){
			tomin(dp[i+1][j][k],val);
			continue;
		}

		rep(h,0,1){
			if(h && k)continue;

			tomin(dp[i+1][j+h][h],val + h * cnt[i+1] * 2);
		}
	}

	int ans = min(dp[n][rest][0],dp[n][rest][1]);
	
	cout<<d<<" "<<ans<<endl;
    return 0;
}

Submission Info

Judge Result