oj.uz

Submission #500410

# Submission time Handle Problem Language Result Execution time Memory
500410 2021-12-30T22:20:16 Z doowey Boat (APIO16_boat) C++14
0 / 100
 244 ms 9456 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 505;
const int M = N * 4;
const int MOD = (int)1e9 + 7;
int L[N], R[N];

int C[M][N];
int I[N][N];

int fin[M][N];

int powr(int n, int k){
    if(k == 0) return 1;
    int p = powr(n, k / 2);
    p = (p * 1ll * p) % MOD;
    if(k % 2 == 1) p = (p * 1ll * n) % MOD;
    return p;
}

void add(int &a, int b){
    a += b;
    if(a >= MOD) a -= MOD;
    else if(a < 0) a += MOD;
}

int dp[N][M];

int main(){
    fastIO;
    //freopen("in.txt","r",stdin);
    int n;
    cin >> n;
    vector<int> pp;
    for(int i = 1; i <= n; i ++ ){
        cin >> L[i] >> R[i];
        pp.push_back(L[i]);
        pp.push_back(R[i]);
    }
    sort(pp.begin(), pp.end());
    pp.resize(unique(pp.begin(), pp.end()) - pp.begin());
    vector<pii> segm;
    for(int i = 0 ; i < pp.size(); i ++ ){
        segm.push_back(mp(pp[i], pp[i]));
        if(i + 1 < pp.size() && pp[i] + 1 <= pp[i + 1] - 1){
            segm.push_back(mp(pp[i] + 1, pp[i + 1] - 1));
        }
    }
    int m = segm.size();
    for(int i = 1; i < N ;i ++ ){
        I[i][0] = 1;
    }
    for(int k = 1; k < N ; k ++ ){
        for(int i = 1; i < N ; i ++ ){
            add(I[i][k], I[i-1][k-1]);
            add(I[i][k], I[i][k-1]);
        }
    }
    int sz;
    int P, Q;
    int inv;
    int cum;
    for(int i = 0 ; i < m ; i ++ ){
        sz = segm[i].se - segm[i].fi + 1;
        P = Q = 1;
        for(int j = 1; j <= n; j ++ ){
            if(j > sz) break;
            P = (P * 1ll * (sz - j + 1)) % MOD;
            Q = (Q * 1ll * j) % MOD;
            inv = powr(Q, MOD - 2);
            C[i][j] = (P * 1ll * inv) % MOD;
        }
        for(int j = 1; j <= n; j ++ ){
            for(int v = 1; v <= j; v ++ ){
                add(fin[i][j], C[i][v] * 1ll * I[j][v]);
            }
        }
        for(int j = n; j >= 1; j -- ){
            add(fin[i][j], -fin[i][j-1]);
        }
    }
    int tl, tr;
    int mm;
    int side;
    int res = 0;
    for(int i = 1; i <= n; i ++ ){
        for(int j = 0 ; j < m ; j ++ ){
            tl = segm[j].fi;
            tr = segm[j].se;
            if(L[i] <= tl && tr <= R[i]){
                mm = 0;
                for(int v = i; v >= 1; v -- ){

                    if(L[v] <= tl && tr <= R[v]) mm ++ ;
                    side = 0;
                    if(j > 0) add(side, dp[v - 1][j - 1]);
                    if(v == 1) add(side, 1);
                    add(dp[i][j], (side * 1ll * fin[j][mm]) % MOD);
                }
            }
            add(res, dp[i][j]);
            if(j)
                add(dp[i][j], dp[i][j-1]);
        }
    }

    cout << res << "\n";
    return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |     for(int i = 0 ; i < pp.size(); i ++ ){
      |                     ~~^~~~~~~~~~~
boat.cpp:55:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |         if(i + 1 < pp.size() && pp[i] + 1 <= pp[i + 1] - 1){
      |            ~~~~~~^~~~~~~~~~~
boat.cpp:72:9: warning: unused variable 'cum' [-Wunused-variable]
   72 |     int cum;
      |         ^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 9320 KB Output is correct
2 Correct 226 ms 9160 KB Output is correct
3 Correct 231 ms 9284 KB Output is correct
4 Correct 230 ms 9236 KB Output is correct
5 Correct 227 ms 9156 KB Output is correct
6 Correct 232 ms 9456 KB Output is correct
7 Correct 233 ms 9156 KB Output is correct
8 Correct 233 ms 9128 KB Output is correct
9 Correct 242 ms 9368 KB Output is correct
10 Correct 225 ms 9140 KB Output is correct
11 Correct 227 ms 9156 KB Output is correct
12 Correct 229 ms 9244 KB Output is correct
13 Correct 226 ms 9156 KB Output is correct
14 Correct 226 ms 9192 KB Output is correct
15 Correct 244 ms 9268 KB Output is correct
16 Incorrect 43 ms 4292 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 9320 KB Output is correct
2 Correct 226 ms 9160 KB Output is correct
3 Correct 231 ms 9284 KB Output is correct
4 Correct 230 ms 9236 KB Output is correct
5 Correct 227 ms 9156 KB Output is correct
6 Correct 232 ms 9456 KB Output is correct
7 Correct 233 ms 9156 KB Output is correct
8 Correct 233 ms 9128 KB Output is correct
9 Correct 242 ms 9368 KB Output is correct
10 Correct 225 ms 9140 KB Output is correct
11 Correct 227 ms 9156 KB Output is correct
12 Correct 229 ms 9244 KB Output is correct
13 Correct 226 ms 9156 KB Output is correct
14 Correct 226 ms 9192 KB Output is correct
15 Correct 244 ms 9268 KB Output is correct
16 Incorrect 43 ms 4292 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 3388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 9320 KB Output is correct
2 Correct 226 ms 9160 KB Output is correct
3 Correct 231 ms 9284 KB Output is correct
4 Correct 230 ms 9236 KB Output is correct
5 Correct 227 ms 9156 KB Output is correct
6 Correct 232 ms 9456 KB Output is correct
7 Correct 233 ms 9156 KB Output is correct
8 Correct 233 ms 9128 KB Output is correct
9 Correct 242 ms 9368 KB Output is correct
10 Correct 225 ms 9140 KB Output is correct
11 Correct 227 ms 9156 KB Output is correct
12 Correct 229 ms 9244 KB Output is correct
13 Correct 226 ms 9156 KB Output is correct
14 Correct 226 ms 9192 KB Output is correct
15 Correct 244 ms 9268 KB Output is correct
16 Incorrect 43 ms 4292 KB Output isn't correct
17 Halted 0 ms 0 KB -