Submission #343643

#	Time	Username	Problem	Language	Result	Execution time	Memory
343643		parsabahrami	Boat (APIO16_boat)	C++17	100 / 100	539 ms	2560 KiB

boat

#include <bits/stdc++.h>
 
using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;
 
#define SZ(x)                       (int) x.size()
#define F                           first
#define S                           second

int Pow(int a, int b, int md, int res = 1) {
    for (; b; b >>= 1, a = 1ll * a * a % md) {
        if (b & 1) res = 1ll * a * res % md;
    }
    return res;
}

const int N = 1e3 + 10, MOD = 1e9 + 7;
int dp[N][N], I[N], L[N], R[N], n;
vector<int> comp = {0, MOD};

int add(int x, int y) {
    int res = x + y;
    if (res >= MOD) res -= MOD;
    return res;
}

int main() {
    for (int i = 1; i < N; i++) I[i] = Pow(i, MOD - 2, MOD);
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &L[i], &R[i]);
        R[i]++;
        comp.push_back(L[i]);
        comp.push_back(R[i]);
    }
    sort(comp.begin(), comp.end());
    comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
    int m = SZ(comp);
    for (int i = 1; i < m; i++) dp[0][i] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < m; j++) {
            dp[i][j] = dp[i][j - 1];
            if (L[i] > comp[j - 1] || R[i] < comp[j]) continue;
            int len = comp[j] - comp[j - 1];
            int C = 1ll * len * (len - 1) % MOD * ((MOD + 1) / 2) % MOD, k = 1;
            dp[i][j] = add(dp[i][j], 1ll * dp[i - 1][j - 1] * len % MOD);
            for (int last = i - 1; last >= 1; last--) {
                if (L[last] > comp[j - 1] || R[last] < comp[j]) continue;
                dp[i][j] = add(dp[i][j], 1ll * dp[last - 1][j - 1] * C % MOD);
                C = (1ll * (len + k) * C % MOD * I[k + 2] % MOD) % MOD;
                k++;
            }
        }
        for (int j = 1; j < m; j++) dp[i][j] = add(dp[i][j], dp[i - 1][j]);
    }
    printf("%d\n", dp[n][m - 1] - 1);
    return 0;
}

Compilation message (stderr)

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

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