oj.uz

Submission #1017637

# Submission time Handle Problem Language Result Execution time Memory
1017637 2024-07-09T09:16:33 Z vjudge1 Feast (NOI19_feast) C++17
12 / 100
 1000 ms 2720 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define ll long long
#define pii pair<ll,ll>
const int mxN = 3e5 + 5;
const int mod = 1e9 + 7;
using namespace std;
bool operator>(pair<ll,int> a,pair<ll,int>b){
    return make_pair(a.F,-1 * a.S) > make_pair(b.F, -1 * b.S);
}
bool operator<(pair<ll,int> a,pair<ll,int>b){
    return make_pair(a.F,-1 * a.S) < make_pair(b.F, -1 * b.S);
}
int n,k;
ll a[mxN];
pair<ll,int> dp[2][2];
pair<ll,int> num;
ll ans;
bool solve(int lam){
    // cout<<lam<<'\n';
    for(int i = 0;i <= 1;i++){
        dp[i][0] = make_pair(0,0);
        dp[i][1] = make_pair(0,0);
    }
    for(int i = 1;i <= n;i++){
        // cout<<(i & 1)<<' '<<(~i & 1)<<'\n';
        dp[(i & 1)][0] = max(dp[(~i & 1)][0],dp[(~i & 1)][1]);
        dp[(i & 1)][1] = make_pair(dp[(~i & 1)][0].F + a[i] - lam,dp[~i & 1][0].S + 1);
        if(i > 1) dp[(i & 1)][1] = max(dp[(i & 1)][1],make_pair(dp[~i & 1][1].F + a[i],dp[~i & 1][1].S));
        // cout<<dp[(i & 1)][0].F<<' '<<dp[(i & 1)][0].S<<' '<<dp[(i & 1)][1].F<<' '<<dp[(i & 1)][1].S<<'\n';
    }
    num = max(dp[n & 1][0],dp[n & 1][1]);
    // cout<<num.F<<' '<<num.S<<'\n';
    return (num.S <= k);
}
signed main(){
    // cout<<"TEST";
    cin >>n>>k;
    for(int i = 1;i <= n;i++) cin >>a[i];
    ll l = 0,r = 1e16,md;
    int binit = 60;
    while(l < r){
        int md = (l + r) / 2;
        if(solve(md)){
            r = md;
            ans = num.F + num.S * md;
        }else l = md + 1;
    }
    cout<<ans;
}

Compilation message

feast.cpp: In function 'int main()':
feast.cpp:41:23: warning: unused variable 'md' [-Wunused-variable]
   41 |     ll l = 0,r = 1e16,md;
      |                       ^~
feast.cpp:42:9: warning: unused variable 'binit' [-Wunused-variable]
   42 |     int binit = 60;
      |         ^~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 2648 KB Output is correct
2 Correct 95 ms 2652 KB Output is correct
3 Correct 96 ms 2660 KB Output is correct
4 Correct 102 ms 2648 KB Output is correct
5 Correct 107 ms 2652 KB Output is correct
6 Correct 94 ms 2648 KB Output is correct
7 Correct 93 ms 2560 KB Output is correct
8 Correct 115 ms 2664 KB Output is correct
9 Correct 96 ms 2652 KB Output is correct
10 Correct 94 ms 2652 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 2708 KB Output is correct
2 Correct 63 ms 2720 KB Output is correct
3 Correct 61 ms 2668 KB Output is correct
4 Correct 61 ms 2652 KB Output is correct
5 Correct 102 ms 2656 KB Output is correct
6 Correct 101 ms 2652 KB Output is correct
7 Correct 63 ms 2652 KB Output is correct
8 Correct 103 ms 2652 KB Output is correct
9 Correct 94 ms 2644 KB Output is correct
10 Correct 62 ms 2640 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1097 ms 2644 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1016 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1016 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1016 ms 344 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 2648 KB Output is correct
2 Correct 95 ms 2652 KB Output is correct
3 Correct 96 ms 2660 KB Output is correct
4 Correct 102 ms 2648 KB Output is correct
5 Correct 107 ms 2652 KB Output is correct
6 Correct 94 ms 2648 KB Output is correct
7 Correct 93 ms 2560 KB Output is correct
8 Correct 115 ms 2664 KB Output is correct
9 Correct 96 ms 2652 KB Output is correct
10 Correct 94 ms 2652 KB Output is correct
11 Correct 61 ms 2708 KB Output is correct
12 Correct 63 ms 2720 KB Output is correct
13 Correct 61 ms 2668 KB Output is correct
14 Correct 61 ms 2652 KB Output is correct
15 Correct 102 ms 2656 KB Output is correct
16 Correct 101 ms 2652 KB Output is correct
17 Correct 63 ms 2652 KB Output is correct
18 Correct 103 ms 2652 KB Output is correct
19 Correct 94 ms 2644 KB Output is correct
20 Correct 62 ms 2640 KB Output is correct
21 Execution timed out 1097 ms 2644 KB Time limit exceeded
22 Halted 0 ms 0 KB -