oj.uz

Submission #51602

# Submission time Handle Problem Language Result Execution time Memory
51602 2018-06-19T04:58:48 Z tmwilliamlin168 Boat (APIO16_boat) C++14
0 / 100
 101 ms 8184 KB 
#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];
			if(pts[j]<=a[i-1]||pts[j]>b[i-1])
				continue;
			for(int k=0; k<i; ++k)
				dp[i][j]+=dp[k][j-1]*c[j][i-k]%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;
}

Compilation message

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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 8184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 8184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 8184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 101 ms 8184 KB Output isn't correct
2 Halted 0 ms 0 KB -