Hello everyone. I am stuck with upsolving problem B from SEERC-2019. Problem statement
Even after reading editorials and realizing that my solution seems correct, I keep getting WA#5 on codeforces. I am doing dp, like described in editorial, 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_1]$$$.
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 + 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!