# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
226633 | MKopchev | City (BOI06_city) | C++14 | 8 ms | 384 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int nmax=2e4+42;
long long workers;
long long t;
int n;
int inp[nmax];
pair<long long/*number of workers*/,long long/*total time*/> eval(long long most)
{
long long number=0,total=0;
for(int i=1;i<=n;i++)
if(inp[i]<=most)
{
long long d_max=(most-inp[i])/t;
long long workers_now=2*(d_max+1)*(d_max+2);
long long time_now=workers_now*inp[i]+t*(d_max*(d_max+1)*(2*d_max+1)/3*2+2*d_max*(d_max+1));
number+=workers_now;
total+=time_now;
if(number>=workers)return {number,total};
}
//cout<<most<<" -> "<<number<<" "<<total<<endl;
return {number,total};
}
int main()
{
scanf("%lld%lld%i",&workers,&t,&n);
for(int i=1;i<=n;i++)scanf("%i",&inp[i]);
long long ok=1;
while(eval(ok).first<n)ok=ok*2+1;
long long not_ok=0;
while(ok-not_ok>1)
{
long long av=(ok+not_ok)/2;
if(eval(av).first<workers)not_ok=av;
else ok=av;
}
pair<long long/*number of workers*/,long long/*total time*/> help=eval(not_ok);
long long output=help.second+(workers-help.first)*ok;
printf("%lld\n",output);
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |