oj.uz

Submission #742023

# Submission time Handle Problem Language Result Execution time Memory
742023 2023-05-15T11:46:15 Z vjudge1 Boat (APIO16_boat) C++17
0 / 100
 1308 ms 11396 KB 
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <bitset>
#include <cmath>
#include <queue>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define ent "\n"

const int maxn = 5e2 + 100;
const ll INF = (1ll<<61);
const int MOD = 1e9 + 7;
const int inf = (1<<30);
const int maxl = 20;
const int P = 31;

int n;
int a[maxn];
int b[maxn];
ll dp[550][1010];
int cal[maxn];
ll f[maxn * 2][maxn];
ll br[maxn];
ll cnk[maxn][maxn];
vector<int> v;

ll binpow(ll a, ll b){
    if(!b) return 1;
    ll num = binpow(a, b >> 1);
    num = num * num % MOD;
    if(b & 1) num = num * a % MOD;
    return num;
}

int c(int n, int k){
    if(k > n) return 0;
    ll ans = 1;
    for(int i = n - k + 1; i <= n; i++){
        ans = (ans * i) % MOD;
    }
    for(int i = 1; i <= k; i++){
        ans = (ans * br[i]) % MOD;
    }
    return ans;
}

bool ok(int i, int j){
    return v[j] >= a[i] && v[j+1] - 1 <= b[i];
}

void test(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i] >> b[i];
        v.push_back(a[i]);
        v.push_back(b[i] + 1);
        br[i] = binpow(i, MOD - 2);
    }
    v.push_back(1e9 + 1);
    sort(v.begin(), v.end());
    v.resize(unique(v.begin(), v.end()) - v.begin());
    int ans = 0;
    cnk[0][0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= i; j++){
            cnk[i][j] = cnk[i-1][j];
            if(j) cnk[i][j] = (cnk[i][j] + cnk[i-1][j-1]) % MOD;
        }
    }
    for(int i = 0; i < v.size() - 1; i++){
        for(int j = 0; j <= n; j++){
            f[i][j] = c(v[i+1] - v[i], j);
        }
        for(int j = n - 1; j > 0; j--){
            for(int k = j + 1; k <= n; k++){
                f[i][k] = (f[i][k] + 1ll * cnk[k-1][j-1] * f[i][j]) % MOD;
            }
        }
    }
    for(int i = 1; i <= n; i++){
        for(int k = i - 1; k > 0; k--){
            for(int j = 0; j < v.size() - 1; j++){
                if(ok(k+1, j)) cal[j]++;
                if(j) dp[i][j] = (dp[i][j] + 1ll * dp[k][j-1] * f[j][cal[j]]) % MOD;
            }
        }
        for(int j = 0; j < v.size() - 1; j++){
            dp[i][j] += f[j][cal[j]];
            if(!ok(i, j)) dp[i][j] = 0;
            ans = (ans + dp[i][j]) % MOD;
            if(j) dp[i][j] = (dp[i][j] + dp[i][j-1]) % MOD;
        }
    }
    cout << ans << ent;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t; t = 1;
    while(t--) test();
}

Compilation message

boat.cpp: In function 'void test()':
boat.cpp:76:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int i = 0; i < v.size() - 1; i++){
      |                    ~~^~~~~~~~~~~~~~
boat.cpp:88:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |             for(int j = 0; j < v.size() - 1; j++){
      |                            ~~^~~~~~~~~~~~~~
boat.cpp:93:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |         for(int j = 0; j < v.size() - 1; j++){
      |                        ~~^~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1285 ms 11204 KB Output is correct
2 Correct 1304 ms 11244 KB Output is correct
3 Correct 1240 ms 11360 KB Output is correct
4 Correct 1214 ms 11236 KB Output is correct
5 Correct 1308 ms 11276 KB Output is correct
6 Correct 1227 ms 11252 KB Output is correct
7 Correct 1225 ms 11396 KB Output is correct
8 Correct 1208 ms 11268 KB Output is correct
9 Correct 1248 ms 11316 KB Output is correct
10 Correct 1194 ms 11364 KB Output is correct
11 Correct 1273 ms 11372 KB Output is correct
12 Correct 1204 ms 11340 KB Output is correct
13 Correct 1220 ms 11336 KB Output is correct
14 Correct 1228 ms 11264 KB Output is correct
15 Correct 1295 ms 11244 KB Output is correct
16 Incorrect 215 ms 6104 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1285 ms 11204 KB Output is correct
2 Correct 1304 ms 11244 KB Output is correct
3 Correct 1240 ms 11360 KB Output is correct
4 Correct 1214 ms 11236 KB Output is correct
5 Correct 1308 ms 11276 KB Output is correct
6 Correct 1227 ms 11252 KB Output is correct
7 Correct 1225 ms 11396 KB Output is correct
8 Correct 1208 ms 11268 KB Output is correct
9 Correct 1248 ms 11316 KB Output is correct
10 Correct 1194 ms 11364 KB Output is correct
11 Correct 1273 ms 11372 KB Output is correct
12 Correct 1204 ms 11340 KB Output is correct
13 Correct 1220 ms 11336 KB Output is correct
14 Correct 1228 ms 11264 KB Output is correct
15 Correct 1295 ms 11244 KB Output is correct
16 Incorrect 215 ms 6104 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1285 ms 11204 KB Output is correct
2 Correct 1304 ms 11244 KB Output is correct
3 Correct 1240 ms 11360 KB Output is correct
4 Correct 1214 ms 11236 KB Output is correct
5 Correct 1308 ms 11276 KB Output is correct
6 Correct 1227 ms 11252 KB Output is correct
7 Correct 1225 ms 11396 KB Output is correct
8 Correct 1208 ms 11268 KB Output is correct
9 Correct 1248 ms 11316 KB Output is correct
10 Correct 1194 ms 11364 KB Output is correct
11 Correct 1273 ms 11372 KB Output is correct
12 Correct 1204 ms 11340 KB Output is correct
13 Correct 1220 ms 11336 KB Output is correct
14 Correct 1228 ms 11264 KB Output is correct
15 Correct 1295 ms 11244 KB Output is correct
16 Incorrect 215 ms 6104 KB Output isn't correct
17 Halted 0 ms 0 KB -