Submission #65192

---

Source Code Expand

#include<cstdio>
#include<vector>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

const int M=1000000007;

struct interval{
	int a,b;
	bool operator<(const interval &I)const{ return a<I.a || a==I.a && b<I.b; }
};

int main(){
	int n,m; scanf("%d%d",&n,&m);
	static interval I[100000];
	rep(i,m) scanf("%d%d",&I[i].a,&I[i].b);

	vector<int> X;
	X.push_back(0);
	X.push_back(n);
	rep(i,m){
		X.push_back(I[i].a);
		X.push_back(I[i].b);
	}
	sort(X.begin(),X.end());
	X.erase(unique(X.begin(),X.end()),X.end());

	sort(I,I+m);

	// dp[j][k] := (0, X[j]] を二本以上で覆い, (X[j], X[k]] を一本で覆い, (X[k], n] を覆っていないような電車の選び方の数
	static int dp[402][402];
	dp[0][0]=1;
	rep(i,m){
		int t=lower_bound(X.begin(),X.end(),I[i].b)-X.begin();

		// rep(j,X.size()) for(int k=j;k<X.size();k++) {
		for(int j=X.size()-1;j>=0;j--) for(int k=X.size()-1;k>=j;k--) {
			// ( 0, x2] は二本以上で覆った
			// (x2, x1] は一本で覆った
			// (x1,  n] はまだ覆ってない
			int x2=X[j],x1=X[k];

			// 電車 i を使う
			if(I[i].a<=x2+1){
				if(x1<I[i].b){
					dp[k][t]+=dp[j][k];
					dp[k][t]%=M;
				}
				else if(x2<I[i].b){
					dp[t][k]+=dp[j][k];
					dp[t][k]%=M;
				}
				else{ // I[i].b<=x2
					dp[j][k]+=dp[j][k];
					dp[j][k]%=M;
				}
			}
		}
	}

	printf("%d\n",dp[X.size()-1][X.size()-1]);

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:17:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:19:40: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result