Submission #91272

#	Time	Username	Problem	Language	Result	Execution time	Memory
91272		RezwanArefin01	Boat (APIO16_boat)	C++17	100 / 100	661 ms	3352 KiB

boat

///usr/bin/g++ -O2 $0 -o ${0%.cpp} && echo "----------" && ./${0%.cpp}; exit;
#include <bits/stdc++.h>
using namespace std;

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

const int N = 1024; 
const int mod = 1e9 + 7;

int n, a[N], b[N], dp[N][N], inv[N], len[N]; 
vector<int> v; 

void add(int &a, int b) { if((a += b) >= mod) a -= mod; } 

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d %d", &a[i], &b[i]); 
        v.push_back(a[i]); 
        v.push_back(++b[i]); 
    } 

    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end()); 
 
    for(int i = 1; i <= n; i++) {
        a[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1; 
        b[i] = lower_bound(v.begin(), v.end(), b[i]) - v.begin() + 1; 
    }
    
    inv[1] = 1;
    for(int i = 2; i <= n; i++) 
        inv[i] = (ll) (mod - mod / i) * inv[mod % i] % mod; 

    int m = v.size() - 1; 
    for(int i = 1; i <= m; i++) len[i] = v[i] - v[i - 1];
    for(int i = 0; i <= m; i++) dp[0][i] = 1; 
    for(int i = 1; i <= n; i++) {  
        for(int j = a[i]; j < b[i]; j++) {
            int prod = len[j], cnt = 1; 
            for(int k = i - 1; k >= 0; k--) {
                add(dp[i][j], (ll) dp[k][j - 1] * prod % mod); 
                if(a[k] <= j && j < b[k]) {
                    ++cnt; 
                    prod = (ll) prod * (len[j] + cnt - 1) % mod;
                    prod = (ll) prod * inv[cnt] % mod; 
                }
            }
        }
        for(int j = 1; j <= m; j++) add(dp[i][j], dp[i][j - 1]); 
    }
    int ans = 0; 
    for(int i = 1; i <= n; i++) 
        add(ans, dp[i][m]); 
    printf("%d\n", ans);
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:17:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:19:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a[i], &b[i]); 
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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