oj.uz

Submission #199458

# Submission time Handle Problem Language Result Execution time Memory
199458 2020-02-01T12:55:07 Z TadijaSebez City (BOI06_city) C++11
100 / 100
 21 ms 5880 KB 
#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

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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 9 ms 5880 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 7 ms 376 KB Output is correct
5 Correct 5 ms 628 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 21 ms 668 KB Output is correct
8 Correct 9 ms 376 KB Output is correct
9 Correct 6 ms 376 KB Output is correct
10 Correct 5 ms 376 KB Output is correct