답안 #1017321

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1017321	2024-07-09T07:23:20 Z	nathan4690	Feast (NOI19_feast)	C++17	63 / 100	76 ms	15028 KB

feast

// 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],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];
    L = 0; R = 1e13;
    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 + res.second * 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
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	11612 KB	Output is correct
2	Correct	49 ms	11868 KB	Output is correct
3	Correct	58 ms	13928 KB	Output is correct
4	Correct	56 ms	12100 KB	Output is correct
5	Correct	45 ms	11868 KB	Output is correct
6	Correct	45 ms	11612 KB	Output is correct
7	Correct	45 ms	14680 KB	Output is correct
8	Correct	45 ms	12008 KB	Output is correct
9	Correct	49 ms	11868 KB	Output is correct
10	Correct	45 ms	13656 KB	Output is correct

Subtask #2
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	37 ms	13656 KB	Output is correct
2	Correct	54 ms	13916 KB	Output is correct
3	Correct	38 ms	11864 KB	Output is correct
4	Incorrect	38 ms	11868 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #3
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	65 ms	11840 KB	Output is correct
2	Correct	64 ms	12120 KB	Output is correct
3	Correct	66 ms	12372 KB	Output is correct
4	Correct	62 ms	12244 KB	Output is correct
5	Correct	62 ms	12364 KB	Output is correct
6	Correct	67 ms	12376 KB	Output is correct
7	Correct	68 ms	13912 KB	Output is correct
8	Correct	76 ms	13652 KB	Output is correct
9	Correct	66 ms	15028 KB	Output is correct
10	Correct	69 ms	13896 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	0 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	0 ms	2396 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct

Subtask #5
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	0 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	0 ms	2396 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	4696 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	4444 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	4444 KB	Output is correct
16	Correct	1 ms	2396 KB	Output is correct
17	Correct	1 ms	4440 KB	Output is correct
18	Correct	1 ms	4444 KB	Output is correct
19	Correct	1 ms	2396 KB	Output is correct
20	Correct	1 ms	4444 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	4444 KB	Output is correct
2	Correct	1 ms	2396 KB	Output is correct
3	Correct	0 ms	2396 KB	Output is correct
4	Correct	1 ms	2396 KB	Output is correct
5	Correct	1 ms	2396 KB	Output is correct
6	Correct	0 ms	2396 KB	Output is correct
7	Correct	1 ms	2396 KB	Output is correct
8	Correct	0 ms	2396 KB	Output is correct
9	Correct	1 ms	4444 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	1 ms	4696 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	1 ms	4444 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	1 ms	4444 KB	Output is correct
16	Correct	1 ms	2396 KB	Output is correct
17	Correct	1 ms	4440 KB	Output is correct
18	Correct	1 ms	4444 KB	Output is correct
19	Correct	1 ms	2396 KB	Output is correct
20	Correct	1 ms	4444 KB	Output is correct
21	Correct	1 ms	348 KB	Output is correct
22	Correct	1 ms	4444 KB	Output is correct
23	Correct	1 ms	2396 KB	Output is correct
24	Correct	1 ms	348 KB	Output is correct
25	Correct	1 ms	348 KB	Output is correct
26	Correct	2 ms	2396 KB	Output is correct
27	Correct	1 ms	352 KB	Output is correct
28	Correct	1 ms	356 KB	Output is correct
29	Correct	1 ms	2400 KB	Output is correct
30	Correct	1 ms	360 KB	Output is correct

Subtask #7
0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	45 ms	11612 KB	Output is correct
2	Correct	49 ms	11868 KB	Output is correct
3	Correct	58 ms	13928 KB	Output is correct
4	Correct	56 ms	12100 KB	Output is correct
5	Correct	45 ms	11868 KB	Output is correct
6	Correct	45 ms	11612 KB	Output is correct
7	Correct	45 ms	14680 KB	Output is correct
8	Correct	45 ms	12008 KB	Output is correct
9	Correct	49 ms	11868 KB	Output is correct
10	Correct	45 ms	13656 KB	Output is correct
11	Correct	37 ms	13656 KB	Output is correct
12	Correct	54 ms	13916 KB	Output is correct
13	Correct	38 ms	11864 KB	Output is correct
14	Incorrect	38 ms	11868 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

답안 #1017321

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 0 / 8.0

Subtask #3 18.0 / 18.0

Subtask #4 10.0 / 10.0

Subtask #5 11.0 / 11.0

Subtask #6 20.0 / 20.0

Subtask #7 0 / 29.0

Subtask #1
4.0 / 4.0

Subtask #2
0 / 8.0

Subtask #3
18.0 / 18.0

Subtask #4
10.0 / 10.0

Subtask #5
11.0 / 11.0

Subtask #6
20.0 / 20.0

Subtask #7
0 / 29.0