oj.uz

Submission #549467

# Submission time Handle Problem Language Result Execution time Memory
549467 2022-04-15T21:14:09 Z sealnot123 City (BOI06_city) C++14
100 / 100
 7 ms 588 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 7 ms 588 KB Output is correct
8 Correct 2 ms 316 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 308 KB Output is correct