oj.uz

Submission #1017633

# Submission time Handle Problem Language Result Execution time Memory
1017633 2024-07-09T09:15:20 Z vjudge1 Feast (NOI19_feast) C++17
12 / 100
 1000 ms 2672 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define ll long long
#define pii pair<ll,ll>
const int mxN = 1e6 + 5;
const int mod = 1e9 + 7;
double lambda = 1e-8;
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;
int 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:42:23: warning: unused variable 'md' [-Wunused-variable]
   42 |     ll l = 0,r = 1e16,md;
      |                       ^~
feast.cpp:43:9: warning: unused variable 'binit' [-Wunused-variable]
   43 |     int binit = 60;
      |         ^~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 2648 KB Output is correct
2 Correct 114 ms 2648 KB Output is correct
3 Correct 117 ms 2652 KB Output is correct
4 Correct 96 ms 2648 KB Output is correct
5 Correct 95 ms 2652 KB Output is correct
6 Correct 94 ms 2652 KB Output is correct
7 Correct 125 ms 2572 KB Output is correct
8 Correct 96 ms 2648 KB Output is correct
9 Correct 101 ms 2652 KB Output is correct
10 Correct 102 ms 2640 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 2652 KB Output is correct
2 Correct 63 ms 2648 KB Output is correct
3 Correct 62 ms 2656 KB Output is correct
4 Correct 80 ms 2652 KB Output is correct
5 Correct 103 ms 2648 KB Output is correct
6 Correct 66 ms 2652 KB Output is correct
7 Correct 74 ms 2672 KB Output is correct
8 Correct 106 ms 2652 KB Output is correct
9 Correct 100 ms 2652 KB Output is correct
10 Correct 77 ms 2652 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1047 ms 2628 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 348 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 348 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 348 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 2648 KB Output is correct
2 Correct 114 ms 2648 KB Output is correct
3 Correct 117 ms 2652 KB Output is correct
4 Correct 96 ms 2648 KB Output is correct
5 Correct 95 ms 2652 KB Output is correct
6 Correct 94 ms 2652 KB Output is correct
7 Correct 125 ms 2572 KB Output is correct
8 Correct 96 ms 2648 KB Output is correct
9 Correct 101 ms 2652 KB Output is correct
10 Correct 102 ms 2640 KB Output is correct
11 Correct 61 ms 2652 KB Output is correct
12 Correct 63 ms 2648 KB Output is correct
13 Correct 62 ms 2656 KB Output is correct
14 Correct 80 ms 2652 KB Output is correct
15 Correct 103 ms 2648 KB Output is correct
16 Correct 66 ms 2652 KB Output is correct
17 Correct 74 ms 2672 KB Output is correct
18 Correct 106 ms 2652 KB Output is correct
19 Correct 100 ms 2652 KB Output is correct
20 Correct 77 ms 2652 KB Output is correct
21 Execution timed out 1047 ms 2628 KB Time limit exceeded
22 Halted 0 ms 0 KB -