Submission #1285321

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285321		chipilin	Feast (NOI19_feast)	C++20	100 / 100	259 ms	34480 KiB

feast

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll; 
typedef vector<ll> vl; 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<pii> vii;

const ll inf = (1LL << 62) ; 

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

    int n, k; cin >> n >> k ;
    vi v(n); rep(i,0,n) cin >> v[i]; 

    vector<vl> dp(n, vl(2, -inf)); 
    vvi cnt(n, vi(2, 0)); 
    auto solve = [&](ll lm) { 
        rep(i,0,n) { 
            dp[i][0] = dp[i][1] = -inf; 
            cnt[i][0] = cnt[i][1] = 0; 
        }
        dp[0][0] = 0, cnt[0][0] = 0;
        dp[0][1] = v[0] - lm, cnt[0][1] = 1; 

        rep(i,1,n) {
            if(dp[i - 1][0] > dp[i - 1][1]) { 
                dp[i][0] = dp[i - 1][0];
                cnt[i][0] = cnt[i - 1][0];  
            }else{ 
                dp[i][0] = dp[i - 1][1]; 
                cnt[i][0] = cnt[i - 1][1]; 
            }
            if(dp[i - 1][1] + v[i] > dp[i - 1][0] + v[i] - lm) { 
                dp[i][1] = dp[i - 1][1] + v[i]; 
                cnt[i][1] = cnt[i - 1][1]; 
            }else{ 
                dp[i][1] = dp[i - 1][0] + v[i] - lm; 
                cnt[i][1] = cnt[i - 1][0] + 1; 
            }
        }
        if(dp[n - 1][1] > dp[n - 1][0]) return make_pair(dp[n - 1][1], cnt[n - 1][1]) ; 
        else return make_pair(dp[n - 1][0], cnt[n - 1][0]) ;  
    };

    ll low = 0, high = inf; 
    while(high - low > 1) { 
        ll mid = low + (high - low) / 2; 
        auto cur = solve(mid) ; 
        if(cur.second >= k) low = mid; 
        else high = mid; 
    }
    // cerr << "low: " << low << "\n";
    cout << solve(low).first + low * k << "\n"; 
}

• 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