Submission #52972

#	Time	Username	Problem	Language	Result	Execution time	Memory
52972		evpipis	Boat (APIO16_boat)	C++11	58 / 100	2047 ms	10496 KiB

boat

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

#define pb push_back
const int len = 502, mod = 1e9+7;
int n, m = 0;
int po[2*len], dp[2][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 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 j = 0; j <= m+1; j++)
        dp[0][j][0][0] = 1;

    for (int i = 1; i <= n; i++){
        dp[i&1][0][0][0] = 1;

        for (int j = 1; j <= m+1; j++){
            int ans = 0;
            for (int x = 0; x <= i; x++){
                ans = add(ans, mul(dp[i&1][j-1][x][0], bi[j-1][x]));
                ans = add(ans, mul(dp[i&1][j-1][x][1], bi[j-1][x-1]));
            }
            dp[i&1][j][0][0] = ans;

            for (int k = 1; k <= i; k++){
                for (int t = 0; t < 2; t++){
                    ans = dp[(i-1)&1][j][k][t];
                    if (t == 0 && l[i] <= po[j-1]+1 && po[j]-1 <= r[i])
                        ans = add(ans, dp[(i-1)&1][j][k-1][0]);
                    if (t == 1 && l[i] <= po[j] && po[j] <= r[i])
                        ans = add(ans, dp[(i-1)&1][j][k-1][0]);

                    dp[i&1][j][k][t] = ans;
                }
            }
        }
    }

    printf("%d\n", add(dp[n&1][m+1][0][0], mod-1));
    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:32:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < vec.size(); i++)
                     ~~^~~~~~~~~~~~
boat.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
boat.cpp:27: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: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 0 / 42