답안 #1017312

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1017312	2024-07-09T07:21:45 Z	nathan4690	Feast (NOI19_feast)	C++17	63 / 100	86 ms	14972 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 = 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 + 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	51 ms	14680 KB	Output is correct
2	Correct	52 ms	14928 KB	Output is correct
3	Correct	53 ms	14940 KB	Output is correct
4	Correct	57 ms	14972 KB	Output is correct
5	Correct	56 ms	14804 KB	Output is correct
6	Correct	51 ms	14684 KB	Output is correct
7	Correct	52 ms	14680 KB	Output is correct
8	Correct	52 ms	14792 KB	Output is correct
9	Correct	51 ms	14672 KB	Output is correct
10	Correct	53 ms	14680 KB	Output is correct

Subtask #2
0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	44 ms	14752 KB	Output is correct
2	Correct	48 ms	14936 KB	Output is correct
3	Correct	47 ms	14736 KB	Output is correct
4	Incorrect	47 ms	14896 KB	Output isn't correct
5	Halted	0 ms	0 KB	-

Subtask #3
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	77 ms	14928 KB	Output is correct
2	Correct	86 ms	14928 KB	Output is correct
3	Correct	78 ms	14672 KB	Output is correct
4	Correct	81 ms	14672 KB	Output is correct
5	Correct	76 ms	14936 KB	Output is correct
6	Correct	78 ms	14972 KB	Output is correct
7	Correct	81 ms	14940 KB	Output is correct
8	Correct	75 ms	14684 KB	Output is correct
9	Correct	78 ms	14804 KB	Output is correct
10	Correct	78 ms	14940 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	4444 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	1 ms	2396 KB	Output is correct
7	Correct	0 ms	2396 KB	Output is correct
8	Correct	0 ms	2396 KB	Output is correct
9	Correct	0 ms	2512 KB	Output is correct
10	Correct	0 ms	2396 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	4444 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	1 ms	2396 KB	Output is correct
7	Correct	0 ms	2396 KB	Output is correct
8	Correct	0 ms	2396 KB	Output is correct
9	Correct	0 ms	2512 KB	Output is correct
10	Correct	0 ms	2396 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	0 ms	2396 KB	Output is correct
13	Correct	1 ms	4440 KB	Output is correct
14	Correct	1 ms	4444 KB	Output is correct
15	Correct	1 ms	2396 KB	Output is correct
16	Correct	1 ms	4440 KB	Output is correct
17	Correct	1 ms	2392 KB	Output is correct
18	Correct	1 ms	2408 KB	Output is correct
19	Correct	0 ms	2396 KB	Output is correct
20	Correct	1 ms	4696 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	4444 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	1 ms	2396 KB	Output is correct
7	Correct	0 ms	2396 KB	Output is correct
8	Correct	0 ms	2396 KB	Output is correct
9	Correct	0 ms	2512 KB	Output is correct
10	Correct	0 ms	2396 KB	Output is correct
11	Correct	1 ms	2396 KB	Output is correct
12	Correct	0 ms	2396 KB	Output is correct
13	Correct	1 ms	4440 KB	Output is correct
14	Correct	1 ms	4444 KB	Output is correct
15	Correct	1 ms	2396 KB	Output is correct
16	Correct	1 ms	4440 KB	Output is correct
17	Correct	1 ms	2392 KB	Output is correct
18	Correct	1 ms	2408 KB	Output is correct
19	Correct	0 ms	2396 KB	Output is correct
20	Correct	1 ms	4696 KB	Output is correct
21	Correct	1 ms	2392 KB	Output is correct
22	Correct	1 ms	2396 KB	Output is correct
23	Correct	1 ms	2396 KB	Output is correct
24	Correct	1 ms	4444 KB	Output is correct
25	Correct	1 ms	2396 KB	Output is correct
26	Correct	1 ms	4440 KB	Output is correct
27	Correct	1 ms	4444 KB	Output is correct
28	Correct	1 ms	4604 KB	Output is correct
29	Correct	1 ms	2460 KB	Output is correct
30	Correct	1 ms	4440 KB	Output is correct

Subtask #7
0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	51 ms	14680 KB	Output is correct
2	Correct	52 ms	14928 KB	Output is correct
3	Correct	53 ms	14940 KB	Output is correct
4	Correct	57 ms	14972 KB	Output is correct
5	Correct	56 ms	14804 KB	Output is correct
6	Correct	51 ms	14684 KB	Output is correct
7	Correct	52 ms	14680 KB	Output is correct
8	Correct	52 ms	14792 KB	Output is correct
9	Correct	51 ms	14672 KB	Output is correct
10	Correct	53 ms	14680 KB	Output is correct
11	Correct	44 ms	14752 KB	Output is correct
12	Correct	48 ms	14936 KB	Output is correct
13	Correct	47 ms	14736 KB	Output is correct
14	Incorrect	47 ms	14896 KB	Output isn't correct
15	Halted	0 ms	0 KB	-

답안 #1017312

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