제출 #526681

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
526681		jalsol	Financial Report (JOI21_financial)	C++11	65 / 100	79 ms	4292 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define Task ""

struct __Init__ {
    __Init__() {
        cin.tie(nullptr)->sync_with_stdio(false);
        if (fopen(Task".inp", "r")) {
            freopen(Task".inp", "r", stdin);
            freopen(Task".out", "w", stdout); }
    }
} __init__;

using ll = long long;

#ifdef LOCAL
#define debug(x) cerr << "[" #x " = " << x << "]\n";
#else
#define debug(...)
#endif // LOCAL

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define fi first
#define se second

#define For(i, l, r) for (int i = (l); i <= (r); ++i)
#define Ford(i, r, l) for (int i = (r); i >= (l); --i)
#define Rep(i, n) For (i, 0, (n) - 1)
#define Repd(i, n) Ford (i, (n) - 1, 0)

template<class C> int isz(const C& c) { return c.size(); }
template<class T> bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } return false; }
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } return false; }

constexpr int eps = 1e-9;
constexpr int inf = 1e9;
constexpr ll linf = 1e18;

// =============================================================================

constexpr int maxN = 3e5 + 5;

int n, d;
int a[maxN];

struct Sub1 {
    int ans = 0;

    void solve() {
        Rep (mask, 1 << n) {
            int cnt = 0;
            int mx = -inf;
            int pre = -1;
            bool ok = true;

            Rep (i, n) if (mask >> i & 1) {
                if (pre != -1 && i - pre > d) {
                    ok = false;
                    break;
                }

                if (chmax(mx, a[i + 1])) {
                    ++cnt;
                }

                pre = i;
            }

            if (ok) {
                chmax(ans, cnt);
            }
        }

        cout << ans << '\n';
    }
};

struct Sub2 {
    static constexpr int maxN = 405;

    vector<int> temp;
    int dp[maxN][maxN];

    void solve() {
        temp.resize(n);
        Rep (i, n) temp[i] = a[i + 1];
        sort(all(temp));
        temp.erase(unique(all(temp)), temp.end());

        For (i, 1, n) {
            a[i] = lower_bound(all(temp), a[i]) - temp.begin() + 1;
        }

        For (i, 1, n) {
            dp[i][a[i]] = 1;

            Ford (j, i - 1, i - d) {
                if (j <= 0) break;

                For (mx, 1, isz(temp)) if (dp[j][mx]) {
                    chmax(dp[i][max(mx, a[i])], dp[j][mx] + (mx < a[i]));
                }
            }
        }

        cout << *max_element(dp[n] + 1, dp[n] + isz(temp) + 1) << '\n';
    }
};

struct Sub3 {
    static constexpr int maxN = 7000 + 5;

    int dp[maxN];
    int ans = 0;

    void solve() {
        Ford (i, n, 1) {
            dp[i] = 1;
            int bound = min(i + d, n);

            For (j, i + 1, bound) {
                if (a[i] < a[j]) {
                    chmax(dp[i], dp[j] + 1);
                } else {
                    bound = min(j + d, n);
                }
            }

            chmax(ans, dp[i]);
        }

        cout << ans << '\n';
    }
};

struct Sub4 {
    deque<int> dq;
    int ans = 0;

    void solve() {
        Ford (i, n, 1) {
            while (isz(dq) && a[i] >= a[dq.front()]) {
                dq.pop_front();
            }

            dq.push_front(i);
            chmax(ans, isz(dq));
        }

        cout << ans << '\n';
    }
};

struct Sub5 {
    vector<int> lis;

    void solve() {
        lis.reserve(n);

        For (i, 1, n) {
            auto it = lower_bound(all(lis), a[i]);

            if (it == lis.end()) {
                lis.push_back(a[i]);
            } else {
                *it = a[i];
            }
        }

        cout << isz(lis) << '\n';
    }
};

signed main() {
    cin >> n >> d;
    For (i, 1, n) cin >> a[i];

#define SUB(x) \
    Sub##x* sol = new Sub##x{}; \
    sol->solve(); delete sol

    if (n <= 20) {
        SUB(1);
    } else if (n <= 400) {
        SUB(2);
    } else if (n <= 7000) {
        SUB(3);
    } else if (d == 1) {
        SUB(4);
    } else if (d == n) {
        SUB(5);
    }
}

/*

*/

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In constructor '__Init__::__Init__()':
Main.cpp:11:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |             freopen(Task".inp", "r", stdin);
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:12:20: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |             freopen(Task".out", "w", stdout); }
      |             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 20 / 20
• Subtask 4: 12 / 12
• Subtask 5: 5 / 5
• Subtask 6: 0 / 35