Submission #282531

#	Time	Username	Problem	Language	Result	Execution time	Memory
282531		AaronNaidu	Boat (APIO16_boat)	C++14	0 / 100	5 ms	2432 KiB

boat

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

ll mod = 1000000007; 
int n;
ll x;
vector<ll> v;
vector<pair<ll, int> > ycoords;
int indexes[501];

ll dp[501][501];

ll getDP(int a, int b) {
    if (a == -1)
    {
        return 1;
    }
    if (dp[a][b] > 0)
    {
        return dp[a][b];
    }
    
    ll ans = 0;
    if (ycoords[b].first >= v[a])
    {
        ans += getDP(a-1, indexes[a]);
        ans %= mod;
    }
    ans += getDP(a-1, b);
    ans %= mod;
    dp[a][b] = ans;
    return ans;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> x >> x;
        v.push_back(x);
        ycoords.push_back({x, i});
    }
    sort(ycoords.begin(), ycoords.end());
    for (int i = 0; i < n; i++)
    {
        indexes[ycoords[i].second] = i;
    }
    ll ans = getDP(n-1, n-1) - 1;
    if (ans < 0)
    {
        ans += mod;
    }
    
    ans %= mod;
    cout << ans << "\n";
}

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