Submission #1341227

#TimeUsernameProblemLanguageResultExecution timeMemory
1341227trungcanTezina (COCI26_tezina)C++20
0 / 70
1 ms344 KiB
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;
const int LIM = 1e8;

int n, k, a[N];
long long s[N], ans;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> k;
    for (int i = 1; i <= n; ++i) cin >> a[i], s[i] = s[i - 1] + a[i];

    sort(a + 1, a + n + 1);

    int j = n, l = 1;
    for (int i = 1; i <= k; ++i){
        while (j && (a[j] / i) * 1LL * (a[j] + 2) > LIM)
            --j;
        if (a[j] < i) break;

        while (a[l] < i) ++l;
        for (int x = i; x <= a[j]; x += i){
            int L = l, R = j, r = -1;
            while (L <= R){
                int mid = L + ((R - L) >> 1);
                if (a[mid] < x + i){
                    r = mid;
                    L = mid + 1;
                } else
                    R = mid - 1;
            }

//            cout << i << " " << x / i << "\t" << l << " " << r << "\t" << (x / i) * (s[r] - s[l - 1] + ((r - l + 1) << 1)) << "\n";
            if (l <= r)
                ans += (x / i) * 1LL * (s[r] - s[l - 1] + ((r - l + 1) << 1));
            l = max(1, r + 1);
        }
    }

    cout << ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...