Submission #1091182

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091182		connornguyxn	Financial Report (JOI21_financial)	C++14	65 / 100	110 ms	7884 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using str = string;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <class T>
using vector2 = vector<vector<T>>;
template <class T>
using vector3 = vector<vector2<T>>;
#define fi first
#define se second
#define nl '\n'
#define sp ' '
#define all(a) (a).begin(), (a).end()
#define tvl (tv * 2)
#define tvr (tv * 2 + 1)
#define FOR(i, l, r) for (ll i = (l), _r = (r); i <= _r; i++)
#define FORD(i, r, l) for (ll i = (r), _l = (l); i >= _l; i--)
#define FORIN(it, a) for (auto& it : a)
#define bmask(i) (1LL << (i))
#define bget(i, n) ((n) >> (i) & 1)
const ll MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
template <class T, class... C>
void assign(int n, T v, C&&... a) {
    using e = int[];
    e{(a.assign(n, v), 0)...};
}
template <class... C>
void resize(int n, C&&... a) {
    using e = int[];
    e{(a.resize(n), 0)...};
}
////////////////////////////////////////
template <class... T>
void print(T&&... a) {
    cout << "[debug] ";
    using e = int[];
    e{(cout << a << sp, 0)...};
    cout << endl;
}
template <class Ch, class Tr, class C>
basic_ostream<Ch, Tr>& operator<<(basic_ostream<Ch, Tr>& cout, C a) {
    cout << "{ ";
    FORIN(it, a) cout << it << sp;
    return cout << "}";
}
template <class T1, class T2>
ostream& operator<<(ostream& cout, pair<T1, T2> a) {
    return cout << '(' << a.fi << sp << a.se << ')';
}
void logtime() {
    cout << flush;
    clog << nl << "[time] " << clock() * 1.0 / CLOCKS_PER_SEC << nl;
}


// imparr
// <tags>

int n, m, d;
vector<int> a;
////////////////////////////////////////////////////////////////////////////////
namespace sub2 {
    bool checksub() {
        return n <= 400;
    }
    ////////////////////////////////////////
    vector2<int> dp;
    ////////////////////////////////////////
    int solve(int cur, int mx) {
        if (cur > n) return 0;
        
        int& res = dp[cur][mx];
        if (res != -1) return res;
        res = 0;
        
        FOR(nxt, cur + 1, min(n, cur + d)) {
            res = max(res, solve(nxt, max(mx, a[nxt])) + (a[nxt] > mx));
        }
        
        return res;
    }
    
    ////////////////////////////////////////
    void main() {
        dp.assign(n + 1, vector<int>(m + 1, -1));
        int ans = 0;
        FOR(i, 1, n) ans = max(ans, solve(i, a[i]) + 1);
        cout << ans;
    }
}
////////////////////////////////////////////////////////////////////////////////
namespace sub3 {
    bool checksub() {
        return n <= 7000;
    }
    ////////////////////////////////////////
    vector<int> dp;
    ////////////////////////////////////////
    int solve(int cur) {
        if (cur > n) return 0;
        
        int& res = dp[cur];
        if (res != -1) return res;
        res = 0;
        
        int last = cur + d;
        for (int i = cur + 1; i <= n && i <= last; i++) {
            if (a[i] > a[cur]) {
                res = max(res, solve(i) + 1);
            } else {
                last = i + d;
            }
        }
        
        return res;
    }
    ////////////////////////////////////////
    void main() {
        dp.assign(n + 1, -1);
        int ans = 0;
        FOR(i, 1, n) ans = max(ans, solve(i) + 1);
        cout << ans;
    }
}
////////////////////////////////////////////////////////////////////////////////
namespace sub4 {
    bool checksub() {
        return d == 1;
    }
    ////////////////////////////////////////
    void main() {
        int ans = 0;
        
        a.push_back(INF);
        deque<int> st{n + 1};
        FORD(i, n, 1) {
            while (a[st.back()] <= a[i]) st.pop_back();
            st.push_back(i);
            ans = max(ans, (int)st.size() - 1);
        }
        
        cout << ans;
    }
}
////////////////////////////////////////////////////////////////////////////////
namespace sub5 {
    bool checksub() {
        return d == n;
    }
    ////////////////////////////////////////
    void main() {
        vector<int> dp(1, INF);
        FOR(i, 1, n) {
            if (a[i] > dp.back()) {
                dp.push_back(a[i]);
            } else {
                *lower_bound(all(dp), a[i]) = a[i];
            };
        };
        cout << dp.size();
    }
}
////////////////////////////////////////////////////////////////////////////////
namespace sub6 {
    ////////////////////////////////////////
    void main() {
        
    }
}
////////////////////////////////////////////////////////////////////////////////
int main() {
    #define TASK "imparr"
   // freopen(TASK".inp", "r", stdin);
 //   freopen(TASK".out", "w", stdout);
    cin.tie(nullptr)->sync_with_stdio(false);
    atexit(logtime);
    ////////////////////////////////////////
    cin >> n >> d;
    
    resize(n + 1, a);
    FOR(i, 1, n) cin >> a[i];
    
    vector<int> zip = a;
    sort(all(zip));
    zip.erase(unique(all(zip)), zip.end());
    FOR(i, 0, n) a[i] = lower_bound(all(zip), a[i]) - zip.begin(); 
    m = zip.size();
    
    if (sub2::checksub()) return sub2::main(), 0;
    if (sub3::checksub()) return sub3::main(), 0;
    if (sub4::checksub()) return sub4::main(), 0;
    if (sub5::checksub()) return sub5::main(), 0;
    ////////////////////////////////////////
}

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