QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#191642 | #5259. Skills in Pills | timreizin | RE | 0ms | 3788kb | C++20 | 1.6kb | 2023-09-30 05:30:51 | 2023-09-30 05:30:51 |
Judging History
answer
#include <vector>
#include <queue>
#include <list>
#include <iostream>
#include <array>
#include <string>
#include <numeric>
#include <algorithm>
#include <cmath>
using namespace std;
using ll = long long;
int main()
{
int k, j, n;
cin >> k >> j >> n;
auto findArr = [&n](int k, int j)
{
vector<int> res;
int cnt0 = 0, cnt1 = 1;
for (int i = 0; i < n + 5; ++i)
{
res.push_back((i == 0 ? 0 : res.back()));
++cnt0;
++cnt1;
if (cnt0 == k && cnt1 == j)
{
res.pop_back();
return res;
}
res[i] += cnt0 / k + cnt1 / j;
cnt0 %= k;
cnt1 %= j;
}
return res;
};
vector<int> arr1 = findArr(k, j), arr2 = findArr(j, k);
vector<int> dp(n);
dp[0] = 0;
for (int i = 1; i <= n; ++i)
{
if (i > arr1.size())
dp[i] = dp[i - arr1.size() - 1] + arr1.back() + 2;
else
dp[i] = arr1[i - 1];
if (i > arr2.size())
dp[i] = min(dp[i], dp[i - arr2.size() - 1] + arr2.back() + 2);
else
dp[i] = min(dp[i], arr2[i - 1]);
}
int cnt1 = 0, cnt2 = 0, res = 0;
for (int i = 1; i <= n; ++i)
{
++cnt1;
++cnt2;
res += cnt1 / k + cnt2 / j;
if (cnt1 == k && cnt2 == j)
{
res += dp[n - i];
break;
}
cnt1 %= k;
cnt2 %= j;
}
cout << res;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3784kb
input:
3 9 20
output:
8
result:
ok single line: '8'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3568kb
input:
8 2 12
output:
7
result:
ok single line: '7'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
2 5 15
output:
10
result:
ok single line: '10'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3460kb
input:
10 8 13
output:
2
result:
ok single line: '2'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
6 6 19
output:
6
result:
ok single line: '6'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3536kb
input:
2 3 5
output:
3
result:
ok single line: '3'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
4 2 8
output:
6
result:
ok single line: '6'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3788kb
input:
5 5 5
output:
2
result:
ok single line: '2'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3592kb
input:
3 8 11
output:
4
result:
ok single line: '4'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3732kb
input:
5 8 16
output:
5
result:
ok single line: '5'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3580kb
input:
9 7 279
output:
70
result:
ok single line: '70'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3728kb
input:
8 3 56
output:
25
result:
ok single line: '25'
Test #13:
score: -100
Runtime Error
input:
5 9 46