Submission #1131559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131559		garam1732	Boat (APIO16_boat)	C++20	9 / 100	1 ms	332 KiB

boat

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

#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;

const int MAXN = 550;//100100*5;
const ll MOD = 1e9+7;
const ll INF = 2e18;

vector<ll> v;
pll arr[MAXN];
ll dp[MAXN][MAXN*2], sum[MAXN][MAXN*2]; // dp[i][j] : choose jth interval for ith school
ll comb[MAXN*2][MAXN], fac[MAXN], rfac[MAXN];
ll cnt[MAXN][MAXN*2];

ll e[MAXN];

ll pw(ll a, ll b) {
    if(b==0) return 1;
    ll x=pw(a*a%MOD, b>>1);
    if(b&1) x=x*a%MOD;
    return x;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    int n; cin>>n;
    for(int i=1; i<=n; i++) {
        cin >> arr[i].ff>>arr[i].ss;
        v.push_back(arr[i].ff); v.push_back(arr[i].ss+1);
    }

    ll res=0;
    e[0]=1;
    for(int i=1;i<=n;i++) {
        e[i]=1;
        for(int j=1;j<i;j++) {
            if(arr[j].ff<arr[i].ff) e[i]+=e[j];
        }
        res+=(e[i]%=MOD);
    }cout<<res%MOD;
}

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