oj.uz

Submission #1017570

# Submission time Handle Problem Language Result Execution time Memory
1017570 2024-07-09T08:54:45 Z vjudge1 Feast (NOI19_feast) C++17
41 / 100
 26 ms 2132 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define int long long
#define pii pair<ll,ll>
const int mxN = 1e5 + 5;
const int mod = 1e9 + 7;
double lambda = 1e-8;
using namespace std;
bool operator>(pair<int,int> a,pair<int,int>b){
    return make_pair(a.F,-1 * a.S) > make_pair(b.F, -1 * b.S);
}
bool operator<(pair<int,int> a,pair<int,int>b){
    return make_pair(a.F,-1 * a.S) < make_pair(b.F, -1 * b.S);
}
int n,k;
int a[mxN];
pair<int,int> dp[mxN][2];
pair<int,int> num;
int ans;
bool solve(int lam){
    // cout<<lam<<'\n';
    for(int i = 0;i <= n;i++){
        dp[i][1] = make_pair(0,0);
        dp[i][0] = make_pair(0,0);
    }
    for(int i = 1;i <= n;i++){
        dp[i][0] = max(dp[i - 1][0],dp[i - 1][1]);
        dp[i][1] = make_pair(dp[i - 1][0].F + a[i] - lam,dp[i - 1][0].S + 1);
        if(i > 1) dp[i][1] = max(dp[i][1],make_pair(dp[i - 1][1].F + a[i],dp[i - 1][1].S));
        // cout<<dp[i][0].F<<' '<<dp[i][0].S<<' '<<dp[i][1].F<<' '<<dp[i][1].S<<'\n';
    }
    num = max(dp[n][0],dp[n][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];
    int 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:24: warning: unused variable 'md' [-Wunused-variable]
   41 |     int l = 0,r = 1e16,md;
      |                        ^~
feast.cpp:42:9: warning: unused variable 'binit' [-Wunused-variable]
   42 |     int binit = 60;
      |         ^~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 2132 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 26 ms 1896 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 392 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 392 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 400 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 392 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 400 KB Output is correct
21 Correct 1 ms 344 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 2 ms 348 KB Output is correct
25 Correct 1 ms 344 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 1 ms 448 KB Output is correct
30 Correct 1 ms 348 KB Output is correct

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 2132 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -