제출 #1336673

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1336673		maicon	Feast (NOI19_feast)	C++20	100 / 100	91 ms	9804 KiB

feast

#include <bits/stdc++.h>

#define INF -1000000000

using namespace std;

/*
Some important points to notice in this problem... the more subarrays I choose, the more benefit I get.
But the more I choose, the less benefit is added, so it forms a concave chart.
Based on this, I can use the Alien trick to solve it
*/

int N, K;
long long int a[300001];
long long int dp[300001][2]; //dp[i][x] the best sum I get until index i using the index i in a subarray, or not using it, x=0 not using it, x=1 using it
int sub[300001][2]; //sub[i][x] number of subarrays I'm using until index i, when x=0 means i is not in a subarray, and x=1 indicates it is

void solve(long long int p) { //p is the penalty I'll use every time I create a new subarray
	dp[0][0] = 0; //I don't add the first item to a subarray, so benefit is 0
	sub[0][0] = 0; //I don't have any subarray
	
	dp[0][1] = a[0] -p; //I add the first item to a subarray, so benefit is a[0] -p (the penalty of creating this array)
	sub[0][1] = 1; //I have ONE subarray so far

	for (int i = 1; i < N; i++) {

		/*Let's say we don't want to take index i for the current subarray, so our x = 0
		So, the best benefit is what we had better from bringing item i-1 or not bringing i-1
		*/
		if (dp[i-1][0] > dp[i-1][1] || dp[i-1][0] == dp[i-1][1] && sub[i-1][0] > sub[i-1][1]) {
			dp[i][0] = dp[i-1][0];
			sub[i][0] = sub[i-1][0];
		} else {
			dp[i][0] = dp[i-1][1];
			sub[i][0] = sub[i-1][1];
		}

		/*Other possibility is we want to take index i for the current subarray, so we need to check if we are creating a new subarray or not
		If we create a new subarray (when i-1 is not in the subarray), then we need to add a penalty for creating this subarray
		If we are just extending a previous subarray, there's no penalty
		*/
		if (dp[i-1][0] + a[i] -p > dp[i-1][1] + a[i] || dp[i-1][0] + a[i] -p == dp[i-1][1] + a[i] && sub[i-1][0]+1 > sub[i-1][1]) {
			dp[i][1] = dp[i-1][0] + a[i] -p; //Adding item i to a new subarray
			sub[i][1] = sub[i-1][0]+1; //New subarray created
		} else {
			dp[i][1] = dp[i-1][1] + a[i]; //Adding item i to the current subarray
			sub[i][1] = sub[i-1][1]; //No new subarray created
		}
	}
}

long long int binarySearchPenalty() {
	long long int low = 0;
	long long int high = 300000*1000000001LL;
	long long int best;
	int subarrays;
	while (low < high) {
		long long int mid = (low + high) / 2;
		solve(mid);

		if (dp[N-1][0] > dp[N-1][1]) {
			best = dp[N-1][0];
			subarrays = sub[N-1][0];
		} else {
			best = dp[N-1][1];
			subarrays = sub[N-1][1];
		}

		if (subarrays > K) { //If I used more than K subarrays, then I need to increase the penalty of creating new arrays
			low = mid + 1;
		} else { //If I didn't use more than K subarrays, I can decrease the penalty of creating subarrays
			high = mid;
		}
	}

	//At some point, low and high would be the same, so I can use this penalty to find the answer
	solve(low);

	if (dp[N-1][0] > dp[N-1][1]) {
		best = dp[N-1][0];
		subarrays = sub[N-1][0];
	} else {
		best = dp[N-1][1];
		subarrays = sub[N-1][1];
	}

	return best + low * K; //As the best in the dp consideres the penalties applied, then I need to remember to remove the penalties
}

int main() {

	scanf("%d %d ", &N, &K);

	for(int i = 0; i < N; i++) {
		scanf("%lld ", &a[i]);
	}

	printf("%lld\n", binarySearchPenalty());

	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

feast.cpp: In function 'int main()':
feast.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         scanf("%d %d ", &N, &K);
      |         ~~~~~^~~~~~~~~~~~~~~~~~
feast.cpp:95:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |                 scanf("%lld ", &a[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 11 / 11
• Subtask 6: 20 / 20
• Subtask 7: 29 / 29