QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#847013#2544. Flatland Currencyicpc_zhzx034#WA 334ms9220kbC++141.6kb2025-01-07 16:53:232025-01-07 16:53:33

Judging History

你现在查看的是最新测评结果

  • [2025-01-07 16:53:33]
  • 评测
  • 测评结果:WA
  • 用时:334ms
  • 内存:9220kb
  • [2025-01-07 16:53:23]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 1e5 + 5;

ll n, x0, X, ans, a[N], pos0[5], pos1[5], p[5][N], sum[5][N];

inline void solve() {
	for (int i = max(0ll, pos1[1] - 13); i <= min(pos0[1], pos1[1] + 12); ++i) {
		for (int j = max(0ll, pos1[2] - 7); j <= min(pos0[2], pos1[2] + 6); ++j) {
			for (int k = max(0ll, pos1[3] - 5); k <= min(pos0[3], pos1[3] + 4); ++k) {
				for (int l = max(0ll, pos1[4] - 4); l <= min(pos0[4], pos1[4] + 3); ++l) {
					ans = max(ans, min(X - sum[1][i] - sum[2][j] - sum[3][k] - sum[4][l], (ll)i + j * 2 + k * 3 + l * 4));
				}
			}
		}
	}
}

int main() {
	#ifdef LOCAL
		assert(freopen("test.in", "r", stdin));
		assert(freopen("test.out", "w", stdout));
	#endif
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> X;
	x0 = X % 5;
	X -= x0;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		p[(5 - a[i] % 5) % 5][++pos0[(5 - a[i] % 5) % 5]] = a[i];
	}
	for (int i = 1; i <= 4; ++i) {
		sort(p[i] + 1, p[i] + pos0[i] + 1);
		for (int j = 1; j <= pos0[i]; ++j) {
			sum[i][j] = sum[i][j - 1] + p[i][j];
		}
	}
	for (int i = 1; i <= 4; ++i) {
		pos1[i] = 1;
		p[i][pos0[i] + 1] = 1e18;
	}
	for (int i = 1; i <= pos0[1] + pos0[2] + pos0[3] + pos0[4]; ++i) {
		ld p1 = p[1][pos1[1]], p2 = p[2][pos1[2]] / 2.0, p3 = p[3][pos1[3]] / 3.0, p4 = p[4][pos1[4]] / 4.0;
		if (p1 >= p2 && p1 >= p3 && p1 >= p4) {
			++pos1[1];
		} else if (p2 >= p3 && p2 >= p4) {
			++pos1[2];
		} else if (p3 >= p4) {
			++pos1[3];
		} else {
			++pos1[4];
		}
		solve();
	}
	cout << ans + x0 << "\n";
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 7808kb

input:

5 57
9 14 31 18 27

output:

8

result:

ok answer is '8'

Test #2:

score: 0
Accepted
time: 0ms
memory: 7644kb

input:

4 50
11 11 11 11

output:

12

result:

ok answer is '12'

Test #3:

score: 0
Accepted
time: 334ms
memory: 9132kb

input:

100000 89648823509660
921733427 402270498 51157221 585477094 435728758 913951087 580580944 557082810 585086423 837912728 799129405 867009344 751591136 714946046 464999915 256043168 416678301 183246216 569365122 479031618 435168577 31068363 903791719 497652990 960987871 223120213 395437892 112869678 ...

output:

200414

result:

ok answer is '200414'

Test #4:

score: -100
Wrong Answer
time: 328ms
memory: 9220kb

input:

99999 3234700062922
394766137 401419056 55997758 205712163 585962152 750591556 245421581 607883471 437707305 758188075 522354844 202404802 307099733 99935245 321784033 643800024 481548024 43007287 404431495 848761213 352455926 541535791 702868758 875691279 485597478 119612707 776231855 48839061 1144...

output:

11382

result:

wrong answer expected '61505', found '11382'