oj.uz

Submission #266354

# Submission time Handle Problem Language Result Execution time Memory
266354 2020-08-15T08:14:49 Z abacaba Boat (APIO16_boat) C++14
0 / 100
 361 ms 1528 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 - 1) + 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 256 ms 1404 KB Output is correct
2 Correct 259 ms 1316 KB Output is correct
3 Correct 241 ms 1488 KB Output is correct
4 Correct 213 ms 1400 KB Output is correct
5 Correct 235 ms 1400 KB Output is correct
6 Correct 338 ms 1400 KB Output is correct
7 Correct 343 ms 1464 KB Output is correct
8 Correct 333 ms 1380 KB Output is correct
9 Correct 342 ms 1528 KB Output is correct
10 Correct 339 ms 1400 KB Output is correct
11 Correct 337 ms 1400 KB Output is correct
12 Correct 335 ms 1400 KB Output is correct
13 Correct 337 ms 1400 KB Output is correct
14 Correct 343 ms 1400 KB Output is correct
15 Correct 361 ms 1432 KB Output is correct
16 Incorrect 218 ms 1400 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 1404 KB Output is correct
2 Correct 259 ms 1316 KB Output is correct
3 Correct 241 ms 1488 KB Output is correct
4 Correct 213 ms 1400 KB Output is correct
5 Correct 235 ms 1400 KB Output is correct
6 Correct 338 ms 1400 KB Output is correct
7 Correct 343 ms 1464 KB Output is correct
8 Correct 333 ms 1380 KB Output is correct
9 Correct 342 ms 1528 KB Output is correct
10 Correct 339 ms 1400 KB Output is correct
11 Correct 337 ms 1400 KB Output is correct
12 Correct 335 ms 1400 KB Output is correct
13 Correct 337 ms 1400 KB Output is correct
14 Correct 343 ms 1400 KB Output is correct
15 Correct 361 ms 1432 KB Output is correct
16 Incorrect 218 ms 1400 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 1404 KB Output is correct
2 Correct 259 ms 1316 KB Output is correct
3 Correct 241 ms 1488 KB Output is correct
4 Correct 213 ms 1400 KB Output is correct
5 Correct 235 ms 1400 KB Output is correct
6 Correct 338 ms 1400 KB Output is correct
7 Correct 343 ms 1464 KB Output is correct
8 Correct 333 ms 1380 KB Output is correct
9 Correct 342 ms 1528 KB Output is correct
10 Correct 339 ms 1400 KB Output is correct
11 Correct 337 ms 1400 KB Output is correct
12 Correct 335 ms 1400 KB Output is correct
13 Correct 337 ms 1400 KB Output is correct
14 Correct 343 ms 1400 KB Output is correct
15 Correct 361 ms 1432 KB Output is correct
16 Incorrect 218 ms 1400 KB Output isn't correct
17 Halted 0 ms 0 KB -