Submission #1243563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243563		nvc2k8	Boat (APIO16_boat)	C++20	9 / 100	164 ms	7412 KiB

boat

#include <bits/stdc++.h>
#define TASK "askdjkasd"
#define endl '\n'
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define BIT(i,x) (((i)>>(x))&1)
#define FOR(i,a,b) for(int i = (a); i<=(b); i++)
#define FORD(i,a,b) for(int i = (a); i>=(b); i--)
#define all(C) C.begin(), C.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int INT_LIM = 2147483647;
const ll LL_LIM = 9223372036854775807;
template <typename X> bool minimize(X &x, const X &y) {if (x>y){x = y; return true;}return false;}
template <typename X> bool maximize(X &x, const X &y) {if (x<y){x = y; return true;}return false;}
///------------------------------------------///
const int MOD = 1e9+7;
int pw(int x, int p)
{
    int ret = 1;
    while (p)
    {
        if (p&1) ret = 1LL*ret*x%MOD;
        x = 1LL*x*x%MOD; p>>=1;
    }
    return ret;
}
void add(int &x, const int &y)
{
    x+=y;
    if (x>=MOD) x-=MOD;
}

int inv[505];
int n, m = 0;
int a[505], b[505];
int c[1005];
int f[1005][505];
int nCk[1005][505];
int nCk2[505][505];

void inp()
{
    cin >> n;
    inv[0] = 1;
    FOR(i, 1, n) inv[i] = 1LL*inv[i-1]*i%MOD;
    inv[n] = pw(inv[n], MOD-2);
    FORD(i, n, 1) inv[i-1] = 1LL*inv[i]*i%MOD;

    set<int> tmp;

    FOR(i, 1, n)
    {
        cin >> a[i] >> b[i];
        tmp.insert(a[i]-1);
        tmp.insert(b[i]);
    }

    for (auto i:tmp)
    {
        c[++m] = i;
    }

    FOR(i, 1, m)
    {
        nCk[i][0] = 1;
        FOR(j, 1, n)
        {
            if (c[i]-c[i-1]-j+1==0) break;
            nCk[i][j] = 1LL*nCk[i][j-1]*(c[i]-c[i-1]-j+1)%MOD;
        }
//        if (i==1) cout << inv[1] << endl;
        FOR(j, 1, n)
        {
            if (c[i]-c[i-1]-j+1==0) break;
            nCk[i][j] = 1LL*nCk[i][j]*inv[j]%MOD;
        }
    }

    FOR(i, 0, n) FOR(j, 0, i)
    {
        if (j==0 || j==i) nCk2[i][j] = 1;
        else nCk2[i][j] = (nCk2[i-1][j-1]+nCk2[i-1][j])%MOD;
    }
}

int calc(int m, int k)
{
    if (f[m][k]!=0) return f[m][k];
    FOR(i, 0, k) add(f[m][k], 1LL*nCk2[k][i]*nCk[m][i+1]);

    return f[m][k];
}

int dp[505][1005];

void solve()
{
    FOR(i, 0, m) dp[0][i] = 1;

    int ans = 0;
    FOR(i, 1, n) FOR(j, 1, m)
    {
        if (a[i]<=c[j-1]+1 && c[j]<=b[i])
        {
//            dp[i][j] = c[j]-c[j-1];
            int cnt = 0;
            FORD(t, i-1, 0)
            {
                add(dp[i][j], 1LL*dp[t][j-1]*calc(j, cnt)%MOD);
//                cout << i << ' ' << j << ' ' << t << ' ' << 1LL*dp[t][j-1]*calc(j, cnt)%MOD << endl;
                if (a[t]<=c[j-1]+1 && c[j]<=b[t]) cnt++;
            }
//            cout << i << ' ' << j << ' ' << dp[i][j] << endl;
        }
        add(ans, dp[i][j]);
//        cout << i << ' ' << j << ' ' << dp[i][j] << endl;
        add(dp[i][j], dp[i][j-1]);
    }
    cout << ans;
}

signed main()
{
    ///--------------------------///
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    if (fopen(TASK".INP","r")!=NULL)
    {
        freopen(TASK".INP","r",stdin);
        freopen(TASK".OUT","w",stdout);
    }
    ///--------------------------///

    int NTEST = 1;
    bool codeforces = 0;
    if (codeforces) cin >> NTEST;

    while (NTEST--)
    {
        inp();
        solve();
    }

    return 0;
}

///------------------------------------------///

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:132:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         freopen(TASK".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
boat.cpp:133:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         freopen(TASK".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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