oj.uz

답안 #680714

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
680714 2023-01-11T16:03:49 Z MilosMilutinovic Boat (APIO16_boat) C++14
0 / 100
 8 ms 4180 KB 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;

typedef long long ll;

const int MOD = (int)1e9 + 7;
int ckadd(int a, int b) {
	return a + b >= MOD ? a + b - MOD : a + b;
}
int ckmul(int a, int b) {
	return (ll)a * b % MOD;
}
int bin_pow(int x, int k) {
	int r = 1;
	while(k) {
		if (k & 1) r = ckmul(r, x);
		x = ckmul(x, x);
		k /= 2;
	}
	return r;
}

const int N = 505;
int n;
int l[N];
int r[N];
int b[2 * N];
int dp[N][2 * N];
int ways[2 * N][N];
int fact[3 * N];
int inv[3 * N];

void init() {
	fact[0] = 1;
	for (int i = 1; i < 3 * N; i++) fact[i] = ckmul(fact[i - 1], i);
	inv[3 * N - 1] = bin_pow(fact[3 * N - 1], MOD - 2);
	for (int i = 3 * N - 1; i >= 1; i--) inv[i - 1] = ckmul(inv[i], i);
}
int C(int n, int k) {
	if (n < k) return 0;
	return ckmul(fact[n], ckmul(inv[k], inv[n - k]));
}

int main()
{
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	init();

	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &l[i], &r[i]);
		r[i]++;
		b[2 * i] = l[i];
		b[2 * i + 1] = r[i];
	}
	b[2 * n] = 0;
	sort(b, b + 2 * n + 1);
	int m = unique(b, b + 2 * n + 1) - b;
	for (int i = 0; i < n; i++) {
		l[i] = lower_bound(b, b + m, l[i]) - b;
		r[i] = lower_bound(b, b + m, r[i]) - b;
	}
	for (int i = 0; i < 2 * N; i++) {
		int prod = 1;
		int len = b[i + 1] - b[i];
		for (int j = 1; j <= n; j++) {
			prod = ckmul(prod, len + j - 1);
			ways[i][j] = ckmul(prod, inv[j]);
		}
	}
	dp[0][0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 1; j < m; j++) dp[i][j] = ckadd(dp[i][j - 1], dp[i][j]);
		for (int v = 0; v < m; v++) {
			if (b[v] < l[i] || r[i] <= b[v]) continue;
 			int d = b[v + 1] - b[v], c = 0;
			for (int f = i; f >= 0; f--) {
				if (b[v] >= l[f] && b[v] < r[f]) c++;
				dp[i + 1][v] = ckadd(dp[i + 1][v], ckmul(dp[f][v - 1], ways[v][c]));
			}
		}
	}
	for (int j = 1; j < m; j++)
		dp[n][j] = ckadd(dp[n][j], dp[n][j - 1]);
	int ans = 0;
	for (int i = 1; i <= n; i++)
		ans = ckadd(ans, dp[i][m - 1]);
	printf("%d\n", ans);

	return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:97:9: warning: unused variable 'd' [-Wunused-variable]
   97 |     int d = b[v + 1] - b[v], c = 0;
      |         ^
boat.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
boat.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |   scanf("%d%d", &l[i], &r[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
boat.cpp:86:20: warning: iteration 1009 invokes undefined behavior [-Waggressive-loop-optimizations]
   86 |   int len = b[i + 1] - b[i];
      |             ~~~~~~~^
boat.cpp:84:20: note: within this loop
   84 |  for (int i = 0; i < 2 * N; i++) {
      |                  ~~^~~~~~~

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 4180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 4180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 4180 KB Output isn't correct
2 Halted 0 ms 0 KB -