oj.uz

Submission #742038

# Submission time Handle Problem Language Result Execution time Memory
742038 2023-05-15T12:22:17 Z vjudge1 Boat (APIO16_boat) C++17
0 / 100
 1745 ms 12248 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[maxn][maxn * 2];
int cal[maxn];
ll f[maxn * 2][maxn];
ll br[maxn];
ll cnk[maxn][maxn];
vector<int> v;
ll fc[maxn];

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++){
            fc[j] = c(v[i+1] - v[i], j);
        }
        for(int j = n; j >= 0; j--){
            for(int k = j; k <= n; k++){
                f[i][k] = (f[i][k] + 1ll * cnk[k-1][j-1] * fc[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++){
            if(ok(1, j)) cal[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:77:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i = 0; i < v.size() - 1; i++){
      |                    ~~^~~~~~~~~~~~~~
boat.cpp:89:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |             for(int j = 0; j < v.size() - 1; j++){
      |                            ~~^~~~~~~~~~~~~~
boat.cpp:94:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for(int j = 0; j < v.size() - 1; j++){
      |                        ~~^~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1277 ms 12044 KB Output is correct
2 Correct 1246 ms 12024 KB Output is correct
3 Correct 1374 ms 12128 KB Output is correct
4 Correct 1287 ms 12024 KB Output is correct
5 Correct 1238 ms 12024 KB Output is correct
6 Correct 1336 ms 12248 KB Output is correct
7 Correct 1437 ms 12096 KB Output is correct
8 Correct 1387 ms 12048 KB Output is correct
9 Correct 1513 ms 12100 KB Output is correct
10 Correct 1251 ms 12076 KB Output is correct
11 Correct 1384 ms 12000 KB Output is correct
12 Correct 1271 ms 12080 KB Output is correct
13 Correct 1349 ms 12084 KB Output is correct
14 Correct 1253 ms 12012 KB Output is correct
15 Correct 1745 ms 11980 KB Output is correct
16 Incorrect 242 ms 6172 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1277 ms 12044 KB Output is correct
2 Correct 1246 ms 12024 KB Output is correct
3 Correct 1374 ms 12128 KB Output is correct
4 Correct 1287 ms 12024 KB Output is correct
5 Correct 1238 ms 12024 KB Output is correct
6 Correct 1336 ms 12248 KB Output is correct
7 Correct 1437 ms 12096 KB Output is correct
8 Correct 1387 ms 12048 KB Output is correct
9 Correct 1513 ms 12100 KB Output is correct
10 Correct 1251 ms 12076 KB Output is correct
11 Correct 1384 ms 12000 KB Output is correct
12 Correct 1271 ms 12080 KB Output is correct
13 Correct 1349 ms 12084 KB Output is correct
14 Correct 1253 ms 12012 KB Output is correct
15 Correct 1745 ms 11980 KB Output is correct
16 Incorrect 242 ms 6172 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 2200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1277 ms 12044 KB Output is correct
2 Correct 1246 ms 12024 KB Output is correct
3 Correct 1374 ms 12128 KB Output is correct
4 Correct 1287 ms 12024 KB Output is correct
5 Correct 1238 ms 12024 KB Output is correct
6 Correct 1336 ms 12248 KB Output is correct
7 Correct 1437 ms 12096 KB Output is correct
8 Correct 1387 ms 12048 KB Output is correct
9 Correct 1513 ms 12100 KB Output is correct
10 Correct 1251 ms 12076 KB Output is correct
11 Correct 1384 ms 12000 KB Output is correct
12 Correct 1271 ms 12080 KB Output is correct
13 Correct 1349 ms 12084 KB Output is correct
14 Correct 1253 ms 12012 KB Output is correct
15 Correct 1745 ms 11980 KB Output is correct
16 Incorrect 242 ms 6172 KB Output isn't correct
17 Halted 0 ms 0 KB -