oj.uz

Submission #266353

# Submission time Handle Problem Language Result Execution time Memory
266353 2020-08-15T08:14:13 Z abacaba Boat (APIO16_boat) C++14
0 / 100
 373 ms 1656 KB 
#include <iostream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <chrono>
#include <vector>
#include <map>
#include <random>
#include <set>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <stdio.h>
#include <queue>
#include <bitset>
#include <cstdlib>
#include <deque>
#include <cassert>
#include <stack>
#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
 
// typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define ppb pop_back
#define emb emplace_back
#define ll long long
#define ull unsigned long long
#define cntbit(x) __builtin_popcount(x)
#define endl '\n'
#define uset unordered_set
#define umap unordered_map
#define pii pair<int, int>
#define ld long double
#define pll pair<long long, long long>
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
template <typename T> inline T range(T l, T r) {
    return uniform_int_distribution<T>(l, r)(rng);
}
 
template <typename T> void Min(T &a, T b) {
    a = min(a, b);
}
 
template <typename T> void Max(T &a, T b) {
    a = max(a, b);
}

const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int N = 5e2 + 15;
int n;
pii a[N];

int dp[N][N];

inline int add(int a, int b) {
	a += b;
	if(a >= mod)
		return a - mod;
	if(a < 0)
		return a + mod;
	return a;
}

inline void add_t(int &a, int b) {
	a = add(a, b);
}

inline int mul(int a, int b) {
	return 1LL * a * b % mod;
}

inline void mul_t(int &a, int b) {
	a = mul(a, b);
}

main() {
	ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
//	freopen("input.txt", "r", stdin);
	cin >> n;
	for(int i = 1; i <= n; ++i)
		cin >> a[i].f >> a[i].se;
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j < i; ++j) {
			for(int prob = 0; prob <= n; ++prob) {
				if(a[i].se > a[j].se) {
					int st = max(a[j].se + 1, a[i].f);
					for(; st <= a[i].se; ++st) {
						int new_prob = (st - a[j].se) + prob; // (st - a[j].se - 1) ?
						if(new_prob > n) {
							add_t(dp[i][n], mul(a[i].se - st + 1, dp[j][prob]));
							break;
						}
						add_t(dp[i][new_prob], dp[j][prob]);
					}
				}
				for(int k = min(a[j].se, a[i].se); k >= a[i].f; --k) {
					int new_prob = prob - (a[j].se - k + 1);
					if(new_prob < 0)
						break;
					add_t(dp[i][new_prob], dp[j][prob]);
				}
			}
		}
		for(int j = 0; a[i].f + j <= a[i].se; ++j) {
			if(j >= n) {
				add_t(dp[i][n], a[i].se - (a[i].f + j) + 1);
				break;
			}
			add_t(dp[i][j], 1);
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; ++i)
		for(int j = 0; j <= n; ++j)
			add_t(ans, dp[i][j]);
	cout << ans << endl;
	return 0;
}

Compilation message

boat.cpp:88:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   88 | main() {
      |      ^

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 1400 KB Output is correct
2 Correct 215 ms 1400 KB Output is correct
3 Correct 221 ms 1400 KB Output is correct
4 Correct 208 ms 1436 KB Output is correct
5 Correct 223 ms 1400 KB Output is correct
6 Correct 332 ms 1352 KB Output is correct
7 Correct 351 ms 1308 KB Output is correct
8 Correct 334 ms 1656 KB Output is correct
9 Correct 335 ms 1400 KB Output is correct
10 Correct 324 ms 1400 KB Output is correct
11 Correct 328 ms 1400 KB Output is correct
12 Correct 373 ms 1528 KB Output is correct
13 Correct 358 ms 1348 KB Output is correct
14 Correct 342 ms 1404 KB Output is correct
15 Correct 352 ms 1424 KB Output is correct
16 Incorrect 219 ms 1392 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 1400 KB Output is correct
2 Correct 215 ms 1400 KB Output is correct
3 Correct 221 ms 1400 KB Output is correct
4 Correct 208 ms 1436 KB Output is correct
5 Correct 223 ms 1400 KB Output is correct
6 Correct 332 ms 1352 KB Output is correct
7 Correct 351 ms 1308 KB Output is correct
8 Correct 334 ms 1656 KB Output is correct
9 Correct 335 ms 1400 KB Output is correct
10 Correct 324 ms 1400 KB Output is correct
11 Correct 328 ms 1400 KB Output is correct
12 Correct 373 ms 1528 KB Output is correct
13 Correct 358 ms 1348 KB Output is correct
14 Correct 342 ms 1404 KB Output is correct
15 Correct 352 ms 1424 KB Output is correct
16 Incorrect 219 ms 1392 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 233 ms 1400 KB Output is correct
2 Correct 215 ms 1400 KB Output is correct
3 Correct 221 ms 1400 KB Output is correct
4 Correct 208 ms 1436 KB Output is correct
5 Correct 223 ms 1400 KB Output is correct
6 Correct 332 ms 1352 KB Output is correct
7 Correct 351 ms 1308 KB Output is correct
8 Correct 334 ms 1656 KB Output is correct
9 Correct 335 ms 1400 KB Output is correct
10 Correct 324 ms 1400 KB Output is correct
11 Correct 328 ms 1400 KB Output is correct
12 Correct 373 ms 1528 KB Output is correct
13 Correct 358 ms 1348 KB Output is correct
14 Correct 342 ms 1404 KB Output is correct
15 Correct 352 ms 1424 KB Output is correct
16 Incorrect 219 ms 1392 KB Output isn't correct
17 Halted 0 ms 0 KB -