Submission #204386

#	Time	Username	Problem	Language	Result	Execution time	Memory
204386		aloo123	Boat (APIO16_boat)	C++14	100 / 100	770 ms	8440 KiB

boat

#include<bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
 
#define pb push_back
#define mp make_pair
 
#define all(x) (x).begin(), (x).end()
 
#define fi first
#define se second
 
using namespace std;
//using namespace __gnu_pbds;
 
typedef long long ll;   
typedef pair<int, int> pii;
//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
const int MAXN = (int)1e3 + 5;
const int MOD = (int)1e9 + 7;
 
int fact[MAXN], rev[MAXN];
 
int dp[2][MAXN][MAXN];
 
vector<int> T;
 
pii arr[MAXN];
 
int n;
 
void addMod(int &a, int b, int m = MOD) {
    a += b;
 
    if (m <= a) {
        a -= m;
    }
}
 
void mulMod(int &a, int b, int m = MOD) {
    a = (a * 1ll * b) % m;
}
 
int binPow(int a, int b) {
    int ret = 1;
 
    while (b > 0) {
        if (b & 1) {
            mulMod(ret, a);
        }
 
        mulMod(a, a);
        b >>= 1;
    }
 
    return ret;
}
 
void solve() {
    scanf("%d", &n);
 
    for (int i = 1; i <= n; ++i) {
        scanf("%d %d", &arr[i].fi, &arr[i].se);
        T.pb(arr[i].fi);
        T.pb(arr[i].se + 1);
    }
 
    T.pb(0);
    sort(all(T));
    T.resize(unique(all(T)) - T.begin());
 
    for (int i = 1; i <= n; ++i) {
        arr[i].fi = lower_bound(all(T), arr[i].fi) - T.begin();
        arr[i].se = lower_bound(all(T), arr[i].se + 1) - T.begin();
    }           
 
    fact[0] = rev[0] = 1;
 
    for (int i = 1; i < MAXN; ++i) {
        fact[i] = fact[i - 1];
        mulMod(fact[i], i);
        rev[i] = binPow(fact[i], MOD - 2);
    } 
 
    dp[0][0][0] = 1;
 
    for (int i = 1; i <= n; ++i) {
        int p = 0, w = 0;
 
        for (int c = arr[i].fi; c < arr[i].se; ++c) {
            int lim = T[c + 1] - T[c];
 
            for (int cnt = 1; cnt <= i; ++cnt) {
                int tmp = dp[0][c][cnt - 1];
                mulMod(tmp, max(0, lim - cnt + 1));
                addMod(dp[1][c][cnt], tmp);                                                                
            }
 
            while (p < c) {
                for (int cnt = 0; cnt <= i; ++cnt) {
                    int tmp = dp[0][p][cnt];
                    mulMod(tmp, rev[cnt]);
                    addMod(w, tmp);
                }
 
                ++p;
            }
 
            int tmp = w;
            mulMod(tmp, lim);
            addMod(dp[1][c][1], tmp);
        }
 
        for (int c = 0; c < T.size(); ++c) {
            for (int cnt = 0; cnt <= i; ++cnt) {
                addMod(dp[0][c][cnt], dp[1][c][cnt]);
                dp[1][c][cnt] = 0;
            }
        }
    }
 
    int ans = 0;
 
    for (int c = 1; c + 1 < T.size(); ++c) {
        for (int cnt = 1; cnt <= n; ++cnt) {
            int tmp = dp[0][c][cnt];
            mulMod(tmp, rev[cnt]);
            addMod(ans, tmp);            
        }
    }        
 
    printf("%d\n", ans);
}
 
int main() {
    int tt = 1;
 
    while (tt--) {
        solve();
    }
 
    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'void solve()':
boat.cpp:115:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int c = 0; c < T.size(); ++c) {
                         ~~^~~~~~~~~~
boat.cpp:125:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int c = 1; c + 1 < T.size(); ++c) {
                     ~~~~~~^~~~~~~~~~
boat.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &arr[i].fi, &arr[i].se);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42