UOJ 做题记录

其实我这么弱> >根本不会做题呢> >

#21. 【UR #1】缩进优化

其实想想还是一道非常丝播的题目呢> >

直接对于每个缩进长度统计一遍就好了> >

只需要统计能缩出多少tab,而这个显然可以前缀和扫扫罗干罗干就好了> >

无爱地刷rank> >

#include <cstdio>

#define fon(i,s)    for(ul i=0;i<s; ++i)

#define foxe(i,f,t) for(ul i=f;i<=t;++i)

#define qbs 10000100

#define maxn 1000010

typedef long long ll;

typedef unsigned long long ull;

typedef int il;

typedef unsigned int ul;

inline char getc(){ static char buf[qbs];static ul q=qbs; if(qbs==q) fread(buf,qbs,1,stdin),q=0; return buf[q++]; }

inline void readuint(ul& a){ a=0; char p=getc(); while(p>'9' || p<'0') p=getc(); while(p<='9'&&p>='0') a=a*10+p-'0',p=getc(); }

inline void readuint(ull& a){ a=0; char p=getc(); while(p>'9' || p<'0') p=getc(); while(p<='9'&&p>='0') a=a*10+p-'0',p=getc(); }

inline void putc(char p,bool e=0){ static char buf[qbs+10];static ul q=0; if(~p) buf[q++]=p; if((e&&q) || qbs==q) fwrite(buf,q,1,stdout),q=0; }

inline void printuint(ul a){if(a>=10) printuint(a/10); putc(a%10+'0');}

inline void printuint(ull a){if(a>=10) printuint(a/10); putc(a%10+'0');}

ul now,c[maxn],n,ma;

ull ans,tot;

int main(){

	readuint(n);

	fon(i,n) readuint(now),tot+=now,ans+=now>>1,++c[now],ma=now>ma?now:ma;

	foxe(i,1,ma) c[i]+=c[i-1];

	foxe(i,3,ma){

		register ul nowx=0;

		register ull nowans=0;

		now=i-1;

		while(now+i-1<ma) nowans+=(ull)(++nowx)*(c[now+i]-c[now]),now+=i;

		nowans+=(ull)(++nowx)*(c[ma]-c[now]);

		nowans*=i-1;

		ans=nowans>ans?nowans:ans;

	}

	ans=tot-ans;

	printuint(ans);

	putc('\n',1);

	return 0;

}