oj.uz

Submission #105097

# Submission time Handle Problem Language Result Execution time Memory
105097 2019-04-10T14:24:27 Z win11905 Boat (APIO16_boat) C++11
0 / 100
 3 ms 512 KB 
#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;
int dp[N], pf[N][N];
vector<int> coor, vec[N];
vector<pii> que;
 
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;
}
 
int f(int i, int 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 (1ll * up * powMod(down, M-2)) % M;
}

int pref[N];
 
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++;
        pref[a]++, pref[b]--;
        coor.emplace_back(a), coor.emplace_back(b);
        que.emplace_back(a, b);
    }
    sort(all(coor));
    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();
        pref[l]++, pref[r]--;
    }
    for(int i = 1; i < coor.size()-1; ++i) {
        pref[i] += pref[i-1];
        for(int j = 1; j <= pref[i]; ++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] * pf[z][sz-j]) % M;
        }
    } 
    int ans = 0;
    for(int i = 1; i < coor.size()-1; ++i) ans = (ans + dp[i]) % M;
    printf("%d\n", ans);
}

Compilation message

boat.cpp: In function 'int main()':
boat.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 1; i < coor.size()-1; ++i) {
                    ~~^~~~~~~~~~~~~~~
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:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:39: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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -