oj.uz

Submission #242884

# Submission time Handle Problem Language Result Execution time Memory
242884 2020-06-29T16:23:36 Z Redhood Boat (APIO16_boat) C++14
0 / 100
 2000 ms 384 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define all(x) (x).begin() , (x).end()
#define rall(x) (x).rbegin() , (x).rend()
#define mkp make_pair
#define pb push_back
#define len(x) (int)(x).size()
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
//#define int long long
const int MOD = (int)1e9 + 7, N = 502 , NN = 1001;
int pw(int a , int b){
    if(b == 0)return 1;
    int ans = pw(a , b >> 1);
    ans = (1ll * ans * ans) % MOD;
    if(b & 1)
        ans = (1ll * ans * a) % MOD;
    return ans;
}
int f[4*N][N] , inv[N] , fact[N];
int C[N][N] , done[4*N][N] , cnt[4*N][N];

void md(int &a){
    if(a >= MOD)a-=MOD;
}

void COMBA(vector<pii>&lines){
    fact[0] = 1;
    for(int i = 1 ; i < N; ++i)
        fact[i] = (1ll * fact[i-1] * i) % MOD;

    inv[N-1] = pw(fact[N-1], MOD-2);

    for(int i = N-2;i>=0;--i)
        inv[i] = (1ll * inv[i+1]*(i+1))%MOD;

    for(int i = 0 ; i < N; ++i){
        C[i][0] = 1;
        for(int j = 1; j <= i ; ++j){
            C[i][j] = C[i-1][j] + C[i-1][j-1];
            md(C[i][j]);
        }
    }
    /// fucking cnt[i][j]

    for(int i = 1; i < len(lines); ++i){
        for(int want = 0 ;want < N; ++want){
            int len = lines[i].se - lines[i].fi + 1;
            if(len < want)
                done[i][want] = 0;
            else{
                ll answer = 1;
                for(int j = len-want + 1; j<= len; ++j){
                    answer = (1ll * answer * j) % MOD;
                }
                answer = (1ll * answer * inv[want]) % MOD;
                done[i][want] = answer;
            }
        }
    }
    for(int i = 0 ; i  < len(lines); ++i){
        for(int j = 1 ; j < N; ++j){
            for(int k = 0 ; k < j; ++k){
                cnt[i][j] += (1ll * C[j-1][k] * done[i][j-k])%MOD;
                md(cnt[i][j]);
            }
        }
    }
}
signed main(){
    ifstream cin("1_01.in");
    ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    int n;cin >> n;
    vector<pii>boats(n);
    for(auto&i:boats)cin>>i.fi>>i.se;
    /// lulz wtf is going on here
    set < int > dots;
    for(auto x : boats)
        dots.insert(x.fi) , dots.insert(x.se);
    vector<pii>lines;
    lines.pb({0 , 0});
    for(auto i : dots)
        lines.pb(mkp(i , i));
    auto it = dots.begin();
    int prev = *it;
    ++it;
    while(it != dots.end()){
        if(prev + 1 <= *it-1)
            lines.pb({prev + 1 , *it-1});
        prev = *it;
        ++it;
    }
    sort(all(lines));

    for(auto &i : boats){
        int l = lower_bound(all(lines) , mkp(i.fi , -1))-lines.begin();
        int r = lower_bound(all(lines) , mkp(i.se + 1 , -1))-lines.begin() - 1;
        i = mkp(l , r);
    }

    COMBA(lines);


    for(int i = 0 ; i < n; ++i)
        f[0][i] = 1;
    for(int i = 1; i < len(lines); ++i){
        for(int j = 0; j < N; ++j)
            f[i][j] = f[i-1][j];
        /// what if we skip anybody
        for(int j = 1; j <= n; ++j){
            int cur = j;
            int bad = 0;
            for(int k = 1; k <= n , cur>0; ++k , --cur){
                if(boats[cur-1].se < i || boats[cur-1].fi > i)
                    {bad++;continue;}
                /// firstly update answer
                f[i][j] += (f[i-1][j-k]*1ll*cnt[i][k - bad])%MOD;
                md(f[i][j]);
            }
        }
//        cout << " I " << i << '\n';
//        for(int j = 0 ; j <= n; ++j)
//            cout << f[i][j] << ' ' ;
//        cout << '\n';
    }




    cout << f[len(lines)-1][n];
    return 0;
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:117:30: warning: left operand of comma operator has no effect [-Wunused-value]
             for(int k = 1; k <= n , cur>0; ++k , --cur){
                            ~~^~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2074 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2074 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2080 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2074 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -