oj.uz

Submission #736040

# Submission time Handle Problem Language Result Execution time Memory
736040 2023-05-05T07:04:11 Z Marceantasy Feast (NOI19_feast) C++17
12 / 100
 432 ms 24300 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long 
#define ar array
#define rep(i, n) for(int i = 0; i<(int)n; ++i)
 
const int mxN = 3e5+5, M = 1e9+7; 
int n, k;
ll a[mxN];
pair<long double, int> dp[2][mxN];

ll f(long double lambda){
    dp[0][0] = {0, 0};
    dp[1][0] = {a[0]-lambda, 1};
    for(int i = 1; i<n; ++i){
        dp[0][i] = max(dp[0][i-1], dp[1][i-1]);
        dp[1][i] = max(make_pair(dp[0][i-1].first+a[i]-lambda, dp[0][i-1].second+1), make_pair(dp[1][i-1].first+a[i], dp[1][i-1].second));
    }
    return max(dp[0][n-1], dp[1][n-1]).second;
}

void solve(){
    cin >> n >> k;
    rep(i, n) cin >> a[i];
    long double l = 0, r = 1e9;
    rep(_, 70){
        long double m = (l+r+1)/2;
        if(f(m) < k){
            r = m;
        }else{
            l = m;
        }
    }
    long double lambda = l;
    f(lambda);
    cout << (ll)round(lambda * k + max(dp[0][n-1], dp[1][n-1]).first);
}
 
int main(){
#ifdef _DEBUG
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
    std::ios_base::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);
 
    solve();
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 23584 KB Output is correct
2 Correct 270 ms 23960 KB Output is correct
3 Correct 265 ms 24300 KB Output is correct
4 Correct 229 ms 24152 KB Output is correct
5 Correct 230 ms 24004 KB Output is correct
6 Correct 222 ms 23592 KB Output is correct
7 Correct 234 ms 23596 KB Output is correct
8 Correct 257 ms 24088 KB Output is correct
9 Correct 246 ms 23628 KB Output is correct
10 Correct 228 ms 23912 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 230 ms 22092 KB Output is correct
2 Correct 225 ms 22540 KB Output is correct
3 Correct 221 ms 22020 KB Output is correct
4 Correct 224 ms 22220 KB Output is correct
5 Correct 240 ms 23568 KB Output is correct
6 Correct 221 ms 21920 KB Output is correct
7 Correct 226 ms 22476 KB Output is correct
8 Correct 234 ms 24268 KB Output is correct
9 Correct 238 ms 23432 KB Output is correct
10 Correct 254 ms 22424 KB Output is correct

Subtask #3
0 / 18.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 23584 KB Output is correct
2 Correct 270 ms 23960 KB Output is correct
3 Correct 265 ms 24300 KB Output is correct
4 Correct 229 ms 24152 KB Output is correct
5 Correct 230 ms 24004 KB Output is correct
6 Correct 222 ms 23592 KB Output is correct
7 Correct 234 ms 23596 KB Output is correct
8 Correct 257 ms 24088 KB Output is correct
9 Correct 246 ms 23628 KB Output is correct
10 Correct 228 ms 23912 KB Output is correct
11 Correct 230 ms 22092 KB Output is correct
12 Correct 225 ms 22540 KB Output is correct
13 Correct 221 ms 22020 KB Output is correct
14 Correct 224 ms 22220 KB Output is correct
15 Correct 240 ms 23568 KB Output is correct
16 Correct 221 ms 21920 KB Output is correct
17 Correct 226 ms 22476 KB Output is correct
18 Correct 234 ms 24268 KB Output is correct
19 Correct 238 ms 23432 KB Output is correct
20 Correct 254 ms 22424 KB Output is correct
21 Incorrect 432 ms 24132 KB Output isn't correct
22 Halted 0 ms 0 KB -