QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#102733 | #3194. Knapsack Collection | PetroTarnavskyi# | WA | 136ms | 81468kb | C++17 | 1.3kb | 2023-05-03 16:44:06 | 2023-05-03 16:44:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define SZ(a) (int)a.size()
#define ALL(a) a.begin(), a.end()
#define FOR(i, a, b) for (int i = (a); i<(b); ++i)
#define RFOR(i, b, a) for (int i = (b)-1; i>=(a); --i)
#define MP make_pair
#define PB push_back
#define F first
#define S second
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int MX = 1e7 + 47;
LL ans[MX];
int n, s, t;
void f(int i, multiset<int> m)
{
if (ans[i]) return;
while (!m.empty())
{
int pos = (i + ans[i]) % s;
auto it = m.lower_bound(pos);
if (it == m.end()) it = m.begin();
int pos2 = *it;
m.erase(it);
ans[i] += (pos2 - pos + s) % s;
ans[i] += t;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> s >> t;
multiset<int> ms;
FOR(i, 0, n)
{
int a;
cin >> a;
ms.insert(a);
}
for (auto i : ms) f(i, ms);
int j = *ms.begin();
int val = ans[j];
FOR(i, 0, s)
{
int k = (j - i + s) % s;
if (ans[k]) val = ans[k];
else ans[k] = ++val;
}
cout << *min_element(ans, ans + s) << '\n';
cout << *max_element(ans, ans + s) << '\n';
LL sum = accumulate(ans, ans + s, 0ll);
LL g = gcd(sum, s);
cout << sum / g << '/' << s / g << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3320kb
input:
7 10 10000000 0 0 0 0 0 0 1
output:
70000001 70000009 350000027/5
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 2ms
memory: 3368kb
input:
10 10 3 0 0 2 2 4 4 6 6 8 8
output:
39 40 79/2
result:
ok 3 lines
Test #3:
score: 0
Accepted
time: 70ms
memory: 81468kb
input:
9 10000000 1 0 7 2 3 4 5 6 1 8
output:
9 10000000 12500021249991/2500000
result:
ok 3 lines
Test #4:
score: -100
Wrong Answer
time: 136ms
memory: 48356kb
input:
1000 5752352 9302172 1473740 1253927 2058266 2440001 3007902 2154122 5162393 1447874 5636700 2726828 3029551 3245083 3959896 1675726 5612527 5425457 2603081 959614 619276 579327 1512143 3107246 4323157 2224868 491514 4037564 5737062 1155534 4260273 1099943 3864642 4100143 2282326 3273233 3346948 250...
output:
893486527 9489162722 1291202822513755/1438088
result:
wrong answer 1st lines differ - expected: '9483421118', found: '893486527'