Submission #1350320

#	Time	Username	Problem	Language	Result	Execution time	Memory
1350320		rexdino	Tezina (COCI26_tezina)	C++20	70 / 70	61 ms	2024 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
#define FOR(i, a, b) for(int i=(a); i<=(b); ++i)
#define REP(i, a, b) for(int i=(a); i>=(b); --i)
#define BIT(x, i) (((x) >> (i)) & 1)
#define MASK(i) (1LL << (i))
#define sz(v) (int)(v).size()
#define ALL(v) (v).begin(),(v).end()
using namespace std;
    
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template <class T1, class T2> bool ckmax(T1 &a, T2 b){ if (a < b) {a = b; return 1;}return 0;}
template <class T1, class T2> bool ckmin(T1 &a, T2 b){ if (a > b) {a = b; return 1;}return 0;}

const int N = 1e6 + 5;
const int mod = 1e9 + 7;
const int base = 311;
const ll INF = 1e18;
const int MAX = 100000000;
// Author: rexdino
int n, k;
int a[N], b[N];
ll pre[N];

void solve(){
	cin >> n >> k;
	FOR(i, 1, n) cin >> a[i];

	sort(a + 1, a + n + 1);
	FOR(i, 1, n) b[i] = a[i] + 2, pre[i] = pre[i - 1] + b[i];
	ll sum = 0;

	int j = 1;
	int p = 1;
	FOR(i, 1, k){
		while(p <= n && 1ll * (a[p] / i) * (b[p]) <= MAX) p++;
		sum += 1ll * (n - p + 1) * MAX;
		while(j < n && a[j] < i) j++;
		int cur = j;
		

		// cerr << i << ": " << j << " " << p << " " << "\n";

		
		while(cur <= n && cur < p){
			int x = a[cur] / i;
			int l = cur, r = n, pos = -1;
			while(l <= r){
				int mid = (l + r) >> 1;
				if (a[mid] / i == x){
					pos = mid;
					l = mid + 1;
				} else r = mid - 1;
			}

			sum += (pre[min(pos, p - 1)] - pre[cur - 1]) * x;
			// cerr << i << ": " << cur << " " << pos << " " << "\n";
			cur = pos + 1;
		}
	}

	cout << sum;
}

signed main(){
    #define NAME "main"
    if (fopen(NAME".inp", "r")){
        freopen(NAME".inp", "r", stdin);
        freopen(NAME".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int t = 1;
    // cin >> t;
    while(t--) solve();

    // cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s\n";
    return 0;
}

Compilation message (stderr)

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

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