oj.uz

Submission #742026

# Submission time Handle Problem Language Result Execution time Memory
742026 2023-05-15T11:48:38 Z vjudge1 Boat (APIO16_boat) C++17
0 / 100
 1322 ms 11468 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] = (dp[i][j] + f[j][cal[j]]) % MOD;
            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 1236 ms 11244 KB Output is correct
2 Correct 1222 ms 11288 KB Output is correct
3 Correct 1273 ms 11468 KB Output is correct
4 Correct 1219 ms 11256 KB Output is correct
5 Correct 1219 ms 11308 KB Output is correct
6 Correct 1322 ms 11292 KB Output is correct
7 Correct 1192 ms 11200 KB Output is correct
8 Correct 1211 ms 11380 KB Output is correct
9 Correct 1244 ms 11292 KB Output is correct
10 Correct 1285 ms 11268 KB Output is correct
11 Correct 1299 ms 11404 KB Output is correct
12 Correct 1278 ms 11304 KB Output is correct
13 Correct 1247 ms 11252 KB Output is correct
14 Correct 1257 ms 11436 KB Output is correct
15 Correct 1222 ms 11284 KB Output is correct
16 Incorrect 220 ms 6164 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1236 ms 11244 KB Output is correct
2 Correct 1222 ms 11288 KB Output is correct
3 Correct 1273 ms 11468 KB Output is correct
4 Correct 1219 ms 11256 KB Output is correct
5 Correct 1219 ms 11308 KB Output is correct
6 Correct 1322 ms 11292 KB Output is correct
7 Correct 1192 ms 11200 KB Output is correct
8 Correct 1211 ms 11380 KB Output is correct
9 Correct 1244 ms 11292 KB Output is correct
10 Correct 1285 ms 11268 KB Output is correct
11 Correct 1299 ms 11404 KB Output is correct
12 Correct 1278 ms 11304 KB Output is correct
13 Correct 1247 ms 11252 KB Output is correct
14 Correct 1257 ms 11436 KB Output is correct
15 Correct 1222 ms 11284 KB Output is correct
16 Incorrect 220 ms 6164 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1236 ms 11244 KB Output is correct
2 Correct 1222 ms 11288 KB Output is correct
3 Correct 1273 ms 11468 KB Output is correct
4 Correct 1219 ms 11256 KB Output is correct
5 Correct 1219 ms 11308 KB Output is correct
6 Correct 1322 ms 11292 KB Output is correct
7 Correct 1192 ms 11200 KB Output is correct
8 Correct 1211 ms 11380 KB Output is correct
9 Correct 1244 ms 11292 KB Output is correct
10 Correct 1285 ms 11268 KB Output is correct
11 Correct 1299 ms 11404 KB Output is correct
12 Correct 1278 ms 11304 KB Output is correct
13 Correct 1247 ms 11252 KB Output is correct
14 Correct 1257 ms 11436 KB Output is correct
15 Correct 1222 ms 11284 KB Output is correct
16 Incorrect 220 ms 6164 KB Output isn't correct
17 Halted 0 ms 0 KB -