Submission #199458

#	Time	Username	Problem	Language	Result	Execution time	Memory
199458		TadijaSebez	City (BOI06_city)	C++11	100 / 100	21 ms	5880 KiB

city

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=20050;
const ll inf=8e18;
ll n;
int t,k,c[N];
bool Check(ll d)
{
	ll cnt=0;
	for(int i=1;i<=k;i++)
	{
		ll sz=max((d-c[i])/t,(ll)0);
		if(d>=c[i]) sz++;
		if(sz>0 && n/sz<=sz) return 1;
		cnt+=4*(sz*(sz+1)/2);
	}
	return cnt>=n;
}
const int H=10000050;
ll ptr=0;
ll dp[H];
ll GetSqSum(ll x)
{
	while(ptr<x && ptr<H-1) ptr++,dp[ptr]=dp[ptr-1]+ptr*ptr;
	ll ans=dp[min(x,(ll)H-1)];
	for(ll i=H;i<=x;i++) ans+=i*i;
	return ans;
}
void Prove()
{
	ll sum=0;
	for(ll i=1;i<100;i++)
	{
		sum+=i*i;
		ll tmp=i*i*i+((-11)*i*i+35*i)/2-16;
		if(sum!=tmp)
		{
			printf("! %lld\n",i);
		}
		printf("sum:%lld tmp:%lld\n",sum,tmp);
	}
}
int main()
{
	//Prove();
	scanf("%lld %i %i",&n,&t,&k);
	for(int i=1;i<=k;i++) scanf("%i",&c[i]);
	ll top=inf,bot=0,mid,ans;
	while(top>=bot)
	{
		mid=top+bot>>1;
		//printf("%lld %lld %lld\n",mid,bot,top);
		if(Check(mid)) ans=mid,top=mid-1;
		else bot=mid+1;
	}
	//printf("ans:%lld\n",ans);
	ll sum=0,tot=0;
	for(int i=1;i<=k;i++)
	{
		ll sz=max((ans-c[i])/t,(ll)0);
		if(ans>=c[i]) sz++;
 
		sum+=4*((sz*(sz+1)/2)*(c[i]-t)+t*GetSqSum(sz));
 
		ll cnt=4*(sz*(sz+1)/2);
		tot+=cnt;
	}
	//printf("tot:%lld sum:%lld\n",tot,sum);
	sum-=ans*(tot-n);
	printf("%lld\n",sum);
	return 0;
}

Compilation message (stderr)

city.cpp: In function 'int main()':
city.cpp:52:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid=top+bot>>1;
       ~~~^~~~
city.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %i %i",&n,&t,&k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
city.cpp:48:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=k;i++) scanf("%i",&c[i]);
                        ~~~~~^~~~~~~~~~~~
city.cpp:62:3: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
   if(ans>=c[i]) sz++;
   ^~

• Subtask 1: 100 / 100