Submission #947262

#	Time	Username	Problem	Language	Result	Execution time	Memory
947262		NValchanov	Boat (APIO16_boat)	C++17	9 / 100	1 ms	756 KiB

boat

#include<bits/stdc++.h>

#define endl '\n'
#define a first
#define b second

using namespace std;

typedef long long ll;

const ll MAXN = 512;
const ll MAXA = 1e6 + 10;
const ll MOD = 1e9 + 7;

ll n;
pair<ll,ll> s[MAXN];
ll dp[MAXN];

void read()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> s[i].a >> s[i].b;
    }
    s[0].a = s[0].b = 0;
}

void fill_dp()
{
    dp[0] = 1;
    for(int i = 1; i <= n; i++)
    {
        for(int j = 0; j < i; j++)
        {
            if(s[i].a > s[j].a)
                dp[i] = (dp[i] + dp[j]) % MOD;
        }
    }
}

void solve()
{
    ll ans = 0;
    for(int i = 1; i <= n; i++)
    {
        ans = (ans + dp[i]) % MOD;
    }
    cout << ans << endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

    read();
    fill_dp();
    solve();

	return 0;
}

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