QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#557089 | #360. Cultivation | makrav | 30 | 19ms | 4088kb | C++20 | 14.3kb | 2024-09-11 02:50:44 | 2024-09-11 02:50:44 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
#define int ll
const int INF = 1000000000000;
void solve() {
int h, w, n; cin >> h >> w >> n;
vector<pair<int, int>> a(n);
for (int i = 0; i < n; i++) cin >> a[i].ff >> a[i].sc;
vector<vector<bool>> gp(n, vector<bool>(n, false));
sort(all(a), [](pair<int, int> x, pair<int, int> y) {
return x.second < y.second;
});
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
bool gpp = true;
for (int k = 0; k < n; k++) {
if (k==i||k==j)continue;
if ((a[k].first - a[i].first) * (a[k].first - a[j].first) <= 0 && (a[k].second - a[i].second) * (a[k].second - a[j].second) <= 0) {
gpp = false;
break;
}
}
gp[i][j]=gpp;
}
}
vector<pair<int, int>> gps;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (gp[i][j]) {
//cout << i << ' ' << j << '\n';
gps.pb({i, j});
}
}
}
// for (auto &u : a) cout << u.first << ' ' << u.second << '\n';
// for (auto &u : gps) {
// cout << u.first << ' ' << u.second << '\n';
// }
//return;
// all above -- correct (i think)
vector<ll> delta(sz(gps));
vector<int> is_delta_correct(sz(gps));
for (int i = 0; i < sz(gps); i++) {
ll max_up = 0, min_d = h + 1;
int mxy = max(a[gps[i].first].first, a[gps[i].second].first), mny = min(a[gps[i].first].first, a[gps[i].second].first);
for (int j = 0; j < n; j++) {
if (a[gps[i].first].second < a[j].second && a[j].second < a[gps[i].second].second) {
if (a[j].first > mxy) min_d = min(min_d, (ll)a[j].first);
else {
assert(a[j].first < mny);
max_up = max(max_up, (ll)a[j].first);
}
}
}
if (min_d == h + 1 && max_up == 0) delta[i] = INF;
else if (min_d != h + 1 && max_up != 0) delta[i] = (min_d - max_up - 1);
else {
if (min_d != h + 1) {
is_delta_correct[i] = 1;
delta[i] = min_d - 1;
} else {
is_delta_correct[i] = 2;
delta[i] = h - max_up;
}
}
}
// all above -- probably correct ..)
vector<int> never_left(n), never_right(n);
vector<ll> lol_left(n), lol_right(n);
vector<int> type_left(n), type_right(n);
for (int i = 0; i < n; i++) {
{
// left
int max_up = 0, min_d = h + 1;
for (int j = 0; j < n; j++) {
if (a[j].second < a[i].second) {
if (a[j].first == a[i].first) {
never_left[i] = 1;
break;
}
if (a[j].first < a[i].first) max_up = max(max_up, a[j].first);
else min_d = min(min_d, a[j].first);
}
}
if (min_d == h + 1 && max_up == 0) lol_left[i] = INF;
else if (min_d != h + 1 && max_up != 0) lol_left[i] = min_d - max_up;
else {
if (min_d != h + 1) {
type_left[i] = 1;
lol_left[i] = min_d - 1;
} else {
type_left[i] = 2;
lol_left[i] = h - max_up;
}
}
}
{
// right
int max_up = 0, min_d = h + 1;
for (int j = 0; j < n; j++) {
if (a[j].second > a[i].second) {
if (a[j].first == a[i].first) {
never_right[i] = 1;
break;
}
if (a[j].first < a[i].first) max_up = max(max_up, a[j].first);
else min_d = min(min_d, a[j].first);
}
}
if (min_d == h + 1 && max_up == 0) lol_right[i] = INF;
else if (min_d != h + 1 && max_up != 0) lol_right[i] = min_d - max_up;
else {
if (min_d != h + 1) {
type_right[i] = 1;
lol_right[i] = min_d - 1;
} else {
type_right[i] = 2;
lol_right[i] = h - max_up;
}
}
//cout << a[i].first << ' ' << a[i].second << ' ' << type_right[i] << ' ' << never_right[i] << '\n';
}
}
// check this block above
vector<int> ord_left(n), ord_right(n);
iota(all(ord_left), 0); iota(all(ord_right), 0);
sort(all(ord_left), [&](int i, int j) {
return a[i].second < a[j].second;
});
sort(all(ord_right), [&](int i, int j) {
return a[i].second > a[j].second;
});
vector<int> pos_left(n), pos_right(n);
for (int i = 0; i < n; i++) {
pos_left[ord_left[i]] = i;
pos_right[ord_right[i]] = i;
}
vector<int> ups;
for (int i = 0; i < n; i++) ups.pb(a[i].first - 1);
// part above probably correct
vector<int> alds;
for (int i = 0; i < sz(gps); i++) {
alds.pb(a[gps[i].second].second - a[gps[i].first].second - 1);
}
sort(all(alds));
alds.resize(unique(all(alds)) - alds.begin());
map<int, int> pos;
for (int i = 0; i < sz(alds); i++) pos[alds[i]] = i;
vector<int> ind_mid(sz(gps));
for (int i = 0; i < sz(gps); i++) ind_mid[i] = pos[a[gps[i].second].second - a[gps[i].first].second - 1];
// part above probably correct
vector<int> ordp1(sz(gps)) /* order by delta of basic y values */, ordp2(sz(gps)) /* order by delta of second y values */;
vector<int> vals(sz(gps)), W(sz(gps));
for (int i = 0; i < sz(gps); i++) {
vals[i] = abs(a[gps[i].first].first - a[gps[i].second].first);
W[i] = a[gps[i].second].second - a[gps[i].first].second;
}
iota(all(ordp1), 0);
sort(all(ordp1), [&](int i, int j){
return vals[i] < vals[j];
});
iota(all(ordp2), 0);
sort(all(ordp2), [&](int i, int j) {
return delta[i] < delta[j];
});
vector<int> YS;
for (int i =0;i<n;i++)YS.pb(a[i].first);
sort(all(YS));
int MX=0;
for (int i=1;i<n;i++){
MX=max(MX,YS[i]-YS[i-1]-1);
}
// fuck
int need_down = INF;
for (int i = 0; i < n; i++) need_down = min(need_down, h - a[i].first);
auto solve = [&](int up) -> long long {
// returns minimal answer with current up value
vector<pair<int, int>> lefts, rights;
vector<int> used_left(n, 0), used_right(n, 0), cnt_mid(sz(alds));
vector<pair<int, int>> start_mid, endd_mid, endd_mid_fuck;
for (int i = 0; i < n; i++) {
{
if (never_left[i]) continue;
if (type_left[i] == 0) {
if (lol_left[i] - 1 <= up) continue;
lefts.pb({lol_left[i] - 1 - up, pos_left[i]});
used_left[pos_left[i]] = 1;
} else if (type_left[i] == 1) {
if (up >= lol_left[i]) continue;
used_left[pos_left[i]] = 1;
} else {
used_left[pos_left[i]] = 1;
lefts.pb({lol_left[i], pos_left[i]});
}
}
}
for (int i = 0; i < n; i++) {
{
if (never_right[i]) continue;
if (type_right[i] == 0) {
if (lol_right[i] - 1 <= up) continue;
rights.pb({lol_right[i] - 1 - up, pos_right[i]});
used_right[pos_right[i]] = 1;
} else if (type_right[i] == 1) {
if (up >= lol_right[i]) continue;
used_right[pos_right[i]] = 1;
} else {
used_right[pos_right[i]] = 1;
//cout << a[pos_right[i]].second << "fuckk\n";
rights.pb({lol_right[i], pos_right[i]});
}
if (lol_right[i] - 1 <= up) {
continue;
}
}
}
sort(all(lefts)); sort(all(rights));
int pmax_left = -1, pmax_right = -1, pmid = -1;
auto update_left = [&]() {
while (pmax_left >= 0 && !used_left[pmax_left]) pmax_left--;
};
auto update_right = [&]() {
while (pmax_right >= 0 && !used_right[pmax_right]) pmax_right--;
};
auto update_mid = [&]() {
while (pmid >= 0 && cnt_mid[pmid] <= 0) pmid--;
};
for (int i = 0; i < n; i++) {
if (used_left[i]) pmax_left = i;
if (used_right[i]) pmax_right = i;
}
vector<int> E0;
for (int i = 0; i < sz(gps); i++) {
int j = ordp2[i];
if (is_delta_correct[j] == 0) {
endd_mid.pb({ind_mid[j], max(0ll, delta[j] - up)});
} else if (is_delta_correct[j] == 1) {
if (up >= delta[j]) {
E0.pb(ind_mid[j]);
}
} else {
endd_mid_fuck.pb({ind_mid[j], delta[j]});
}
start_mid.pb({ind_mid[ordp1[i]], max(0ll, vals[ordp1[i]] - up)});
}
// for (int i = 0; i < sz(gps); i++) {
// if (is_delta_correct[ordp2[i]]) {
// endd_mid.pb({ind_mid[ordp2[i]], delta[ordp2[i]]});
// } else {
// }
// if (delta[ordp2[i]] > up) endd_mid.pb({ind_mid[ordp1[i]], delta[ordp2[i]] - up});
// }
int ind_start = 0, ind_endd = 0, ind_endd_fuck = 0, ind_left = 0, ind_right = 0;
for (int F : E0) {
cnt_mid[F]--;
}
while (ind_start < sz(start_mid) && start_mid[ind_start].second == 0) {
cnt_mid[start_mid[ind_start].first]++;
ind_start++;
}
while (ind_endd_fuck < sz(endd_mid_fuck) && endd_mid_fuck[ind_endd_fuck].second == 0) {
cnt_mid[endd_mid_fuck[ind_endd_fuck].first]--;
ind_endd_fuck++;
}
while (ind_endd < sz(endd_mid) && endd_mid[ind_endd].second == 0) {
cnt_mid[endd_mid[ind_endd].first]--;
ind_endd++;
}
while (ind_left < sz(lefts) && lefts[ind_left].first == 0) {
used_left[lefts[ind_left].second] = 0;
ind_left++;
}
while (ind_right < sz(rights) && rights[ind_right].first == 0) {
used_right[rights[ind_right].second] = 0;
ind_right++;
}
update_left(); update_right();
for (int i = 0; i < sz(alds); i++) {
if (cnt_mid[i] > 0) pmid = i;
}
int NEW_NEED = max(need_down, MX-up);
int A = 4 * INF;
int pl = (pmax_left == -1 ? 0 : a[ord_left[pmax_left]].second - 1), pr = (pmax_right == -1 ? 0 : w - a[ord_right[pmax_right]].second),
pm = (pmid == -1 ? 0 : alds[pmid]);
if (NEW_NEED == 0) {
A = min(A, max(pl+pr,pm));
}
//cout<<up<<" moment zero " << pl << ' ' << pr << ' ' << pm << '\n';
int pmnt=-1;
//cout << up << " start shit " << pl << ' ' << pr << ' ' << pm << '\n';
while (ind_start < sz(start_mid) || ind_endd_fuck < sz(endd_mid_fuck) || ind_left < sz(lefts) || ind_right < sz(rights) || ind_endd < sz(endd_mid)) {
int mnt = 4 * INF;
if (ind_start < sz(start_mid)) mnt = min(mnt, start_mid[ind_start].second);
if (ind_left < sz(lefts)) mnt = min(mnt, lefts[ind_left].first);
if (ind_right < sz(rights)) mnt = min(mnt, rights[ind_right].first);
if (ind_endd < sz(endd_mid)) mnt = min(mnt, endd_mid[ind_endd].second);
if (ind_endd_fuck < sz(endd_mid_fuck)) mnt = min(mnt, endd_mid_fuck[ind_endd_fuck].second);
while (ind_start < sz(start_mid) && start_mid[ind_start].second == mnt) {
cnt_mid[start_mid[ind_start].first]++;
ind_start++;
}
while (ind_endd < sz(endd_mid) && endd_mid[ind_endd].second == mnt) {
cnt_mid[endd_mid[ind_endd].first]--;
ind_endd++;
}
while (ind_endd_fuck < sz(endd_mid_fuck) && endd_mid_fuck[ind_endd_fuck].second == mnt) {
cnt_mid[endd_mid_fuck[ind_endd_fuck].first]--;
ind_endd_fuck++;
}
while (ind_left < sz(lefts) && lefts[ind_left].first == mnt) {
used_left[lefts[ind_left].second] = 0;
ind_left++;
}
while (ind_right < sz(rights) && rights[ind_right].first == mnt) {
used_right[rights[ind_right].second] = 0;
ind_right++;
}
update_left(); update_mid(); update_right();
int cl = (pmax_left == -1 ? 0 : a[ord_left[pmax_left]].second - 1), cr = (pmax_right == -1 ? 0 : w - a[ord_right[pmax_right]].second),
cmid = (pmid == -1 ? 0 : alds[pmid]);
//cout << up << ' ' << mnt << ' ' << cl << ' ' << cr << ' ' << cmid << '\n';
if (mnt >= NEW_NEED) {
A = min(A, mnt + max(cl + cr, cmid));
// if (mnt+max(cl+cr,cmid) == 1){
// cout<<"FUCKCKKKCKCKC " << up << ' ' << mnt << '\n';
// }
if (mnt > NEW_NEED && pmnt <= NEW_NEED) {
A=min(A, NEW_NEED+max(pl+pr,pm));
}
}
pmnt=mnt;
pm=cmid;
pl=cl;
pr=cr;
}
return A + up;
};
ll ans = 4000000000;
for (int up : ups) {
ans = min(ans, solve(up));
}
cout << ans << '\n';
}
signed main() {
int tt = 1;
#ifdef LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> tt;
#else
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
#endif
while (tt--) {
solve();
}
return 0;
}
详细
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 0ms
memory: 3844kb
input:
2 4 2 1 1 1 4
output:
3
result:
ok single line: '3'
Test #2:
score: 5
Accepted
time: 0ms
memory: 3564kb
input:
4 1 1 2 1
output:
3
result:
ok single line: '3'
Test #3:
score: 5
Accepted
time: 0ms
memory: 3620kb
input:
3 3 3 1 2 1 3 3 3
output:
3
result:
ok single line: '3'
Test #4:
score: 5
Accepted
time: 0ms
memory: 3628kb
input:
2 2 1 1 2
output:
2
result:
ok single line: '2'
Test #5:
score: 5
Accepted
time: 0ms
memory: 3648kb
input:
4 4 10 4 2 2 3 2 4 4 1 1 2 2 1 4 3 3 3 3 1 1 4
output:
2
result:
ok single line: '2'
Test #6:
score: 5
Accepted
time: 0ms
memory: 3616kb
input:
4 4 1 4 1
output:
6
result:
ok single line: '6'
Test #7:
score: 5
Accepted
time: 0ms
memory: 3560kb
input:
4 4 3 2 2 3 3 1 4
output:
5
result:
ok single line: '5'
Test #8:
score: 5
Accepted
time: 0ms
memory: 3568kb
input:
4 4 15 4 3 2 4 4 4 4 1 3 3 1 2 3 1 2 1 3 4 3 2 4 2 2 3 1 3 2 2 1 4
output:
1
result:
ok single line: '1'
Test #9:
score: 5
Accepted
time: 0ms
memory: 3512kb
input:
4 3 3 2 1 2 3 4 1
output:
3
result:
ok single line: '3'
Test #10:
score: 5
Accepted
time: 0ms
memory: 3512kb
input:
4 4 2 3 4 2 4
output:
5
result:
ok single line: '5'
Test #11:
score: 5
Accepted
time: 0ms
memory: 3648kb
input:
2 4 1 1 2
output:
4
result:
ok single line: '4'
Test #12:
score: 5
Accepted
time: 0ms
memory: 3784kb
input:
3 3 4 2 1 1 1 3 2 3 1
output:
2
result:
ok single line: '2'
Test #13:
score: 5
Accepted
time: 0ms
memory: 3808kb
input:
3 4 3 1 4 3 3 3 4
output:
4
result:
ok single line: '4'
Test #14:
score: 5
Accepted
time: 0ms
memory: 3508kb
input:
3 3 2 2 1 3 3
output:
4
result:
ok single line: '4'
Test #15:
score: 5
Accepted
time: 0ms
memory: 3644kb
input:
4 4 2 2 4 3 1
output:
6
result:
ok single line: '6'
Test #16:
score: 5
Accepted
time: 0ms
memory: 3556kb
input:
4 4 3 2 2 2 1 4 2
output:
4
result:
ok single line: '4'
Subtask #2:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #17:
score: 10
Accepted
time: 0ms
memory: 3580kb
input:
15 15 20 6 13 14 4 11 13 15 3 12 4 10 4 11 6 8 9 12 12 2 15 4 3 8 15 8 4 3 1 5 10 11 12 8 7 13 10 11 4 1 3
output:
13
result:
ok single line: '13'
Test #18:
score: 10
Accepted
time: 1ms
memory: 3608kb
input:
25 25 66 24 6 12 18 11 2 24 18 6 9 20 6 15 19 17 2 15 9 15 20 18 9 5 19 9 2 6 12 22 16 6 2 1 5 14 24 12 21 17 24 10 15 21 1 20 22 11 24 11 4 6 21 18 12 25 20 16 3 18 16 6 4 20 9 6 15 24 14 3 20 9 9 25 9 18 6 4 16 12 7 14 22 20 25 24 10 11 14 17 6 23 23 21 12 18 22 8 23 1 11 17 18 8 5 3 7 1 17 8 12 4...
output:
9
result:
ok single line: '9'
Test #19:
score: 10
Accepted
time: 1ms
memory: 3896kb
input:
36 38 28 30 5 4 23 29 20 1 36 8 28 8 9 5 26 23 16 26 1 24 38 22 36 4 26 9 7 10 24 20 11 31 5 24 30 26 30 18 15 14 1 23 31 20 7 23 30 33 9 27 33 8 7 9 16 33 5
output:
30
result:
ok single line: '30'
Test #20:
score: 10
Accepted
time: 0ms
memory: 3872kb
input:
10 40 19 7 5 8 38 4 7 8 5 4 30 1 33 1 16 2 21 8 33 4 36 6 20 6 27 4 14 10 15 9 30 8 13 4 15 10 9 5 22
output:
17
result:
ok single line: '17'
Test #21:
score: 10
Accepted
time: 1ms
memory: 3664kb
input:
40 30 50 19 20 18 16 34 28 5 8 28 21 24 13 7 1 28 23 28 18 12 6 3 6 18 8 40 27 22 19 23 22 8 6 9 12 16 10 27 25 26 19 4 9 40 26 21 22 10 8 5 2 30 25 12 12 3 1 24 14 5 3 4 8 19 9 21 16 6 3 38 29 27 20 37 25 36 24 22 20 29 26 30 19 16 14 3 3 39 25 5 7 20 15 13 12 33 30 27 16 25 14
output:
50
result:
ok single line: '50'
Test #22:
score: 10
Accepted
time: 2ms
memory: 3596kb
input:
40 40 120 23 22 31 36 2 4 2 32 14 40 23 32 18 11 27 36 7 1 25 33 22 40 34 9 26 20 18 7 35 7 3 17 19 6 5 27 19 30 33 15 2 15 19 15 4 8 27 1 8 27 10 2 11 39 31 27 32 35 17 4 18 22 2 7 7 10 5 14 40 23 3 36 6 6 6 15 21 35 27 39 25 1 40 11 36 16 8 23 35 27 18 21 24 39 13 22 4 3 12 17 31 16 3 6 6 4 3 30 2...
output:
16
result:
ok single line: '16'
Test #23:
score: 10
Accepted
time: 1ms
memory: 3668kb
input:
40 40 33 10 22 10 3 7 11 12 14 11 12 1 21 6 23 3 11 8 24 3 40 8 14 7 25 8 15 12 3 10 7 4 32 7 32 9 32 9 30 4 22 8 22 11 24 6 19 10 16 10 2 9 4 10 15 9 28 7 1 4 31 7 35 4 18 2 35
output:
46
result:
ok single line: '46'
Test #24:
score: 10
Accepted
time: 6ms
memory: 3676kb
input:
40 40 200 10 16 27 15 18 11 16 25 34 7 39 25 26 15 12 20 8 1 20 14 25 27 33 4 29 40 20 33 8 9 32 16 37 25 34 27 31 23 30 8 40 30 35 37 27 7 18 27 36 30 13 30 12 32 32 4 15 21 29 39 4 32 8 7 12 21 35 40 32 29 34 17 22 30 12 34 34 39 23 16 27 16 13 26 28 32 8 31 30 16 13 25 28 13 19 35 38 35 2 40 7 1 ...
output:
14
result:
ok single line: '14'
Test #25:
score: 10
Accepted
time: 0ms
memory: 3744kb
input:
40 40 150 8 38 27 32 34 14 29 32 16 36 29 19 40 30 30 22 34 12 4 30 24 37 14 8 31 21 40 17 38 25 16 5 29 5 38 29 28 10 2 5 5 16 20 11 38 6 21 11 5 8 26 13 21 35 27 27 10 11 18 30 30 40 8 18 31 5 16 7 3 1 35 36 40 26 18 39 25 8 19 16 17 26 6 20 13 30 34 4 35 8 33 4 25 29 39 7 22 40 10 36 26 3 30 14 1...
output:
16
result:
ok single line: '16'
Test #26:
score: 10
Accepted
time: 9ms
memory: 3848kb
input:
40 40 300 5 29 4 30 10 5 19 1 11 37 8 26 2 12 29 25 13 33 4 36 15 9 6 39 27 35 34 14 35 27 32 26 14 35 23 35 23 34 12 6 2 21 20 29 20 23 5 21 15 11 7 13 6 23 33 7 19 22 20 31 28 25 7 18 15 39 25 1 2 16 5 23 5 28 7 21 5 31 8 29 16 14 18 29 16 3 3 23 20 35 24 34 14 4 14 30 39 18 25 5 19 37 28 10 7 11 ...
output:
18
result:
ok single line: '18'
Test #27:
score: 10
Accepted
time: 13ms
memory: 3772kb
input:
40 40 300 23 5 15 1 34 20 36 22 19 4 31 19 11 34 13 33 3 20 18 4 27 10 37 21 14 11 30 34 8 29 6 26 32 33 8 10 1 14 40 40 4 22 19 31 6 28 37 16 22 34 38 17 16 2 18 36 12 4 38 15 1 24 1 18 32 8 6 18 35 26 12 36 25 2 38 20 19 3 25 12 2 34 35 22 10 36 26 3 10 22 36 8 29 33 3 39 5 10 7 9 36 14 24 5 5 21 ...
output:
14
result:
ok single line: '14'
Test #28:
score: 10
Accepted
time: 6ms
memory: 3792kb
input:
39 40 200 9 40 2 33 16 32 14 33 14 27 3 28 5 31 36 30 15 22 23 17 22 28 13 10 4 14 24 35 4 35 12 22 28 32 8 37 7 31 1 37 28 21 39 22 12 17 7 20 35 16 10 12 12 6 27 31 33 15 19 16 13 35 26 35 10 19 15 25 18 19 21 9 11 9 39 4 3 31 20 24 37 26 22 38 13 40 18 12 29 4 31 2 10 26 2 39 2 3 18 9 14 34 39 23...
output:
15
result:
ok single line: '15'
Test #29:
score: 10
Accepted
time: 15ms
memory: 3848kb
input:
38 38 300 30 33 11 38 6 10 19 20 29 30 1 18 30 20 11 19 23 15 32 3 32 30 5 34 7 30 34 1 5 4 20 35 8 13 25 32 12 2 6 3 1 19 38 7 35 16 14 9 37 2 10 4 13 21 37 17 34 4 20 20 14 12 20 13 36 3 10 33 5 8 23 23 9 22 17 19 13 9 20 14 31 4 11 23 17 32 12 10 21 23 31 11 17 35 12 17 31 27 3 6 10 37 2 38 5 15 ...
output:
9
result:
ok single line: '9'
Test #30:
score: 10
Accepted
time: 15ms
memory: 3820kb
input:
40 40 300 25 27 25 10 20 19 16 40 29 29 39 20 3 4 6 20 20 6 1 25 39 32 28 26 27 17 30 38 4 33 27 24 21 4 36 32 29 7 4 23 39 2 40 6 14 40 33 39 23 32 23 34 18 6 36 28 40 4 15 28 13 33 34 3 4 35 20 29 38 36 7 24 5 25 20 3 37 13 40 26 5 9 40 36 24 26 16 14 8 28 37 6 24 16 7 3 28 28 34 13 34 36 29 12 13...
output:
10
result:
ok single line: '10'
Test #31:
score: 10
Accepted
time: 15ms
memory: 3856kb
input:
40 40 300 31 12 30 38 21 17 11 12 1 28 10 37 10 13 5 22 18 21 28 37 23 40 29 32 21 33 5 3 21 24 14 15 2 23 9 33 15 31 38 12 37 8 37 26 1 5 28 34 22 10 18 29 30 39 23 34 25 37 35 1 10 7 25 11 10 38 34 30 18 1 12 1 10 25 16 11 35 40 26 30 5 15 23 3 22 22 16 4 8 21 12 23 24 29 4 27 40 5 18 15 35 38 1 1...
output:
9
result:
ok single line: '9'
Test #32:
score: 10
Accepted
time: 15ms
memory: 3744kb
input:
40 40 300 24 6 26 15 30 7 10 12 17 17 7 25 36 26 19 39 32 10 20 1 16 1 34 1 23 19 10 38 40 7 13 39 25 27 28 25 39 18 25 20 17 3 32 28 10 4 6 3 12 16 29 35 13 12 29 16 2 35 6 15 19 7 1 32 18 24 13 18 1 31 28 31 29 12 19 4 20 10 1 3 6 38 1 10 27 14 33 26 1 12 8 31 9 39 22 21 8 39 37 3 26 33 25 10 32 4...
output:
11
result:
ok single line: '11'
Subtask #3:
score: 15
Accepted
Dependency #2:
100%
Accepted
Test #33:
score: 15
Accepted
time: 5ms
memory: 3744kb
input:
2 200000000 300 1 88265857 1 174408185 1 105379902 1 185252998 2 30206021 2 102367431 2 89739523 1 116153736 2 68837704 1 110817136 2 26646126 2 86276690 1 127329134 2 126441765 1 19927577 1 38738747 1 105161585 1 60367988 2 67085969 1 1865971 1 27164731 1 77127255 2 168438218 1 4482768 1 197852914 ...
output:
3425851
result:
ok single line: '3425851'
Test #34:
score: 15
Accepted
time: 7ms
memory: 3704kb
input:
40 1000000000 300 20 483437001 11 245274001 5 80864001 2 7139001 36 895164001 32 773938001 27 666531001 36 894646001 20 467811001 36 877372001 4 76683001 25 599539001 25 604099001 34 834882001 6 105503001 12 279215001 27 655684001 16 364895001 19 439732001 4 61698001 39 973882001 38 925548001 28 684...
output:
19162076
result:
ok single line: '19162076'
Test #35:
score: 15
Accepted
time: 18ms
memory: 3888kb
input:
40 1000000000 300 38 393750001 12 93750001 33 31250002 18 68749999 36 631250003 14 581250003 37 843750003 39 31250001 17 6250002 11 481250000 3 818750001 37 568750002 20 281250001 36 731249999 3 731250003 30 206250000 14 893750002 18 618749999 2 868750003 9 243750003 9 781250000 39 168749999 37 8687...
output:
12500068
result:
ok single line: '12500068'
Test #36:
score: 15
Accepted
time: 18ms
memory: 4080kb
input:
40 1000000000 300 20 273611973 30 962515424 19 457562756 14 228419368 9 839242624 34 416448186 6 49326057 27 373662328 18 43718671 40 180109032 35 703858821 6 62818768 23 176704786 30 419420243 29 966647309 30 971207395 9 471992569 17 18782375 28 524707582 15 887562815 20 339788418 40 188122260 33 1...
output:
25840886
result:
ok single line: '25840886'
Test #37:
score: 15
Accepted
time: 18ms
memory: 4004kb
input:
35 1000000000 300 26 304985784 31 53820856 34 188129610 32 933853739 29 435634084 16 233290946 24 581180249 14 763935773 10 265931834 9 274498426 16 675425485 15 87227536 21 985415295 14 272012946 12 765102757 24 458857877 20 610373170 25 928877042 32 589674594 23 467914943 31 693779625 19 197133223...
output:
14686151
result:
ok single line: '14686151'
Test #38:
score: 15
Accepted
time: 19ms
memory: 4088kb
input:
40 1000000000 300 6 786763464 27 418721225 37 714875337 10 156646263 9 190541536 30 429336661 7 865464196 28 815774814 35 25779712 30 681279351 11 395942851 13 574687654 29 137106802 33 754832787 37 294845778 19 815900516 14 704212093 36 198711902 17 533523161 34 748841831 17 981957453 30 294955278 ...
output:
21233330
result:
ok single line: '21233330'
Test #39:
score: 15
Accepted
time: 17ms
memory: 4064kb
input:
40 1000000000 300 40 70731728 31 860477266 8 270731733 14 56097551 5 524390251 21 148780485 6 60975598 26 612195132 13 997560998 36 426829256 32 7317081 1 256097581 25 457312359 12 241463431 5 85365829 18 4440737 1 436585368 34 39238855 33 625252064 1 143902436 13 338440011 25 334146355 5 515606983 ...
output:
4878171
result:
ok single line: '4878171'
Test #40:
score: 15
Accepted
time: 18ms
memory: 3952kb
input:
40 1000000000 300 34 290272040 11 654139182 15 574182947 32 483616706 23 30659851 7 688206175 33 677483533 20 245930698 16 854673531 5 415424827 23 516937655 2 347957583 4 76422831 29 693454243 24 109103102 19 755284863 16 509051878 8 373221893 35 422824677 1 923039234 37 493392984 2 648194620 12 12...
output:
23360164
result:
ok single line: '23360164'
Test #41:
score: 15
Accepted
time: 6ms
memory: 3824kb
input:
40 999992811 300 40 756167738 1 755422093 1 756075552 40 755448533 40 755699260 1 755699433 40 756570280 40 755364761 1 755246371 40 756081840 1 756154293 1 756152536 1 755866341 1 755312497 40 755640274 7 340135464 3 953017751 1 755712914 1 755664483 40 755797029 9 969531054 40 755779575 1 75564995...
output:
129414313
result:
ok single line: '129414313'
Test #42:
score: 15
Accepted
time: 11ms
memory: 3720kb
input:
40 1000000000 300 17 999998001 1 999997965 1 999997890 1 7932 5 505323503 40 999998121 1 999998027 1 999998002 9 999997972 1 999997920 40 999997891 30 7999 29 7999 31 999998062 1 999998144 40 999997890 40 999998033 1 999998006 21 999997999 40 999998031 40 8094 40 999997995 13 999998024 40 999997875 ...
output:
209640461
result:
ok single line: '209640461'
Test #43:
score: 15
Accepted
time: 10ms
memory: 3980kb
input:
40 1000000000 300 23 549509844 40 95786908 40 39290135 13 992491098 26 87052294 40 231331522 19 288109792 23 482918072 1 27192653 25 931473083 40 1 12 695623563 8 518257580 1 40343403 40 271412132 40 24291430 1 776119616 29 837580112 5 24636122 2 883373187 31 209930451 37 133788324 1 224219724 1 138...
output:
21898080
result:
ok single line: '21898080'
Test #44:
score: 15
Accepted
time: 17ms
memory: 3992kb
input:
40 1000000000 300 6 366666665 15 300000001 24 233333337 1 966666667 25 853754960 23 766666669 30 233333334 24 433333334 15 566666670 14 233333334 34 233333335 32 166666668 37 366666664 30 337173509 30 100000002 31 33333334 17 500000004 15 834459573 22 773895258 32 900000001 35 100000002 40 500000001...
output:
53549258
result:
ok single line: '53549258'
Subtask #4:
score: 0
Wrong Answer
Test #45:
score: 30
Accepted
time: 1ms
memory: 3636kb
input:
1000000000 1000000000 17 822413671 70423910 260075513 431043546 300945721 793553248 142848049 163787897 392462410 831950868 699005697 111397300 444396260 130450496 642691616 595456084 467968916 463598810 159764248 611476406 929313754 539645102 365153650 964108073 906780716 373514044 970118116 655138...
output:
852626202
result:
ok single line: '852626202'
Test #46:
score: 30
Accepted
time: 1ms
memory: 3584kb
input:
1000000000 1000000000 24 382358372 812500277 617637090 687506454 441176760 562497727 382346048 687504690 205880053 312504652 794110577 62497634 264714161 937490675 970587944 812502893 617647581 62504110 852944701 812498007 88227293 187492617 558814156 687495577 29403236 812494493 911761865 187491781...
output:
904419459
result:
ok single line: '904419459'
Test #47:
score: 30
Accepted
time: 1ms
memory: 3672kb
input:
1000000000 1000000000 25 59999964 299999989 740000035 100000111 139999972 499999797 740000159 899999809 940000104 899999905 459999870 299999853 139999925 899999750 260000183 300000150 260000200 699999915 940000072 99999821 340000223 900000130 739999776 499999813 59999984 700000029 539999767 90000023...
output:
480000793
result:
ok single line: '480000793'
Test #48:
score: 30
Accepted
time: 1ms
memory: 3652kb
input:
1000000000 1000000000 25 496770868 499466029 150245306 140351260 443861207 442170127 915815913 907024280 592352731 580300173 614771420 602707761 545759771 564678204 790963611 795646738 466306333 474998682 700037062 710428701 326403486 341417980 13108429 18468915 296795338 282907012 207909366 2192548...
output:
1967193239
result:
ok single line: '1967193239'
Test #49:
score: 30
Accepted
time: 1ms
memory: 3600kb
input:
1000000000 1000000000 25 508699723 917649746 972134563 24654272 591574312 768222747 342111766 678842208 280650655 335101574 112108587 538128714 232733100 741988808 569340416 313541403 333183415 646381341 348331220 239049882 321253252 46884019 458715217 456559440 11396102 588839952 212356188 55359081...
output:
967430445
result:
ok single line: '967430445'
Test #50:
score: 30
Accepted
time: 0ms
memory: 3892kb
input:
1000000000 1000000000 25 87500002 928571428 712500002 71428571 212500002 71428570 837500001 71428573 912499999 214285715 287500002 785714285 37500003 785714285 962500002 357142856 787500000 785714288 787500003 500000003 462500002 71428570 462500001 357142859 37499999 500000000 462500002 642857144 37...
output:
660714282
result:
ok single line: '660714282'
Test #51:
score: 30
Accepted
time: 1ms
memory: 3672kb
input:
1000000000 1000000000 25 499999999 565789472 499999990 250000002 499999996 749999995 499999999 144736850 499999993 513157893 499999992 644736853 500000010 13157889 499999998 118421056 499999993 197368414 499999990 592105269 499999994 486842107 500000005 276315783 499999994 539473685 499999990 618421...
output:
1131578975
result:
ok single line: '1131578975'
Test #52:
score: 30
Accepted
time: 0ms
memory: 3576kb
input:
999999999 777777777 25 777772259 317438734 467526694 324943812 750092374 316807230 351488629 328182224 670366487 319838016 194662876 330078646 807706262 316391102 682779230 318750710 529347725 323684686 437218310 325726470 284055780 328324426 156380921 332766879 754204172 318252081 631742119 3197068...
output:
1086358403
result:
ok single line: '1086358403'
Test #53:
score: 30
Accepted
time: 0ms
memory: 3672kb
input:
100000000 1000000000 25 75997424 820728673 777782 777777776 777783 777777777 777780 777777778 18626903 845305698 32700264 518597334 66223561 813120928 92237121 497548369 66359837 477082113 51360029 493816356 777776 777777775 777778 777777776 77907935 347786430 777776 777777776 777779 777777786 77777...
output:
434734665
result:
ok single line: '434734665'
Test #54:
score: 30
Accepted
time: 1ms
memory: 3604kb
input:
1000000000 1000000000 25 202384720 191386798 272784910 876112960 134295596 689831109 144607550 725288401 304962179 141608855 184056836 214149818 580684614 928741905 339656490 906353399 222518718 825019927 65386126 415917878 836363213 211099284 885557581 342429798 772605154 167160669 750597218 865168...
output:
1169492481
result:
ok single line: '1169492481'
Test #55:
score: 30
Accepted
time: 1ms
memory: 3672kb
input:
1000000000 1000000000 25 217898725 381443931 363716745 553078122 741451918 906975033 153568070 900704450 12302872 385341608 276235760 349179186 221511192 438759684 177246208 108385423 157609379 88135252 542559523 122476619 676920172 289023879 132864371 527493734 980440215 892433157 465353007 9681278...
output:
936384704
result:
ok single line: '936384704'
Test #56:
score: 30
Accepted
time: 1ms
memory: 3656kb
input:
1000000000 1000000000 25 108777360 996968244 655575871 74556270 426116462 624297074 601010849 48108108 411143918 863537296 176018437 125264437 769284398 653206473 823951690 375380635 675138657 124417631 305117857 433890179 878598110 72028431 322847356 902439915 323815174 873868901 575209775 37455562...
output:
603034352
result:
ok single line: '603034352'
Test #57:
score: 30
Accepted
time: 0ms
memory: 3656kb
input:
335563010 332545567 25 106441293 332545567 117303130 332545567 335563010 272104540 335563010 47336793 335563010 171741328 315104367 332545567 335563010 258033462 174568335 332545567 170964494 332545567 335563010 68594399 304935196 332545567 97310526 332545567 99941575 332545567 12373018 332545567 33...
output:
389908846
result:
ok single line: '389908846'
Test #58:
score: 0
Wrong Answer
time: 0ms
memory: 3616kb
input:
1000000000 1000000000 25 786394982 791216768 119431195 847633609 81087720 1 264330507 432964753 737246186 427050407 922213406 555980523 550982306 581735630 1 1 852080288 1 1 538609505 375220500 773780706 182457491 294843990 1 634980243 421417169 1 253676052 1 601408832 610485554 957268112 249030717 ...
output:
886822710
result:
wrong answer 1st lines differ - expected: '905880429', found: '886822710'
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
100%
Accepted
Dependency #4:
0%