oj.uz

Submission #545658

# Submission time Handle Problem Language Result Execution time Memory
545658 2022-04-05T06:00:49 Z balbit Feast (NOI19_feast) C++14
12 / 100
 153 ms 14824 KB 
#include <bits/stdc++.h>
#define int ll
using namespace std;

#define ll long long
#define f first
#define s second
#define pii pair<ll, ll>

#define MX(a,b) a=max(a,b)
#define MN(a,b) a=min(a,b)
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()

#define REP(i,n) for (int i = 0; i<n; ++i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define pb push_back

#ifdef BALBIT
#define bug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do( T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do( T && x, S && ...y) {cerr<<x<<", "; _do(y...);}
#else
#define bug(...)
#define endl '\n'
#endif // BALBIT

const int maxn = 3e5+5;
const ll inf = 1ll<<61;
ll A[maxn];
pii dp[maxn][2];

int n;

pair<ll, ll> operator + (pair<ll, ll> a, pair<ll, ll> b) {
    return {a.f + b.f, a.s + b.s};
}

pair<ll, ll> get(int p) {
    // beware of initial states!!
    dp[0][0] = {0, 0}; // no value, nothing taken yet
    dp[0][1] = {-inf, -inf};
    REP1(i,n) {
        dp[i][0] = dp[i][1] = {-inf, inf};
        MX(dp[i][0], dp[i-1][0]); // continue not taking anything
        MX(dp[i][0], dp[i-1][0] + make_pair(-p, -1)); // take an empty segment (?)
        MX(dp[i][0], dp[i-1][1]); // stop taking stuff
        MX(dp[i][1], dp[i-1][0] + make_pair(-p + A[i], -1));
        MX(dp[i][1], dp[i-1][1] + make_pair(-p + A[i], -1));
        MX(dp[i][1], dp[i-1][1] + make_pair(A[i], 0));
    }
    return max(dp[n][0], dp[n][1]);
}

inline ll DIV(ll a, ll b) {
    return a/b - ((a%b) && ((a^b)<0));
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    bug(1,2);

    int k; cin>>n>>k;
    REP1(i,n) {
        cin>>A[i];
    }

    ll l = 0, r = 2e9+10;

    while (l!=r) {
        ll md = DIV((l+r),2);
        pair<ll, ll> gt = get(md);
        if (-gt.s > k) {
            // taking too many zones, gotta make the penalty higher
            l = md+1;
        }else{
            r = md;
        }
    }

    pair<ll, ll> gt = get(l);
    // only linear difference from it
    bug(l, gt.f, -gt.s);
    ll re = gt.f + (k) * (l);
    cout<<re<<endl;


}

/*
5 2
5 -100 6 -100 7 -100
*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 12616 KB Output is correct
2 Correct 102 ms 14656 KB Output is correct
3 Correct 102 ms 14824 KB Output is correct
4 Correct 102 ms 14816 KB Output is correct
5 Correct 104 ms 14716 KB Output is correct
6 Correct 100 ms 14488 KB Output is correct
7 Correct 100 ms 14484 KB Output is correct
8 Correct 102 ms 14668 KB Output is correct
9 Correct 103 ms 14516 KB Output is correct
10 Correct 103 ms 14664 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 12276 KB Output is correct
2 Correct 103 ms 13160 KB Output is correct
3 Correct 94 ms 12748 KB Output is correct
4 Correct 95 ms 12972 KB Output is correct
5 Correct 101 ms 14504 KB Output is correct
6 Correct 95 ms 12944 KB Output is correct
7 Correct 94 ms 13104 KB Output is correct
8 Correct 128 ms 14744 KB Output is correct
9 Correct 108 ms 14364 KB Output is correct
10 Correct 98 ms 13000 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 153 ms 12940 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 12616 KB Output is correct
2 Correct 102 ms 14656 KB Output is correct
3 Correct 102 ms 14824 KB Output is correct
4 Correct 102 ms 14816 KB Output is correct
5 Correct 104 ms 14716 KB Output is correct
6 Correct 100 ms 14488 KB Output is correct
7 Correct 100 ms 14484 KB Output is correct
8 Correct 102 ms 14668 KB Output is correct
9 Correct 103 ms 14516 KB Output is correct
10 Correct 103 ms 14664 KB Output is correct
11 Correct 101 ms 12276 KB Output is correct
12 Correct 103 ms 13160 KB Output is correct
13 Correct 94 ms 12748 KB Output is correct
14 Correct 95 ms 12972 KB Output is correct
15 Correct 101 ms 14504 KB Output is correct
16 Correct 95 ms 12944 KB Output is correct
17 Correct 94 ms 13104 KB Output is correct
18 Correct 128 ms 14744 KB Output is correct
19 Correct 108 ms 14364 KB Output is correct
20 Correct 98 ms 13000 KB Output is correct
21 Incorrect 153 ms 12940 KB Output isn't correct
22 Halted 0 ms 0 KB -