Hello everyone.↵
I am stuck with upsolving problem B from SEERC-2019.↵
[Problem statement](https://codeforces.net/group/77EwhNiBEM/contest/256946/problem/B)↵
↵
Even after reading editorials and realizing that my solution seems correct, I keep getting[WA#5](https://codeforces.net/group/77EwhNiBEM/contest/256946/submission/63088809)7 on codeforces.↵
I am doing dp, like described in [editorial](https://oi.in.ua/wp-content/uploads/2019/10/seerc-2019-editorial.pdf), and sorting all quest before by $x_i$. I am using $dp[j][k]$ array and $tmp[j][k]$ array on every iteration because I need to use every quest at most one time. So I am doing optimization on $tmp$ array, and then copy its contents back to $dp$. Then answer should be at $dp[s_1][s_2]$.↵
↵
I`ll be very glad if someone more experienced than me could help me find the test, where my solution fails or maybe just give me some hints.↵
↵
My code:↵
↵
~~~~~↵
struct q {↵
ll e1, e2, t1, t2;↵
};↵
↵
bool cmp(q q1, q q2) {↵
return q1.e1 < q2.e2;↵
}↵
↵
ll tmp[501][501];↵
ll dp[501][501];↵
ll n, s1, s2;↵
↵
#define chkmin(x, y) (x) == -1 ? (x) = (y) : (x) = min((x), (y))↵
↵
void solve() {↵
cin >> n >> s1 >> s2;↵
vector<q> v(n);↵
for (int i = 0; i < n; i++)↵
cin >> v[i].e1 >> v[i].t1 >> v[i].e2 >> v[i].t2;↵
sort(all(v), cmp);↵
for (int j = 0; j <= s1; j++)↵
for (int k = 0; k <= s2; k++)↵
dp[j][k] = j == 0 && k == 0 ? 0 : -1;↵
↵
for (int i = 0; i < n; i++) {↵
for (int j = 0; j <= s1; j++)↵
for (int k = 0; k <= s2; k++)↵
tmp[j][k] = dp[j][k];↵
↵
for (int j = 0; j <= s1; j++)↵
for (int k = 0; k <= s2; k++) {↵
if (dp[j][k] == -1)↵
continue;↵
if (j != s1) {↵
if (j + v[i].e1 <= s1)↵
chkmin(tmp[j + v[i].e1][k], dp[j][k] + v[i].t1);↵
else↵
chkmin(tmp[s1][min(k + (j + v[i].e1 - s1), s2)], dp[j][k] + v[i].t1);↵
}↵
chkmin(tmp[j][min(k + v[i].e2, s2)], dp[j][k] + v[i].t2);↵
}↵
↵
for (int j = 0; j <= s1; j++)↵
for (int k = 0; k <= s2; k++)↵
dp[j][k] = tmp[j][k];↵
}↵
cout << dp[s1][s2] << endl;↵
}↵
~~~~~↵
↵
Thank you!↵
↵
UPD: Fixed bug with $j = s_1$, now it is WA#7
I am stuck with upsolving problem B from SEERC-2019.↵
[Problem statement](https://codeforces.net/group/77EwhNiBEM/contest/256946/problem/B)↵
↵
Even after reading editorials and realizing that my solution seems correct, I keep getting
I am doing dp, like described in [editorial](https://oi.in.ua/wp-content/uploads/2019/10/seerc-2019-editorial.pdf), and sorting all quest before by $x_i$. I am using $dp[j][k]$ array and $tmp[j][k]$ array on every iteration because I need to use every quest at most one time. So I am doing optimization on $tmp$ array, and then copy its contents back to $dp$. Then answer should be at $dp[s_1][s_2]$.↵
↵
I`ll be very glad if someone more experienced than me could help me find the test, where my solution fails or maybe just give me some hints.↵
↵
My code:↵
↵
~~~~~↵
struct q {↵
ll e1, e2, t1, t2;↵
};↵
↵
bool cmp(q q1, q q2) {↵
return q1.e1 < q2.e2;↵
}↵
↵
ll tmp[501][501];↵
ll dp[501][501];↵
ll n, s1, s2;↵
↵
#define chkmin(x, y) (x) == -1 ? (x) = (y) : (x) = min((x), (y))↵
↵
void solve() {↵
cin >> n >> s1 >> s2;↵
vector<q> v(n);↵
for (int i = 0; i < n; i++)↵
cin >> v[i].e1 >> v[i].t1 >> v[i].e2 >> v[i].t2;↵
sort(all(v), cmp);↵
for (int j = 0; j <= s1; j++)↵
for (int k = 0; k <= s2; k++)↵
dp[j][k] = j == 0 && k == 0 ? 0 : -1;↵
↵
for (int i = 0; i < n; i++) {↵
for (int j = 0; j <= s1; j++)↵
for (int k = 0; k <= s2; k++)↵
tmp[j][k] = dp[j][k];↵
↵
for (int j = 0; j <= s1; j++)↵
for (int k = 0; k <= s2; k++) {↵
if (dp[j][k] == -1)↵
continue;↵
if (j != s1) {↵
if (j + v[i].e1 <= s1)↵
chkmin(tmp[j + v[i].e1][k], dp[j][k] + v[i].t1);↵
else↵
chkmin(tmp[s1][min(k + (j + v[i].e1 - s1), s2)], dp[j][k] + v[i].t1);↵
}↵
chkmin(tmp[j][min(k + v[i].e2, s2)], dp[j][k] + v[i].t2);↵
}↵
↵
for (int j = 0; j <= s1; j++)↵
for (int k = 0; k <= s2; k++)↵
dp[j][k] = tmp[j][k];↵
}↵
cout << dp[s1][s2] << endl;↵
}↵
~~~~~↵
↵
Thank you!↵
↵
UPD: Fixed bug with $j = s_1$, now it is WA#7
