oj.uz

Submission #727194

# Submission time Handle Problem Language Result Execution time Memory
727194 2023-04-20T07:42:24 Z PenguinsAreCute Feast (NOI19_feast) C++17
0 / 100
 188 ms 10112 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL_MAX LONG_LONG_MAX
#define LL_MIN LONG_LONG_MIN
#define speed ios_base::sync_with_stdio(false); cin.tie(0)
#define stMx(a,b) a = max(a,b)
#define stMn(a,b) a = min(a,b)
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef set<int> si;
typedef vector<ii> vii;
typedef set<ii> sii;
#define REP(i, a, b) for(int i = a; i < b; i++)
int32_t main() {
    int N, K; cin >> N >> K; int A[N]; A[0]=0;
    REP(i,1,N+1) {
        cin>>A[i];
        A[i]+=A[i-1];
        //cerr<<i<<" "<<A[i]<<"\n";
    }
    ii dp[N+1];
    int l = -1, h = 300000000000005;
    while(h-l>1){
        dp[0]=mp(0,0);
        int lambda = (l+h)/2;
        //printf("Attempting lambda=%lld\n",lambda);
        ii best = mp(0,0); // value, -1 * subarrs
        REP(i,1,N+1) {
            //printf("%lld %lld %lld\n",A[i],best.fi,lambda);
            dp[i]=max(dp[i-1],mp(A[i]+best.fi-lambda,best.se-1));
            //printf("dp[%lld] has value %lld and %lld subarrs\n",i,dp[i].fi,dp[i].se);
            //printf("dp[%lld] has value %lld and %lld subarrs\n",i,dp[i].fi,dp[i].se);
            stMx(best,mp(dp[i].fi-A[i],dp[i].se));
            //printf("best is now %lld %lld\n",best.fi,best.se);
        }
        if(dp[N].se>=-1*K) h=lambda;
        else l=lambda;
        //REP(i,1,N+1){
        //    cerr<<i<<" "<<A[i]<<"\n";
        //}
    }
    ii best = mp(0,0); // value, -1 * subarrs
        REP(i,1,N+1) {
            //printf("%lld %lld %lld\n",A[i],best.fi,lambda);
            dp[i]=max(dp[i-1],mp(A[i]+best.fi-h,best.se-1));
            //printf("dp[%lld] has value %lld and %lld subarrs\n",i,dp[i].fi,dp[i].se);
            //printf("dp[%lld] has value %lld and %lld subarrs\n",i,dp[i].fi,dp[i].se);
            stMx(best,mp(dp[i].fi-A[i],dp[i].se));
            //printf("best is now %lld %lld\n",best.fi,best.se);
        }
    cout << dp[N].fi+h*K;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 7044 KB Output is correct
2 Correct 188 ms 7200 KB Output is correct
3 Correct 147 ms 7244 KB Output is correct
4 Correct 131 ms 7208 KB Output is correct
5 Incorrect 153 ms 7232 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 7200 KB Output is correct
2 Incorrect 172 ms 10112 KB Output isn't correct
3 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 146 ms 7044 KB Output is correct
2 Correct 188 ms 7200 KB Output is correct
3 Correct 147 ms 7244 KB Output is correct
4 Correct 131 ms 7208 KB Output is correct
5 Incorrect 153 ms 7232 KB Output isn't correct
6 Halted 0 ms 0 KB -