글 읽기 - dnc optim 어디가 틀렸는지 모르겠습니다.

(追記) (追記ここまで)

dnc optim 어디가 틀렸는지 모르겠습니다.

13261번 - 탈옥

gs25 2년 전 1

overflow도 안일어나는데 어디가 틀렸는지 도저히 모르겠습니다 ᅲᅲ

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define rep(i, n) for (int i=0; i<n; ++i)
#define rrep(i, n) for (int i=1; i<=n; ++i)
#define ff first 
#define ss second 
using namespace std;
typedef long long ll;
ll dp[820][8010];
ll sum[8010]; 
int L, G; 
ll c[8010]; 
ll ans = 9000000000000LL; 
const ll inf = 9000000000000LL;
void f(int t, int s, int e, int l, int r) {
	// s에서 e 사이 답이 l에서 r 사이 
	if (s > e) return; 
	if (t == 1) {
		int m = s + e >> 1; 
		dp[t][m] = sum[m] * m; 
		f(t, s, m - 1, l, r); 
		f(t, m + 1, e, l, r); 
		return;
	}
	int m = s + e >> 1; 
	ll M = inf, idx=l; 
	for (int i = l; i <= min(r, m); i++) {
		if (M > (sum[m] - sum[i]) * (m - i) + dp[t - 1][i]) {
			M = (sum[m] - sum[i]) * (m - i) + dp[t - 1][i]; 
			idx = i; 
		}
	}
	dp[t][m] = M; 
	f(t, s, m - 1, l, idx); 
	f(t, m + 1, e, idx, r); 
	return;
}
int main(void) {
	//freopen("C:\\Users\\User\\Downloads\\prob3_gold_dec22\19円.in", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> L >> G; 
	rrep(i, L) {
		cin >> c[i]; sum[i] = sum[i - 1] + c[i];
	}
	rrep(i, G) {
		f(i, 1, L, 0, L); 
	}
	cout << dp[G][L]; 
}

댓글을 작성하려면 로그인해야 합니다.

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

dnc optim 어디가 틀렸는지 모르겠습니다.

gs25 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말