oj.uz

Submission #158266

# Submission time Handle Problem Language Result Execution time Memory
158266 2019-10-16T01:33:21 Z maruii Boat (APIO16_boat) C++14
0 / 100
 8 ms 2296 KB 
#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
vector<int> xx(1);
int f[505][505], s[505], g[505][505], A[505], B[505];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	int N; cin >> N;
	for (int i = 1; i <= N; ++i) {
		cin >> A[i] >> B[i]; B[i]++;
		xx.push_back(A[i]);
		xx.push_back(B[i]);
	}
	sort(xx.begin(), xx.end());
	xx.erase(unique(xx.begin(), xx.end()), xx.end());
	for (int i = 1; i <= N; ++i) {
		f[i - 1][0] = 1;
		s[0] = f[i - 1][0];
		for (int j = 1; j + 1 < xx.size(); ++j) s[j] = (s[j - 1] + f[i - 1][j]) % mod;
		for (int j = 1; j + 1 < xx.size(); ++j) {
			if (A[i] <= xx[j] && xx[j + 1] <= B[i]) {
				long long n = xx[j + 1] - xx[j];
				f[i][j] = (n * s[j - 1] + g[i - 1][j]) % mod;
				g[i][j] = ((n + 1) * n / 2 % mod * s[j - 1] % mod + g[i - 1][j] * n % mod - n * (n - 1) / 2 % mod * f[i - 1][j] % mod + mod) % mod;
			}
			else {
				f[i][j] = f[i - 1][j];
				g[i][j] = g[i - 1][j];
			}
		}
	}
	int ans = 0;
	for (int i = 0; i + 1 < xx.size(); ++i) ans = (ans + f[N][i]) % mod;
	cout << ans;
	return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:21:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j + 1 < xx.size(); ++j) s[j] = (s[j - 1] + f[i - 1][j]) % mod;
                   ~~~~~~^~~~~~~~~~~
boat.cpp:22:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 1; j + 1 < xx.size(); ++j) {
                   ~~~~~~^~~~~~~~~~~
boat.cpp:35:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i + 1 < xx.size(); ++i) ans = (ans + f[N][i]) % mod;
                  ~~~~~~^~~~~~~~~~~

Subtask #1
0 / 9.0

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

Subtask #2
0 / 22.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

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