Submission #61176

#	Time	Username	Problem	Language	Result	Execution time	Memory
61176		Flugan42	Boat (APIO16_boat)	C++14	9 / 100	2055 ms	14404 KiB

boat

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef long double lld;
#define rep(i,a,b) for(ll i = a; i < b; i++)
#define per(i,a,b) for(ll i = a; i >= b; i--)
#define inf 1000000000000000000
#define all(x) x.begin(),x.end()
#define sz(x) (ll)(x).size()
#define trav(a,x) for(auto a : x)

const ll mod = 1000000007;
ll n;
vi a,b,s;

int main(){
  cin >> n;
  a.assign(n,0); b.assign(n,0);
  rep(i,0,n) {
    cin >> a[i] >> b[i];
    assert(b[i]-a[i] < 1000010);
    per(j,b[i],a[i]) { s.push_back(j); }
  }

  vi dp; dp.assign(sz(s),0);
  rep(i,0,sz(s)){
    dp[i] = 1;
    rep(j,0,i) if (s[j] < s[i]) dp[i] = (dp[i]+dp[j])%mod;
  }

  ll res = 0;
  rep(i,0,sz(s)) res = (res+dp[i])%mod;
  cout << res << endl;

}

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