Submission #36446998

---

Source Code Expand

#include "bits/stdc++.h"
using namespace std;
#define int long long
#ifdef LOCAL
#define watch(x) cout << #x << ':' << x << ' ';
#else
#define watch(x) 0
#endif
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define mod 1000000007
#define pb push_back
#define ff first
#define ss second
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
typedef long long ll;
typedef unsigned long long ull;
typedef long double lld;

void init() {
#ifdef LOCAL
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("err.txt", "w", stderr);
#endif
}

void solve() {}

int32_t main()
{
	IOS;
	init();
	int t = 1;
	// cin >> t;

	while (t--) {

		int n, m, sum = 0;
		cin >> n >> m;

		vector<int> v(n);
		map<int, int> mp;
		for (int i = 0; i < n; i++) {
			cin >> v[i];
			sum += v[i];
			mp[v[i]]++;
		}

		int ans = 1e15;
		// sort(all(v));
		// for (int i : v) cout << i << " ";
		// cout << "\n";
		// watch(sum);
		set<int> st;

		int res = 0, last = prev(mp.end())->ff;
		int mx = last;
		// watch(last);
		auto it = prev(mp.end());

		auto jt = it;

		while (1) {
			if (/*jt->ff == (last - 1 + m) % m ||*/ jt->ff == last) {
				res += jt->ff * jt->ss;
				st.insert(jt->ff);
				last = (last - 1) % m;
				// watch(last);

				if (jt == mp.begin()) break;
				jt--;
			}
			else break;
		}

		last = 0;
		jt = mp.begin();
		// watch(mx);

		if (mp.count((mx + 1) % m)) {
			last = (mx + 1) % m;
			// watch(last);

			while (1) {
				if (st.count(jt->ff)) break;

				if (jt->ff == last /*|| jt->ff == (last + 1) % m*/) {
					res += jt->ff * jt->ss;
					st.insert(jt->ff);
					last = (last + 1) % m;

					jt++;
					if (jt == mp.end()) break;
				}
				else break;
			}
		}

		ans = sum - res;

		for (int i : st) {
			// watch(i);
			mp.erase(i);
		}

		// watch(res);

		if (!mp.empty()) {
			jt = mp.begin();
			last = -1;
			res = 0;

			while (jt != mp.end()) {
				if (last == -1) {
					last = jt->ff;
					res = jt->ff * jt->ss;
				}
				else if (jt->ff == last) {
					res += jt->ff * jt->ss;
					last = (last + 1) % m;
				}
				else {
					ans = min(ans, sum - res);
					res = jt->ff * jt->ss;
					last = (jt->ff + 1) % m;
				}

				jt++;
			}

			if (last != -1) {
				ans = min(ans, sum - res);
			}
		}

		cout << ans << "\n";

	}
	return 0;
}

Submission Info

Judge Result