QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#477517#9129. Quotient Sumucup-team2000#WA 1ms3816kbC++14600b2024-07-14 04:40:162024-07-14 04:40:16

Judging History

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

  • [2024-09-26 15:38:30]
  • hack成功,自动添加数据
  • (/hack/908)
  • [2024-07-14 04:40:16]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3816kb
  • [2024-07-14 04:40:16]
  • 提交

answer

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

void solve() {
	int n; cin >> n;
	vector<ll> a(n); for (auto& x : a) cin >> x;
	sort(a.begin(), a.end());

	vector<ll> dp(n);
	for (int i = 1; i < n; i++) {
		int l = 0, r = i-1;
		while (l < r) {
			int m = (l + r) / 2;
			ll x = dp[m] + a[i]/a[m], y = dp[m+1] + a[i]/a[m+1];
			if (x == y) {
				l = r = m;
			} else if (x < y) {
				r = m;
			} else {
				l = m+1;
			}
		}
		dp[i] = dp[l] + a[i]/a[l];
	}
	cout << dp[n-1] << endl;
}

int main() {
    cin.tie(0);
    cin.sync_with_stdio(0);

	int t = 1;
	while (t--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3480kb

input:

3
2 3 6

output:

3

result:

ok "3"

Test #2:

score: 0
Accepted
time: 1ms
memory: 3612kb

input:

2
15 4

output:

3

result:

ok "3"

Test #3:

score: 0
Accepted
time: 1ms
memory: 3816kb

input:

9
284791808 107902 13660981249408 4622332661 13405199 24590921 361 244448137 16077087227955422

output:

4580

result:

ok "4580"

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 3592kb

input:

9
12 9 5 17 2 6 7 1 15

output:

7

result:

wrong answer 1st words differ - expected: '6', found: '7'