QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#59246#2544. Flatland CurrencyHongzy#RE 2ms3780kbC++1006b2022-10-28 18:33:512022-10-28 18:33:54

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-28 18:33:54]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:3780kb
  • [2022-10-28 18:33:51]
  • 提交

answer

#include<bits/stdc++.h>
#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
using namespace std;
typedef long long LL;
const int mxn=100010;
int n;
int a[5][mxn];
LL s[5][mxn];
int calc(int cur,LL m,int l,int r){
	if (m<0) return -1e9;
	if (!cur) return 0;
	if (r-l+1<=50){
		int ret=0;
		int pos=0;
		for (int i=l;i<=r;++i)
			ret=max(ret,calc(cur-1,m-s[cur][i],0,a[cur-1][0])+i*cur),pos=i;
	//	printf("%d %d %d\n",cur,pos,ret);
		return ret;
	}
	int ml=(l+r)/3,mr=(l+r)*2/3;
	int al=calc(cur-1,m-s[cur][ml],0,a[cur-1][0])+ml*cur,
		ar=calc(cur-1,m-s[cur][mr],0,a[cur-1][0])+mr*cur;
	if (al<ar) return calc(cur,m,ml,r);
	else return calc(cur,m,l,mr);
}
int main()
{
	LL m;
	scanf("%d%lld",&n,&m);
	for (int i=1,x;i<=n;++i){
		scanf("%d",&x);
		a[5-x%5][++a[5-x%5][0]]=(x/5+1)*5;
	}
	for (int i=1;i<5;++i){
		sort(a[i]+1,a[i]+a[i][0]+1);
		for (int j=1;j<=a[i][0];++j)
			s[i][j]=s[i][j-1]+a[i][j];
	}
	printf("%d\n",calc(4,m,0,a[4][0])+m%5);
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3740kb

input:

5 57
9 14 31 18 27

output:

8

result:

ok answer is '8'

Test #2:

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

input:

4 50
11 11 11 11

output:

12

result:

ok answer is '12'

Test #3:

score: -100
Runtime Error

input:

100000 89648823509660
921733427 402270498 51157221 585477094 435728758 913951087 580580944 557082810 585086423 837912728 799129405 867009344 751591136 714946046 464999915 256043168 416678301 183246216 569365122 479031618 435168577 31068363 903791719 497652990 960987871 223120213 395437892 112869678 ...

output:


result: