Submission #730277

#	Time	Username	Problem	Language	Result	Execution time	Memory
730277		abcvuitunggio	Boat (APIO16_boat)	C++17	9 / 100	342 ms	11092 KiB

boat

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1000000007;
int dp[2][1010][501],c[1001][501],n,a[501],b[501],l[1001],r[1001],id,f[501];
vector <pair <int, int>> v;
int pw(int a, int b){
    if (!b)
        return 1;
    int t=pw(a,b>>1);
    t=(t*t)%mod;
    return (b&1?(t*a)%mod:t);
}
int32_t main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n;
    f[0]=1;
    for (int i=1;i<=n;i++){
        cin >> a[i] >> b[i];
        v.push_back({a[i],0});
        v.push_back({b[i],1});
        f[i]=f[i-1]*i%mod;
    }
    for (int i=1;i<=n;i++)
        f[i]=pw(f[i],mod-2);
    sort(v.begin(),v.end());
    for (int i=0;i<v.size()-1;i++){
        if (v[i].second&&!v[i+1].second)
            continue;
        id++;
        l[id]=v[i].first+v[i].second;
        r[id]=v[i+1].first-1+v[i+1].second;
        c[id][0]=1;
        for (int j=1;j<=n;j++)
            c[id][j]=c[id][j-1]*(r[id]-l[id]-j+2)%mod;
        for (int j=2;j<=n;j++)
            c[id][j]=c[id][j]*f[j]%mod;
    }
    for (int i=0;i<2;i++)
        for (int k=0;k<=n;k++)
            dp[i][id+1][k]=1;
    for (int j=1;j<=id;j++)
        for (int k=0;k<=n;k++)
            dp[n&1^1][j][k]=(j>id?1:c[j][k]);
    for (int i=n;i>=1;i--)
        for (int j=id;j;j--)
            for (int k=0;k<=n;k++){
                if (k>r[j]-l[j]+1){
                    dp[i&1][j][k]=0;
                    continue;
                }
                dp[i&1][j][k]=dp[i&1^1][j][k]+(dp[i&1][j+1][0]-dp[i&1^1][j+1][0])*c[j][k]+(a[i]<=l[j]&&r[j]<=b[i])*dp[i&1^1][j][k+1];
                dp[i&1][j][k]%=mod;
            }
    dp[1][1][0]=(dp[1][1][0]-1)%mod;
    cout << (dp[1][1][0]+mod)%mod;
}

Compilation message (stderr)

boat.cpp: In function 'int32_t main()':
boat.cpp:27:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for (int i=0;i<v.size()-1;i++){
      |                  ~^~~~~~~~~~~
boat.cpp:44:17: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   44 |             dp[n&1^1][j][k]=(j>id?1:c[j][k]);
      |                ~^~
boat.cpp:52:35: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   52 |                 dp[i&1][j][k]=dp[i&1^1][j][k]+(dp[i&1][j+1][0]-dp[i&1^1][j+1][0])*c[j][k]+(a[i]<=l[j]&&r[j]<=b[i])*dp[i&1^1][j][k+1];
      |                                  ~^~
boat.cpp:52:68: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   52 |                 dp[i&1][j][k]=dp[i&1^1][j][k]+(dp[i&1][j+1][0]-dp[i&1^1][j+1][0])*c[j][k]+(a[i]<=l[j]&&r[j]<=b[i])*dp[i&1^1][j][k+1];
      |                                                                   ~^~
boat.cpp:52:120: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   52 |                 dp[i&1][j][k]=dp[i&1^1][j][k]+(dp[i&1][j+1][0]-dp[i&1^1][j+1][0])*c[j][k]+(a[i]<=l[j]&&r[j]<=b[i])*dp[i&1^1][j][k+1];
      |                                                                                                                       ~^~

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