Submission #962739

#	Time	Username	Problem	Language	Result	Execution time	Memory
962739		SuPythony	Boat (APIO16_boat)	C++17	0 / 100	2 ms	348 KiB

boat

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    const int MOD=1e9+7;
    int n; cin>>n;
    vector<ll> a(n+1), b(n+1);
    for (int i=1; i<=n; i++) {
        cin>>a[i]>>b[i];
    }
    vector<vector<ll>> dp(n+1, vector<ll>(2,0));
    dp[1][1]=1;
    dp[1][0]=1;
    for (int i=2; i<=n; i++) {
        for (int j=1; j<i; j++) {
            dp[i][0]=(dp[i][0]+dp[j][0]+dp[j][1])%MOD;
            dp[i][1]=(dp[i][1]+dp[j][0])%MOD;
            if (a[i]>a[j]) {
                dp[i][1]=(dp[i][1]+dp[j][1])%MOD;
            }
        }
    }
    cout<<(dp[n][1]+dp[n][0])%MOD;
}

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