제출 #445861

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
445861		0e4ef622	Feast (NOI19_feast)	C++14	100 / 100	354 ms	15228 KiB

feast

#include <bits/stdc++.h>
#define F first
#define S second
#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define per(i, a, b) for(int i = (b)-1; i >= (a); --i)
#define bck(i, a, b) if ((i) >= (a) && (i) < (b))
#define trav(x, a) for (auto &x : (a))
#define sz(a) (int)(a).size()
#define all(x) (x).begin(), (x).end()
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define dbg(X) std::cerr << "[DBG]("<<__FUNCTION__<<":"<<__LINE__<<") " << #X << ": " << X << std::endl;
using namespace std;
typedef long long ll;
typedef string str;
template<typename T> using vec = vector<T>;
template<typename T> using pq = priority_queue<T, vector<T>, std::greater<T>>;
template<typename T> using mxpq = priority_queue<T>;
typedef pair<int,int> pii;
typedef vec<int> vi;
typedef vec<pii> vii;
typedef vec<vi> vvi;
typedef pair<ll,ll> pll;
typedef vec<ll> vl;
typedef vec<pll> vll;
typedef vec<vl> vvl;
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<typename A, typename B>
istream& operator>>(istream& s, pair<A,B>& p) { return s>>p.first>>p.second; }
template<typename A, typename B>
ostream& operator<<(ostream& s, const pair<A,B>& p) { return s<<"{"<<p.first<<", "<<p.second<<"}"; }
template<typename T>
istream& operator>>(istream& s, vec<T>& p) { for (T& t : p) s >> t; return s; }
template<typename T>
ostream& operator<<(ostream& s, const vec<T>& p) { for (const T& t : p) s << t << " "; return s; }

pll go(vl& a, ll cost) {
    int n = sz(a);
    vl dp0(n),dp1(n), cnt1(n), cnt0(n);
    dp0[0] = 0;
    dp1[0] = a[0] - cost;
    cnt0[0]=0;
    cnt1[0]=1;
    rep(i, 1, n) {
        dp0[i] = max(dp0[i-1], dp1[i-1]);
        if (dp0[i-1] >= dp1[i-1]) cnt0[i] = cnt0[i-1];
        else cnt0[i] = cnt1[i-1];
        dp1[i] = max(dp0[i-1] - cost, dp1[i-1]) + a[i];
        if (dp0[i-1] - cost > dp1[i-1]) {
            cnt1[i] = cnt0[i-1] + 1;
        } else {
            cnt1[i] = cnt1[i-1];
        }
    }
    if (dp0.back() >= dp1.back()) {
        return {dp0.back(), cnt0.back()};
    } else {
        return {dp1.back(), cnt1.back()};
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n, k; cin >> n >> k;
    vl a(n); cin >> a;
    /* cout << go(a, 0) << endl; */
    /* cout << go(a, 1) << endl; */
    /* cout << go(a, 2) << endl; */
    /* cout << go(a, 3) << endl; */
    ll lo = 0, hi = 1e12;
    while (hi - lo > 1) {
        ll m = (lo + hi)/2;
        ll x = go(a, m).S;
        if (x >= k) lo = m;
        else hi=m;
    }
    cout << go(a, lo).F + lo*k << endl;
}

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29