oj.uz

Submission #742020

# Submission time Handle Problem Language Result Execution time Memory
742020 2023-05-15T11:43:10 Z vjudge1 Boat (APIO16_boat) C++17
0 / 100
 1319 ms 6080 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];
int dp[550][1010];
int cal[maxn];
int f[maxn * 2][maxn];
int br[maxn];
int 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 1241 ms 5904 KB Output is correct
2 Correct 1251 ms 5836 KB Output is correct
3 Correct 1282 ms 5840 KB Output is correct
4 Correct 1311 ms 6080 KB Output is correct
5 Correct 1255 ms 5940 KB Output is correct
6 Correct 1282 ms 5840 KB Output is correct
7 Correct 1250 ms 5924 KB Output is correct
8 Correct 1245 ms 5828 KB Output is correct
9 Correct 1291 ms 5908 KB Output is correct
10 Correct 1279 ms 5804 KB Output is correct
11 Correct 1285 ms 5956 KB Output is correct
12 Correct 1319 ms 5856 KB Output is correct
13 Correct 1288 ms 5892 KB Output is correct
14 Correct 1285 ms 5916 KB Output is correct
15 Correct 1236 ms 5784 KB Output is correct
16 Incorrect 220 ms 3884 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1241 ms 5904 KB Output is correct
2 Correct 1251 ms 5836 KB Output is correct
3 Correct 1282 ms 5840 KB Output is correct
4 Correct 1311 ms 6080 KB Output is correct
5 Correct 1255 ms 5940 KB Output is correct
6 Correct 1282 ms 5840 KB Output is correct
7 Correct 1250 ms 5924 KB Output is correct
8 Correct 1245 ms 5828 KB Output is correct
9 Correct 1291 ms 5908 KB Output is correct
10 Correct 1279 ms 5804 KB Output is correct
11 Correct 1285 ms 5956 KB Output is correct
12 Correct 1319 ms 5856 KB Output is correct
13 Correct 1288 ms 5892 KB Output is correct
14 Correct 1285 ms 5916 KB Output is correct
15 Correct 1236 ms 5784 KB Output is correct
16 Incorrect 220 ms 3884 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1241 ms 5904 KB Output is correct
2 Correct 1251 ms 5836 KB Output is correct
3 Correct 1282 ms 5840 KB Output is correct
4 Correct 1311 ms 6080 KB Output is correct
5 Correct 1255 ms 5940 KB Output is correct
6 Correct 1282 ms 5840 KB Output is correct
7 Correct 1250 ms 5924 KB Output is correct
8 Correct 1245 ms 5828 KB Output is correct
9 Correct 1291 ms 5908 KB Output is correct
10 Correct 1279 ms 5804 KB Output is correct
11 Correct 1285 ms 5956 KB Output is correct
12 Correct 1319 ms 5856 KB Output is correct
13 Correct 1288 ms 5892 KB Output is correct
14 Correct 1285 ms 5916 KB Output is correct
15 Correct 1236 ms 5784 KB Output is correct
16 Incorrect 220 ms 3884 KB Output isn't correct
17 Halted 0 ms 0 KB -