제출 #1147833

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1147833		alexbri	Feast (NOI19_feast)	C++20	0 / 100	1094 ms	15524 KiB

feast

#include<bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ll = long long;
using vll = vector<ll>;
using ii = pair<int, int>;
using vii = vector<ii>;
using ld = long double;
#define rep(i, a, b) for (int i = a;  i < b; i++)
#define all(x) x.begin(), x.end()
#define pb(x) push_back(x)
#define sz(x) x.size()

pair<ld, int> f(vector<ld> &nums, ld x) {

    int n = nums.size();
    vector<ld> pf(n), dp(n);
    vi used(n);

    int best = 0;

    rep(i, 1, n) {
        pf[i] = pf[i - 1] + nums[i];
        dp[i] = pf[i] + dp[best] - pf[best] - x;
        used[i] = used[best] + 1;

        if (dp[i - 1] > dp[i]) {
            dp[i] = dp[i - 1];
            used[i] = used[i - 1];
        }

        if (dp[i] - pf[i] > dp[best] - pf[best])
            best = i;

    }

    best = 0;

    rep(i, 1, n)
        if (dp[i] > dp[best])
            best = i;
    
    return {dp[best], used[best]};
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, k; cin >> n >> k;
    vector<ld> nums(n + 1); 
    rep(i, 0, n) {
        ll x; cin >> x;
        nums[i + 1] = x;
    }

    ld l = -1e13, r = 1e13;
    rep(_, 0, 200) {
        ld m = (l + r) / 2.00;
        ld g; 
        int opt;
        tie(g, opt) = f(nums, m);

        if (opt < k)
            r = m;
        else
            l = m;
    }
    
    cout << max(0ll, ll(f(nums, l).first + l * ld(k))) << "\n";
}

/*

    dp[l - 1] - pf[l - 1] - x

    Si voy a cerrar un subarreglo en r, me conviene que sea el que maximice el valor de 
    dp[l - 1] - pf[l - 1] - x

*/

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