Submission #561540

#	Time	Username	Problem	Language	Result	Execution time	Memory
561540		beep_boop	Boat (APIO16_boat)	C++17	9 / 100	3 ms	1300 KiB

boat

/*
 * Created at 11:34 AM on 13 May, 2022
 */

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
#include <numeric>
#include <cassert>
#include <functional>

using namespace std;

#define rep(i, a, b) for(auto (i)=a;(i)<(b);(i)++)
#define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define SZ(x) (int)(x).size()
#define vt vector
#define trav(a, x) for(auto& (a): (x))
#define DO if(true)

#define mp make_pair
#define pb push_back
#define eb emplace_back

//#define int int64_t

typedef vector<int> vi;
typedef pair<int, int> pi;

#define mod 1000000007

void setIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

template<typename T>
void read(vector<T> &a, int n) {
    a.resize(n);
    for (auto &x: a) cin >> x;
}

template<class T, class U>
ostream &operator<<(ostream &out, const pair<T, U> &v) {
    out << "(";
    out << v.first << ", " << v.second;
    return out << ")";
}

template<class T>
ostream &operator<<(ostream &out, const vector<T> &v) {
    out << "[";
    list(i, SZ(v)) {
        if (i) out << ", ";
        out << v[i];
    }
    return out << "]";
}

template<typename T>
void print(vector<T> &a) {
    for (const auto &x: a) cout << x << ' ';
    cout << '\n';
}

template<typename T>
void MOD(T &x, int m = mod) {
    x %= m;
    if (x < 0) x += m;
}

#define trace(...) dbg(#__VA_ARGS__, __VA_ARGS__)

template<typename T>
void dbg(const char *name, T &&arg1) {
    cout << name << " : " << arg1 << '\n';
}

template<typename T, typename... U>
void dbg(const char *names, T &&arg1, U &&... args) {
    const char *comma = strchr(names + 1, ',');
    cout.write(names, comma - names) << " : " << arg1 << " | ";
    dbg(comma + 1, args...);
}

template<class T>
void read(T &x) {
    cin >> x;
}

template<class T, class... U>
void read(T &t, U &... u) {
    read(t);
    read(u...);
}

int gcd(int a, int b) { return !a ? b : gcd(b % a, a); }

int ceil_div(int a, int b) { return (a + b - 1) / b; }

using ll = int64_t;

const int N = 505;
int n;
vt<pi> a;

void sub(int& x){
    while(x >= mod){
        x -= mod;
    }
}

int32_t main() {
    setIO();

    read(n);
    a.resize(n);
    trav(c, a){
        read(c.first, c.second);
    }

    //Initialization
    vt<vi> dp(n + 1, vi(n + 1, 0));

    //Base Case
    list(i, n) {
        dp[n][i] = 1;
    }

    //Computation
    for(int idx = n - 1; idx >= 0; idx--){
        for(int prev = 0; prev <= n; prev++){
            int& res = dp[idx][prev];
            res = 0;

            //Either Pick
            if(prev == n or a[idx] > a[prev]) {
                res += dp[idx + 1][idx];
                sub(res);
            }

            //or not
            res += dp[idx + 1][prev];
            sub(res);
        }
    }

    cout << dp[0][n] << '\n';
    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'std::ostream& operator<<(std::ostream&, const std::vector<T>&)':
boat.cpp:23:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   23 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
      |                             ^
boat.cpp:63:5: note: in expansion of macro 'list'
   63 |     list(i, SZ(v)) {
      |     ^~~~
boat.cpp: In function 'int32_t main()':
boat.cpp:28:30: warning: unnecessary parentheses in declaration of 'c' [-Wparentheses]
   28 | #define trav(a, x) for(auto& (a): (x))
      |                              ^
boat.cpp:128:5: note: in expansion of macro 'trav'
  128 |     trav(c, a){
      |     ^~~~
boat.cpp:23:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   23 | #define list(i, N) for(auto (i)=0;(i)<(N);(i)++)
      |                             ^
boat.cpp:136:5: note: in expansion of macro 'list'
  136 |     list(i, n) {
      |     ^~~~

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