Submission #105090

#	Time	Username	Problem	Language	Result	Execution time	Memory
105090		win11905	Boat (APIO16_boat)	C++11	36 / 100	2044 ms	2080 KiB

boat

#include <bits/stdc++.h>
#define long long long
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define x first
#define y second
using namespace std;

const int N = 1e3+5;
const int M = 1e9+7;

int n;
long dp[N], pf[N][N];
vector<long> vec[N];
vector<pii> que;
vector<int> coor;

int powMod(int a, int b) {
    int val = 1;
    for(; b; b >>= 1) {
        if(b & 1) val = (1ll * val * a) % M;
        a = (1ll * a * a) % M;
    } 
    return val;
}

struct coorh {
    size_t operator()(const pii &z) const {
        return z.x + z.y;
    }
};

unordered_map<pii, int, coorh> Mp;

int f(int i, int x) {
    if(Mp.count(pii(i, x))) return Mp[pii(i, x)];
    int up = 1, down = 1;
    for(int j = x; j < i+x; ++j) up = (1ll * up * j) % M;
    for(int j = 1; j <= i; ++j) down = (1ll * down * j) % M;
    return Mp[pii(i, x)] = (1ll * up * powMod(down, M-2)) % M;
}

int main() {
    scanf("%d", &n);
    dp[0] = 1, coor.emplace_back(0);
    for(int i = 0, a, b; i < n; ++i) {
        scanf("%d %d", &a, &b), b++;
        coor.emplace_back(a), coor.emplace_back(b);
        que.emplace_back(a, b);
    }
    sort(all(coor));
    // for(int i = 1; i < coor.size()-1; ++i) 
    //     for(int j = 1; j <= n; ++j) pf[i][j] = f(j, coor[i+1] - coor[i]);
    for(int i = 0, l, r; i < n; ++i) {
        tie(l, r) = que[i];
        l = lower_bound(all(coor), l) - coor.begin(), r = lower_bound(all(coor), r) - coor.begin();
        for(int z = r-1, sum = 0; z >= l; --z, sum = 0) {
            for(int k = z-1; ~k; --k) sum = (sum + dp[k]) % M;
            vec[z].emplace_back(sum), dp[z] = 0;
            int sz = vec[z].size();
            for(int j = 0; j < sz; ++j) dp[z] = (dp[z] + 1ll * vec[z][j] * f(sz-j, coor[z+1] - coor[z])) % M;
        }
    } 
    int ans = 0;
    for(int i = 1; i < coor.size()-1; ++i) ans = (ans + dp[i]) % M;
    printf("%d\n", ans);
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:65:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < coor.size()-1; ++i) ans = (ans + dp[i]) % M;
                    ~~^~~~~~~~~~~~~~~
boat.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:47:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b), b++;
         ~~~~~~~~~~~~~~~~~~~~~~^~~~~

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