Submission #124068

#	Time	Username	Problem	Language	Result	Execution time	Memory
124068		Mtaylor	Boat (APIO16_boat)	C++17	9 / 100	2066 ms	16732 KiB

boat

#include <bits/stdc++.h>
 
    using namespace std;
    typedef long long ll;
    typedef vector<ll> vl ;
 
    #define mp make_pair
    #define pb push_back
    #define f first
    #define s second
    #define all(v) (v).begin(),(v).end()
 
 
    const int MOD = 1000000007;
    const int N = 1000005;
    const double PI =4*atan(1);
    const double eps = 1e-7;
 
    map<ll,ll> maa;
    map<ll,ll> mal;
    ll n;
    set<ll> ss;
    ll c[N];
    ll d[N];
    ll b[N];
    ll a[N];
    ll dp[505][4005];

    ll solve(ll pos , ll prev){
        if(pos>=n  && prev==0)return 0;
        //cout << pos << " " << prev << endl;
        if(pos>=n)return 1;
        //cout << "trol"<< endl;
        ll to_return =solve(pos+1,prev);
        if(dp[pos][prev]>=0)return dp[pos][prev];
        ll x=max(c[pos],prev);
        //cout << mal[x] << endl;
        ll z=mal[x]-1;
        for(int i=x;i<=d[pos];i++){
        	//cout << pos << " " <<mal[i] << " " << z<< endl;
        	ll y=maa[mal[i]+1];
        	//cout << y<<" " << mal[y]<<endl;
            to_return += ((mal[i]-z)%MOD )* (solve(pos+1, y)%MOD) %MOD ;
            z=mal[i];
            to_return %=MOD;
        }
        return dp[pos][prev]=to_return;
    }
 
 
    int main(){
        ios::sync_with_stdio(0);
        //freopen("easy.txt","r",stdin);
        memset(dp,-1,sizeof(dp));
        cin >> n;
        for(int i=0;i<n;i++){
            cin >> a[i];
            cin >> b[i];
            ss.insert(a[i]);
            ss.insert(a[i]-1);
            ss.insert(a[i]+1);
            ss.insert(b[i]+1);
            ss.insert(b[i]-1);
            ss.insert(b[i]);
        }
        ll cnt=1;
        maa[0]=0;
        mal[0]=0;
        for(auto t:ss){
            maa[t]=cnt;
            mal[cnt]=t;
            cnt++;
        }
        for(int i=0;i<n;i++){
            c[i]=maa[a[i]];
            d[i]=maa[b[i]];
        }
        ll ans = solve(0,0);
        cout << ans;


        return 0;
    }

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