QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#422005#8281. Pangu and Stonesucup-team1069#TL 25ms13456kbC++231016b2024-05-26 16:20:432024-05-26 16:20:43

Judging History

你现在查看的是最新测评结果

  • [2024-05-26 16:20:43]
  • 评测
  • 测评结果:TL
  • 用时:25ms
  • 内存:13456kb
  • [2024-05-26 16:20:43]
  • 提交

answer

#include <algorithm>
#include <iostream>
#include <vector>
#include <set>
#include <map>

using namespace std;
using ll = long long;
const int N = 105;
const ll INF = 1e18 + 123;

int a[N], p[N], u[N][N][N]; 
ll dp[N][N][N];

int sum(int l, int r) {
	return p[r] - p[l - 1];
}

	int n, L, R;
ll solve(int l, int r, int x) {
	if (u[l][r][x]) return dp[l][r][x];
	if (r - l + 1 == x) return 0;
	u[l][r][x] = 1;
	dp[l][r][x] = INF;
	if (x == 1) {
		for (int y = L ; y <= R ; ++ y) {
			dp[l][r][x] = min(dp[l][r][x], solve(l, r, y) + sum(l, r));
		}
	} else {
		for (int k = l ; k < r ; ++ k) {
			for (int y = 1 ; y < x ; ++ y) {
				dp[l][r][x] = min(dp[l][r][x], solve(l, k, y) + solve(k + 1, r, x - y));
			}
		}
	}
	return dp[l][r][x];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> L >> R;
	for (int i = 1 ; i <= n ; ++ i) {
		cin >> a[i];
		p[i] = p[i - 1] + a[i];
	}
	ll ans = solve(1, n, 1);
	if (ans >= INF) ans = 0;
	cout << ans;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3544kb

input:

3 2 2
1 2 3

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

3 2 3
1 2 3

output:

6

result:

ok 1 number(s): "6"

Test #3:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

4 3 3
1 2 3 4

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: 0
Accepted
time: 25ms
memory: 13456kb

input:

100 4 7
570 608 194 26 243 470 418 119 1000 936 440 302 797 155 676 283 869 60 959 793 158 397 808 656 379 316 485 854 753 280 543 435 756 822 106 561 402 347 99 739 8 682 834 549 812 32 338 765 699 575 575 785 171 504 335 113 284 612 276 518 835 677 865 900 687 48 859 179 343 318 626 812 523 11 400...

output:

120446

result:

ok 1 number(s): "120446"

Test #5:

score: -100
Time Limit Exceeded

input:

100 35 76
322 199 744 64 89 251 274 508 722 852 273 341 916 231 495 767 852 260 717 813 346 694 113 796 571 754 603 660 271 915 819 330 116 925 301 1 83 769 79 251 833 761 954 899 65 245 263 444 767 780 340 599 952 447 479 137 425 58 835 963 749 164 513 479 179 18 624 975 175 135 767 607 760 718 859...

output:


result: