Submission #52967

#	Time	Username	Problem	Language	Result	Execution time	Memory
52967		evpipis	Boat (APIO16_boat)	C++11	27 / 100	2073 ms	17888 KiB

boat

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

#define pb push_back
const int len = 105, mod = 1e9+7;
int n, m = 0;
int po[2*len], dp[len][2*len][len][2], bi[2*len][len], l[len], r[len];
vector<int> vec;

int add(int a, int b){
    return (a+b)%mod;
}

int mul(int a, int b){
    return (a*1LL*b)%mod;
}

int pw(int a, int b){
    if (b == 0) return 1;
    if (b%2 == 0) return pw(mul(a, a), b/2);
    return mul(a, pw(mul(a, a), b/2));
}

int solve(int i, int j, int k, int t){
    if (i == 0 || j == 0) return (k == 0);
    if (dp[i][j][k][t] != -1) return dp[i][j][k][t];

    int ans = 0;
    if (k == 0){
        for (int x = 0; x <= i; x++){
            ans = add(ans, mul(solve(i, j-1, x, 0), bi[j-1][x]));
            ans = add(ans, mul(solve(i, j-1, x, 1), bi[j-1][x-1]));
        }
    }
    else{
        ans = add(ans, solve(i-1, j, k, t));
        if (t == 0 && l[i] <= po[j-1]+1 && po[j]-1 <= r[i])
            ans = add(ans, solve(i-1, j, k-1, 0));
        if (t == 1 && l[i] <= po[j] && po[j] <= r[i])
            ans = add(ans, solve(i-1, j, k-1, 0));
    }

    //printf("(%d, %d, %d, %d) = %d\n", i, j, k, t, ans);
    return dp[i][j][k][t] = ans;
}

int main(){
    scanf("%d", &n);
    for (int i = 1; i <= n; i++){
        scanf("%d %d", &l[i], &r[i]);
        vec.pb(l[i]), vec.pb(r[i]);
    }

    sort(vec.begin(), vec.end());
    for (int i = 0; i < vec.size(); i++)
        if (vec[i] != po[m])
            po[++m] = vec[i];

    //for (int i = 0; i <= m; i++)
      //  printf("i = %d, poi = %d\n", i, po[i]);

    for (int i = 0; i <= m; i++){
        bi[i][0] = 1;
        int s = po[i]-po[i-1] - 1;
        for (int k = 1; k <= min(s, n); k++)
            bi[i][k] = mul(bi[i][k-1], mul(s-k+1, pw(k, mod-2)));
    }

    for (int i = 0; i <= n; i++)
        for (int j = 0; j <= m+1; j++)
            for (int k = 0; k <= i; k++)
                dp[i][j][k][0] = dp[i][j][k][1] = -1;

    printf("%d\n", add(solve(n, m+1, 0, 0), mod-1));
    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:55:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec.size(); i++)
                     ~~^~~~~~~~~~~~
boat.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &l[i], &r[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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