Submission #226635

#	Time	Username	Problem	Language	Result	Execution time	Memory
226635		MKopchev	City (BOI06_city)	C++14	100 / 100	11 ms	384 KiB

city

#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<workers)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)

city.cpp: In function 'int main()':
city.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld%i",&workers,&t,&n);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
city.cpp:41:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1;i<=n;i++)scanf("%i",&inp[i]);
                          ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 100 / 100