QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#312381#8159. 刷野 IIIC1942huangjiaxu100 ✓12ms35344kbC++14710b2024-01-23 20:52:162024-01-23 20:52:17

Judging History

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

  • [2024-01-23 20:52:17]
  • 评测
  • 测评结果:100
  • 用时:12ms
  • 内存:35344kb
  • [2024-01-23 20:52:16]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=2005;
typedef long long ll;
int n,m,a[N],st[N],tp;
ll f[N][N],ans=1e18;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	sort(a+1,a+n+1,greater<int>());
	memset(f,0x3f,sizeof(f));
	f[0][0]=0;
	for(int i=1;i<=m;++i){
		st[tp=1]=i-1;
		for(int j=i;j<=n;++j){
			while(tp>1&&f[i-1][st[tp]]-f[i-1][st[tp-1]]>=1ll*a[j]*(st[tp]-st[tp-1]))--tp;
			f[i][j]=f[i-1][st[tp]]+1ll*a[j]*(j-st[tp]);
			while(tp>1&&(f[i-1][j]-f[i-1][st[tp-1]])*(st[tp]-st[tp-1])<=(f[i-1][st[tp]]-f[i-1][st[tp-1]])*(j-st[tp-1]))--tp;
			st[++tp]=j;
		}
	}
	for(int i=1;i<=n;++i)ans=min(ans,f[m][i]);
	printf("%lld\n",ans);
	return 0;
}

詳細信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 35280kb

input:

5 1
2 4 4 4 10000

output:

8

result:

ok 1 number(s): "8"

Test #2:

score: 10
Accepted
time: 0ms
memory: 35288kb

input:

2000 234
62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 62685072 626...

output:

14668306848

result:

ok 1 number(s): "14668306848"

Test #3:

score: 10
Accepted
time: 6ms
memory: 35200kb

input:

2000 345
63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 63271935 632...

output:

21828817575

result:

ok 1 number(s): "21828817575"

Test #4:

score: 10
Accepted
time: 0ms
memory: 35276kb

input:

500 224
66294782 55099630 8718405 48124447 68016284 2367446 17205043 91335098 87097282 9100752 6491957 48720958 53455828 89125408 25719864 11848122 52244731 69201759 26437312 37777762 82726659 78911899 69681329 16885773 68848203 13447237 57046423 92381205 27704872 43706722 19555119 71696875 62061650...

output:

14853863285

result:

ok 1 number(s): "14853863285"

Test #5:

score: 10
Accepted
time: 3ms
memory: 35344kb

input:

500 10
3 3 3 3 3 3 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6...

output:

66

result:

ok 1 number(s): "66"

Test #6:

score: 10
Accepted
time: 3ms
memory: 35280kb

input:

500 10
2 2 2 2 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4...

output:

44

result:

ok 1 number(s): "44"

Test #7:

score: 10
Accepted
time: 12ms
memory: 35196kb

input:

2000 1843
84604572 4716533 6698574 12319038 50671893 13957944 17671601 11350657 96572857 14254508 17344235 80803829 37343616 11656442 85514739 36882120 79160084 11106020 59949111 94099020 26763090 21776877 72218280 42984613 11032095 62624651 24012793 88044654 23027457 486188 66523748 69020965 681051...

output:

91618811350

result:

ok 1 number(s): "91618811350"

Test #8:

score: 10
Accepted
time: 4ms
memory: 35160kb

input:

2000 1024
70230354 98819891 62478100 10135081 33978136 34810340 16477407 19297418 95495214 20997741 28005411 38336888 84993260 63554536 13453707 51666781 16077717 62825857 43152651 66594616 5742411 14693737 83025479 38612236 54542117 38309252 2507161 7782767 48540912 70109835 81187790 33517835 21329...

output:

67590494017

result:

ok 1 number(s): "67590494017"

Test #9:

score: 10
Accepted
time: 5ms
memory: 35196kb

input:

1483 344
86 20 81 16 69 21 53 99 88 20 1 21 41 12 99 35 93 67 95 11 45 17 96 82 41 41 1 81 1 81 1 47 23 45 33 41 41 76 57 71 50 1 61 22 72 81 5 46 13 73 73 91 97 46 1 70 25 77 85 98 29 71 25 21 96 53 73 95 1 55 99 53 81 57 41 6 5 61 89 88 41 71 1 21 46 88 31 41 69 69 59 1 13 46 77 26 45 61 81 21 559...

output:

3185611

result:

ok 1 number(s): "3185611"

Test #10:

score: 10
Accepted
time: 0ms
memory: 35292kb

input:

1241 19
28 11 93 59 17 11 27 16 55 37 91 41 8 39 5 35 53 90 11 9 79 73 15 41 1 37 13 61 53 71 29 25 92 97 9 9 49 27 9 1 21 65 86 37 30 49 41 21 91 93 88 69 69 45 84 37 7 1 11 12 29 20 98 89 22 72 51 77 59 59 69 29 97 63 3 16 33 80 9 11 57 63 91 93 32 11 22 85 79 91 49 11 81 65 17 53 81 31 27 49 8841...

output:

13574

result:

ok 1 number(s): "13574"