codeforces #600 div2 C - Sweets Eating ( 구간합 전처리, dp )

https://codeforces.com/contest/1253/problem/C

 

굉장히 깔끔하게 떨어져서 마음에 들었던 문제

 

 

day n, 하루에 먹을 수 있는 사탕의 최대 개수 m, sugar concentration a 배열이 주어질때, sugar penalty를 사탕을 먹은 날 * ai라고 한다.

 

이 때 사탕 k개를 먹을 때 sugar penalty를 k = [1,n] 구간에 대해서 모두 구하는 문제이다.

 

제일 먼저 a 배열을 오름차순 정렬해준다. sugar concentration이 작은 것을 먼저 먹는 것이 유리하기 때문이다. 그리고 잘 생각해보면 사탕 i개를 먹을 때 sugar penalty f(i)  = f(i-m) + psum(i) (i>m)  // f(i) = psum(i) (i<=m) 으로 점화식을 세울 수 있다.

 

#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const int MAX = 2e5 + 2;
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
 
	ll n, m; cin >> n >> m;
	ll f[MAX], a[MAX], psum[MAX];
	for (int i = 1; i <= n; i++) cin >> a[i];
	sort(a+1, a + n+1);
	for (int i = 1; i <= n; i++) {
		psum[i] = i == 1 ? a[i] : a[i] + psum[i - 1];
		if(i<=m) f[i] = psum[i];
	}
 
	for (int i = m + 1; i <= n; i++)
		f[i] = f[i - m] + psum[i];
 
	for (int i = 1; i <= n; i++)
		cout << f[i] << " ";
	cout << '\n';
 
	
}