oj.uz

Submission #561540

# Submission time Handle Problem Language Result Execution time Memory
561540 2022-05-13T06:07:58 Z beep_boop Boat (APIO16_boat) C++17
9 / 100
 3 ms 1300 KB 
/*
 * 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

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1236 KB Output is correct
2 Correct 3 ms 1236 KB Output is correct
3 Correct 3 ms 1276 KB Output is correct
4 Correct 2 ms 1300 KB Output is correct
5 Correct 3 ms 1236 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 2 ms 1236 KB Output is correct
8 Correct 2 ms 1220 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct
10 Correct 2 ms 1236 KB Output is correct
11 Correct 2 ms 1236 KB Output is correct
12 Correct 2 ms 1248 KB Output is correct
13 Correct 2 ms 1236 KB Output is correct
14 Correct 2 ms 1236 KB Output is correct
15 Correct 2 ms 1236 KB Output is correct
16 Correct 2 ms 1236 KB Output is correct
17 Correct 2 ms 1236 KB Output is correct
18 Correct 3 ms 1236 KB Output is correct
19 Correct 2 ms 1236 KB Output is correct
20 Correct 2 ms 1236 KB Output is correct

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1236 KB Output is correct
2 Correct 3 ms 1236 KB Output is correct
3 Correct 3 ms 1276 KB Output is correct
4 Correct 2 ms 1300 KB Output is correct
5 Correct 3 ms 1236 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 2 ms 1236 KB Output is correct
8 Correct 2 ms 1220 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct
10 Correct 2 ms 1236 KB Output is correct
11 Correct 2 ms 1236 KB Output is correct
12 Correct 2 ms 1248 KB Output is correct
13 Correct 2 ms 1236 KB Output is correct
14 Correct 2 ms 1236 KB Output is correct
15 Correct 2 ms 1236 KB Output is correct
16 Correct 2 ms 1236 KB Output is correct
17 Correct 2 ms 1236 KB Output is correct
18 Correct 3 ms 1236 KB Output is correct
19 Correct 2 ms 1236 KB Output is correct
20 Correct 2 ms 1236 KB Output is correct
21 Incorrect 3 ms 1236 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1236 KB Output is correct
2 Correct 3 ms 1236 KB Output is correct
3 Correct 3 ms 1276 KB Output is correct
4 Correct 2 ms 1300 KB Output is correct
5 Correct 3 ms 1236 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 2 ms 1236 KB Output is correct
8 Correct 2 ms 1220 KB Output is correct
9 Correct 2 ms 1236 KB Output is correct
10 Correct 2 ms 1236 KB Output is correct
11 Correct 2 ms 1236 KB Output is correct
12 Correct 2 ms 1248 KB Output is correct
13 Correct 2 ms 1236 KB Output is correct
14 Correct 2 ms 1236 KB Output is correct
15 Correct 2 ms 1236 KB Output is correct
16 Correct 2 ms 1236 KB Output is correct
17 Correct 2 ms 1236 KB Output is correct
18 Correct 3 ms 1236 KB Output is correct
19 Correct 2 ms 1236 KB Output is correct
20 Correct 2 ms 1236 KB Output is correct
21 Incorrect 3 ms 1236 KB Output isn't correct
22 Halted 0 ms 0 KB -