oj.uz

Submission #830826

# Submission time Handle Problem Language Result Execution time Memory
830826 2023-08-19T11:03:57 Z GrindMachine Feast (NOI19_feast) C++17
30 / 100
 765 ms 17428 KB 
// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
http://www.serbanology.com/vault/The%20Trick%20From%20Aliens

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

void solve(int test_case)
{
    ll n,k; cin >> n >> k;
    vector<ll> a(n+5);
    rep1(i,n) cin >> a[i];

    vector<ll> pref(n+5);
    rep1(i,n) pref[i] = pref[i-1] + a[i];

    auto get = [&](ld lambda) -> pair<ld,ll>{
        vector<pair<ld,ll>> dp(n+5);
        pair<ld,ll> best = {0,0};

        rep1(i,n){
            // do nothing
            dp[i] = dp[i-1];

            // put in subarray
            pair<ld,ll> px = {pref[i]+best.ff-lambda,best.ss+1};
            amax(dp[i],px);

            px = {-pref[i]+dp[i].ff,dp[i].ss};
            amax(best,px);
        }

        return dp[n];
    };

    ld l = 0, r = inf1*n;
    ld lambda = -1;

    rep(iter,200){
        ld mid = (l+r)/2;
        if(get(mid).ss <= k){
            lambda = mid;
            r = mid;
        }
        else{
            l = mid;
        }
    }

    auto [sum,cnt] = get(lambda);
    ll ans = sum + cnt*lambda;
    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 16724 KB Output is correct
2 Correct 576 ms 17076 KB Output is correct
3 Correct 563 ms 17272 KB Output is correct
4 Correct 550 ms 17148 KB Output is correct
5 Correct 567 ms 17068 KB Output is correct
6 Correct 542 ms 16792 KB Output is correct
7 Correct 545 ms 16764 KB Output is correct
8 Correct 553 ms 17100 KB Output is correct
9 Correct 556 ms 16808 KB Output is correct
10 Correct 560 ms 16952 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 573 ms 15188 KB Output is correct
2 Correct 583 ms 15568 KB Output is correct
3 Correct 531 ms 15152 KB Output is correct
4 Correct 549 ms 15288 KB Output is correct
5 Correct 536 ms 16816 KB Output is correct
6 Correct 535 ms 15144 KB Output is correct
7 Correct 570 ms 15540 KB Output is correct
8 Correct 569 ms 17180 KB Output is correct
9 Correct 532 ms 16732 KB Output is correct
10 Correct 564 ms 15444 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 740 ms 17280 KB Output is correct
2 Correct 737 ms 17064 KB Output is correct
3 Correct 716 ms 17224 KB Output is correct
4 Correct 706 ms 17048 KB Output is correct
5 Correct 765 ms 17196 KB Output is correct
6 Correct 728 ms 17312 KB Output is correct
7 Correct 739 ms 17380 KB Output is correct
8 Correct 751 ms 17212 KB Output is correct
9 Correct 734 ms 17428 KB Output is correct
10 Correct 727 ms 17392 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 320 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 320 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Incorrect 1 ms 320 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 543 ms 16724 KB Output is correct
2 Correct 576 ms 17076 KB Output is correct
3 Correct 563 ms 17272 KB Output is correct
4 Correct 550 ms 17148 KB Output is correct
5 Correct 567 ms 17068 KB Output is correct
6 Correct 542 ms 16792 KB Output is correct
7 Correct 545 ms 16764 KB Output is correct
8 Correct 553 ms 17100 KB Output is correct
9 Correct 556 ms 16808 KB Output is correct
10 Correct 560 ms 16952 KB Output is correct
11 Correct 573 ms 15188 KB Output is correct
12 Correct 583 ms 15568 KB Output is correct
13 Correct 531 ms 15152 KB Output is correct
14 Correct 549 ms 15288 KB Output is correct
15 Correct 536 ms 16816 KB Output is correct
16 Correct 535 ms 15144 KB Output is correct
17 Correct 570 ms 15540 KB Output is correct
18 Correct 569 ms 17180 KB Output is correct
19 Correct 532 ms 16732 KB Output is correct
20 Correct 564 ms 15444 KB Output is correct
21 Correct 740 ms 17280 KB Output is correct
22 Correct 737 ms 17064 KB Output is correct
23 Correct 716 ms 17224 KB Output is correct
24 Correct 706 ms 17048 KB Output is correct
25 Correct 765 ms 17196 KB Output is correct
26 Correct 728 ms 17312 KB Output is correct
27 Correct 739 ms 17380 KB Output is correct
28 Correct 751 ms 17212 KB Output is correct
29 Correct 734 ms 17428 KB Output is correct
30 Correct 727 ms 17392 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 1 ms 324 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Incorrect 1 ms 320 KB Output isn't correct
37 Halted 0 ms 0 KB -