oj.uz

Submission #226635

# Submission time Handle Problem Language Result Execution time Memory
226635 2020-04-24T15:38:09 Z MKopchev City (BOI06_city) C++14
100 / 100
 11 ms 384 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 6 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 256 KB Output is correct
7 Correct 11 ms 384 KB Output is correct
8 Correct 6 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct