oj.uz

Submission #545651

# Submission time Handle Problem Language Result Execution time Memory
545651 2022-04-05T05:47:17 Z balbit Feast (NOI19_feast) C++14
12 / 100
 157 ms 14908 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 = -2e9-10, 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 range smaller
            r = md;
        }else{
            l = md+1;
        }
    }

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


}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 14480 KB Output is correct
2 Correct 103 ms 14732 KB Output is correct
3 Correct 109 ms 14908 KB Output is correct
4 Correct 113 ms 14828 KB Output is correct
5 Correct 105 ms 14732 KB Output is correct
6 Correct 98 ms 14492 KB Output is correct
7 Correct 113 ms 14456 KB Output is correct
8 Correct 105 ms 14672 KB Output is correct
9 Correct 97 ms 14472 KB Output is correct
10 Correct 107 ms 14668 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 12880 KB Output is correct
2 Correct 107 ms 13160 KB Output is correct
3 Correct 109 ms 12852 KB Output is correct
4 Correct 107 ms 12952 KB Output is correct
5 Correct 108 ms 14496 KB Output is correct
6 Correct 106 ms 12848 KB Output is correct
7 Correct 120 ms 13188 KB Output is correct
8 Correct 114 ms 14848 KB Output is correct
9 Correct 102 ms 14452 KB Output is correct
10 Correct 94 ms 13092 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 157 ms 14864 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 212 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 212 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 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 14480 KB Output is correct
2 Correct 103 ms 14732 KB Output is correct
3 Correct 109 ms 14908 KB Output is correct
4 Correct 113 ms 14828 KB Output is correct
5 Correct 105 ms 14732 KB Output is correct
6 Correct 98 ms 14492 KB Output is correct
7 Correct 113 ms 14456 KB Output is correct
8 Correct 105 ms 14672 KB Output is correct
9 Correct 97 ms 14472 KB Output is correct
10 Correct 107 ms 14668 KB Output is correct
11 Correct 115 ms 12880 KB Output is correct
12 Correct 107 ms 13160 KB Output is correct
13 Correct 109 ms 12852 KB Output is correct
14 Correct 107 ms 12952 KB Output is correct
15 Correct 108 ms 14496 KB Output is correct
16 Correct 106 ms 12848 KB Output is correct
17 Correct 120 ms 13188 KB Output is correct
18 Correct 114 ms 14848 KB Output is correct
19 Correct 102 ms 14452 KB Output is correct
20 Correct 94 ms 13092 KB Output is correct
21 Incorrect 157 ms 14864 KB Output isn't correct
22 Halted 0 ms 0 KB -