Submission #1341249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1341249		trungcan	Tezina (COCI26_tezina)	C++20	70 / 70	56 ms	1608 KiB

Main

#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);
    if (fopen("Tezina.inp", "r")){
        freopen("Tezina.inp", "r", stdin);
        freopen("Tezina.out", "w", stdout);
    }

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

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

    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 = l - 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";
            ans += (x / i) * 1LL * (s[r] - s[l - 1] + ((r - l + 1) << 1));
            l = r + 1;
        }
    }

    cout << ans;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:14:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         freopen("Tezina.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:15:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         freopen("Tezina.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 17 / 17
• Subtask 2: 19 / 19
• Subtask 3: 34 / 34