UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#212796#3830. Dhuangyuhang10346ms2004kbC++11592b2024-10-20 11:22:302024-10-20 12:44:24

answer

#include<bits/stdc++.h>
using namespace std;
int n,a[100000+5],m,k;
int b[100000+5]; 
bool check(int x)
{
	int l=1;
	for(int i=1;i<=m;i++)
	{
		for(int j=l;j<=min(l+x,n);j++)
			b[j]+=pow(x-j+l,k);
		while(b[l]>=a[l])
		{
			l++;
			if(l>n)
				return true;
		}	
	}
	return false;
}
int main()
{
	scanf("%d %d %d",&n,&m,&k);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	int l=1,r=100000000,ans=n;
	while(l<=r)
	{
		int mid=(l+r)/2;
		memset(b,0,sizeof(b));
		if(check(mid))
		{
			ans=mid;
			r=mid-1;
		}
		else
			l=mid+1;
	}
	cout<<ans;
	return 0;
}

Details

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 1612kb

input:

5 2 0
1 4 2 4 2

output:

5

result:

wrong answer 1st numbers differ - expected: '-1', found: '5'

Subtask #2:

score: 0
Wrong Answer

Test #6:

score: 0
Wrong Answer
time: 97ms
memory: 2004kb

input:

100000 3 0
55571 62024 7086 67802 12577 42004 72323 45260 40287 39641 64847 42428 20318 80027 1675 1...

output:

100000

result:

wrong answer 1st numbers differ - expected: '-1', found: '100000'

Subtask #3:

score: 10
Accepted

Test #11:

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

input:

1000 1 1
993 705 891 648 406 9 983 913 370 408 607 47 85 199 767 448 723 255 253 302 754 135 641 726...

output:

1991

result:

ok 1 number(s): "1991"

Test #12:

score: 0
Accepted
time: 4ms
memory: 1608kb

input:

1000 529 1
321 273 256 430 151 307 590 682 756 267 100 169 963 681 121 604 781 631 573 463 50 114 36...

output:

56

result:

ok 1 number(s): "56"

Test #13:

score: 0
Accepted
time: 2ms
memory: 1604kb

input:

1000 4 1
375 583 285 303 117 912 795 824 832 856 252 265 320 724 508 462 869 18 619 17 43 925 50 489...

output:

909

result:

ok 1 number(s): "909"

Test #14:

score: 0
Accepted
time: 3ms
memory: 1604kb

input:

1000 460 1
989 778 924 926 203 490 224 784 68 157 722 281 524 925 905 204 934 987 87 455 400 479 739...

output:

61

result:

ok 1 number(s): "61"

Test #15:

score: 0
Accepted
time: 3ms
memory: 1604kb

input:

1000 931 1
868 242 1000 627 893 936 831 449 837 763 124 640 61 280 52 954 663 172 902 934 357 604 58...

output:

42

result:

ok 1 number(s): "42"

Subtask #4:

score: 0
Time Limit Exceeded

Test #16:

score: 20
Accepted
time: 55ms
memory: 1988kb

input:

100000 4 1
10156 27005 39480 62054 63362 28009 65831 14391 93683 7991 17027 26313 1403 15929 30567 1...

output:

91939

result:

ok 1 number(s): "91939"

Test #17:

score: 0
Accepted
time: 57ms
memory: 1992kb

input:

100000 6 1
5263 29513 22737 44468 6684 15652 39566 10152 27517 35937 12377 87830 95911 99259 81409 7...

output:

70623

result:

ok 1 number(s): "70623"

Test #18:

score: 0
Accepted
time: 80ms
memory: 1992kb

input:

100000 10 1
68973 33483 89814 68747 21876 81790 94902 4071 20192 97844 88754 71887 49738 13942 70940...

output:

52981

result:

ok 1 number(s): "52981"

Test #19:

score: -20
Time Limit Exceeded

input:

100000 95377 1
29813 76527 66386 77732 54103 9457 23818 16306 93964 97693 94674 18798 6597 30534 681...

output:


result:


Subtask #5:

score: 0
Wrong Answer

Test #21:

score: 0
Wrong Answer
time: 45ms
memory: 1612kb

input:

1000 169 2
853 394 985 195 859 84 227 50 641 365 409 407 845 112 7 582 920 965 590 869 550 781 40 44...

output:

1000

result:

wrong answer 1st numbers differ - expected: '26', found: '1000'

Subtask #6:

score: 0
Time Limit Exceeded

Test #26:

score: 0
Time Limit Exceeded

input:

100000 31778 2
9482 16920 65207 41338 19891 97532 56865 946 56851 5908 19270 8065 53369 97241 69805 ...

output:


result: