Submission #1341234

#TimeUsernameProblemLanguageResultExecution timeMemory
1341234trungcanTezina (COCI26_tezina)C++20
0 / 70
34 ms1608 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 = 1, p = 1;
    for (int i = 1; i <= k; ++i){
        while (j <= n && (a[j] / i) * 1LL * (a[j] + 2) <= LIM)
            ++j;

        ans += (n - j + 1) * 1LL * LIM;

        while (a[p] < i) ++p; //cout << "\t" << l << "\n";
        int l = p;
        for (int x = i; x <= a[j - 1]; x += i){
            int L = l, R = j - 1, 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...