oj.uz

Submission #1017353

# Submission time Handle Problem Language Result Execution time Memory
1017353 2024-07-09T07:32:51 Z nathan4690 Feast (NOI19_feast) C++17
18 / 100
 127 ms 18396 KB 
// NOI19 Task 3: Feast
// https://oj.uz/problem/view/NOI19_feast
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define el cout << '\n'
#define f1(i,n) for(ll i=1;i<=n;i++)
#define __file_name ""
using namespace std;
const ll maxn = 1e6+5, inf=1e18;

ll n,k,a[maxn],b[maxn],L,R,mid;
pair<ll,ll> dp[2][maxn];

pair<ll,ll> check(ll lambda){
    // Penalty is lambda per subarray
    dp[1][0] = {-inf, 0};
    f1(i,n){
        dp[0][i] = max(dp[0][i-1], dp[1][i-1]);
        dp[1][i] = max(make_pair(dp[1][i-1].first + a[i], dp[1][i-1].second),
                       make_pair(dp[0][i-1].first + a[i] - lambda, dp[0][i-1].second + 1));
    }
    return max(dp[0][n], dp[1][n]);
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    if(fopen(__file_name ".inp", "r")){
        freopen(__file_name ".inp","r",stdin);
        freopen(__file_name ".out","w",stdout);
    }
    // code here
    cin >> n >> k;
    f1(i,n) cin >> a[i];
    f1(i,n) b[i] = a[i];
    sort(b+1,b+n+1);
    // ll ans = 0;
    // for(ll i=n;i>=n-k+1;i--) ans += b[i];
    L = 0; R = 1e18;
    while(L <= R){
        mid = (L+R)/2;
        if(check(mid).second >= k) L = mid+1;
        else R = mid-1;
    }
    // cout << L << ' ' << R << ' ' << check(L).second;el;
    pair<ll,ll> res = check(R);
    // cout << res.second;el;
    cout << max(0ll, res.first + k * R);
    return 0;
}

/*
Code by: Nguyen Viet Trung Nhan
Cau Giay Secondary School
*/

Compilation message

feast.cpp: In function 'int main()':
feast.cpp:30:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |         freopen(__file_name ".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:31:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         freopen(__file_name ".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 18076 KB Output is correct
2 Correct 63 ms 18328 KB Output is correct
3 Correct 61 ms 18012 KB Output is correct
4 Incorrect 59 ms 18004 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 18000 KB Output is correct
2 Correct 101 ms 18000 KB Output is correct
3 Correct 121 ms 18396 KB Output is correct
4 Correct 96 ms 18000 KB Output is correct
5 Correct 96 ms 16220 KB Output is correct
6 Correct 115 ms 18208 KB Output is correct
7 Correct 103 ms 18108 KB Output is correct
8 Correct 103 ms 14300 KB Output is correct
9 Correct 105 ms 15640 KB Output is correct
10 Correct 127 ms 14416 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Incorrect 1 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

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