Submission #549467

#	Time	Username	Problem	Language	Result	Execution time	Memory
549467		sealnot123	City (BOI06_city)	C++14	100 / 100	7 ms	588 KiB

city

#include<bits/stdc++.h>
using namespace std;

const int K = 20005;
 
long long cost[K];
 
int main(){
    long long n, t, k;
    assert(3 == scanf("%lld %lld %lld",&n,&t,&k));
    assert(1 <= n && n <= 1e12);
    assert(1 <= t && t <= 5e5);
    assert(1 <= k && k <= 2e4);
    for(int i=1; i<=k; ++i){
        assert(1 == scanf(" %lld",&cost[i]));
    }
    long long l = cost[1], r = 1e12;
    while(l < r){
        long long m = (l+r)/2;
        long long sum = 0;
        for(int i=1; i<=k; ++i){
            if(m < cost[i]) break;
            long long number = (m-cost[i])/t+1;
            if(number >= 1000000){
                sum = n;
                break;
            }
            sum += number*(number+1)*2;
        }
        if(sum >= n) r = m;
        else l = m+1;
    }
    long long ans = 0;
    long long sum = 0;
    for(int i=1; i<=k; ++i){
        if(l-1 < cost[i]) break;
        long long number = (l-1-cost[i])/t+1;
        ans += cost[i]*number*(number+1)*2;
        ans += (number*(number-1)*2)*t;
        ans += ((number-1)*(number)*(2*number-1)/6)*4*t;
        sum += number*(number+1)*2;
    }
    ans += (n-sum)*l;
    assert(sum <= n);
    printf("%lld",ans);
    return 0;
}

• Subtask 1: 100 / 100