제출 #51622

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
51622		tmwilliamlin168	Boat (APIO16_boat)	C++14	100 / 100	606 ms	9404 KiB

boat

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int mxN=500, M=1e9+7;
int n, a[mxN], b[mxN];
ll dp[mxN+1][2*mxN], c[2*mxN][mxN+1];
vector<int> pts;

inline ll modI(ll a, ll m) {
	return a<=1?a:(1-modI(m%a, a)*m)/a+m;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
//	cout << modI(2, M) << endl;
	cin >> n;
	for(int i=0; i<n; ++i) {
		cin >> a[i] >> b[i], --a[i];
		pts.push_back(a[i]);
		pts.push_back(b[i]);
	}
	sort(pts.begin(), pts.end());
	pts.resize(unique(pts.begin(), pts.end())-pts.begin());
	for(int i=1; i<pts.size(); ++i) {
		c[i][1]=pts[i]-pts[i-1];
		for(int j=2; j<=n; ++j)
			c[i][j]=c[i][j-1]*(pts[i]-pts[i-1]+j-1)%M*modI(j, M)%M;
	}
	for(int i=0; i<pts.size(); ++i)
		dp[0][i]=1;
	for(int i=1; i<=n; ++i) {
		dp[i][0]=1;
		for(int j=1; j<pts.size(); ++j) {
			dp[i][j]=dp[i][j-1];
			for(int k=i, n2=0; k; --k) {
				if(pts[j]>a[k-1]&&pts[j]<=b[k-1]) {
					++n2;
					dp[i][j]+=dp[k-1][j-1]*c[j][n2]%M;//, cout << c[j][i-k] << " ";
				}
			}
//			cout << endl;
			dp[i][j]%=M;
//			cout << i << " " << j << " " << dp[i][j] << endl;
		}
	}
	cout << dp[n][pts.size()-1]-1;
}

컴파일 시 표준 에러 (stderr) 메시지

boat.cpp: In function 'int main()':
boat.cpp:28:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<pts.size(); ++i) {
               ~^~~~~~~~~~~
boat.cpp:33:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<pts.size(); ++i)
               ~^~~~~~~~~~~
boat.cpp:37:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=1; j<pts.size(); ++j) {
                ~^~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42