Submission #1312585

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312585		yus1f_m	Boat (APIO16_boat)	C++20	0 / 100	2112 ms	506772 KiB

boat

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define str string
#define pb push_back
#define pf push_front
#define in insert
#define all(v) v.begin(),v.end()
const int sz=1000000,INF=1000000000,MOD=1000000007;
using namespace std;
void solve()
{
    ll n,num1,num2,ans=0;
    cin>>n;
    vector<pair<ll,ll>>nums;
    vector<map<ll,ll>>dp(n+1);
    for(int i=0;i<n;i++)
    {
        cin>>num1>>num2;
        nums.pb({num1,num2});
    }
    dp[1][0]=1;
    for(int i=nums[0].first;i<=nums[0].second;i++)
    {
        dp[1][i]=1;
    }
    for(int i=2;i<=n;i++)
    {
        for(auto Dp:dp[i-1])
        {
            dp[i][0]=(dp[i][0]+Dp.second)%MOD;
        }
        for(auto Dp:dp[i-1])
        {
            for(int j=nums[i-1].first;j<=nums[i-1].second;j++)
            {
                if(Dp.first<j)
                {
                    dp[i][j]=(dp[i][j]+Dp.second)%MOD;
                }
            }
        }
    }
    for(auto Dp:dp[n])
    {
        ans=(ans+Dp.second)%MOD;
    }
    cout<<(ans-1+MOD)%MOD;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    ll t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
}

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