oj.uz

Submission #1017357

# Submission time Handle Problem Language Result Execution time Memory
1017357 2024-07-09T07:33:18 Z nathan4690 Feast (NOI19_feast) C++17
18 / 100
 108 ms 18300 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 << 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 73 ms 17744 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 17876 KB Output is correct
2 Correct 59 ms 18256 KB Output is correct
3 Correct 61 ms 18008 KB Output is correct
4 Incorrect 60 ms 18000 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 101 ms 18164 KB Output is correct
2 Correct 106 ms 18000 KB Output is correct
3 Correct 95 ms 18000 KB Output is correct
4 Correct 96 ms 18004 KB Output is correct
5 Correct 96 ms 18004 KB Output is correct
6 Correct 99 ms 18252 KB Output is correct
7 Correct 99 ms 18276 KB Output is correct
8 Correct 97 ms 18124 KB Output is correct
9 Correct 108 ms 18260 KB Output is correct
10 Correct 98 ms 18300 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Incorrect 0 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 6488 KB Output is correct
2 Incorrect 0 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 6488 KB Output is correct
2 Incorrect 0 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 73 ms 17744 KB Output isn't correct
2 Halted 0 ms 0 KB -