Submission #735351

#	Time	Username	Problem	Language	Result	Execution time	Memory
735351		bin9638	Boat (APIO16_boat)	C++17	31 / 100	1299 ms	524288 KiB

boat

#include <bits/stdc++.h>

using namespace std;

#define N 510
#define ll long long
#define fs first
#define sc second
#define ii pair<ll,int>
#define pb push_back
#define int ll

const ll mod=1e9+7;

void selfadd(int&u,int v)
{
    u+=v;
    if(u>=mod)u-=mod;
   // u=(u+v)%mod;
}

int n,l[N],r[N];
vector<int>dp[N];

int32_t main()
{
    #ifdef SKY
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    #endif // SKY
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>l[i]>>r[i];
        dp[i].resize(r[i]-l[i]+1,0);
    }
    for(int i=1;i<=n;i++)
        for(int j=l[i];j<=r[i];j++)
        {
            dp[i][j-l[i]]=1;
            if(j>l[i])
                dp[i][j-l[i]]=dp[i][j-l[i]-1]+1;
       //     cout<<i<<" "<<j<<" "<<dp[i][j-l[i]]<<endl;
            for(int k=1;k<i;k++)
            {
                if(j>r[k])
                {
                    selfadd(dp[i][j-l[i]],dp[k].back());
                    continue;
                }
                if(j<=l[k])
                    continue;
                selfadd(dp[i][j-l[i]],dp[k][j-l[k]-1]);
            }
           // cout<<i<<" "<<j<<" "<<dp[i][j-l[i]]<<endl;
        }
    int res=0;
    for(int i=1;i<=n;i++)
        selfadd(res,dp[i].back());
    cout<<(res+mod*mod)%mod;
    return 0;
}

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