zinoviev's blog

By zinoviev, history, 3 weeks ago, translation, In English,

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#7 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_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.e1;
}

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 UPD: It was very stupid mistake in comparator. I got AC, code above is correct.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zinoviev (previous revision, new revision, compare).

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

If $$$j = s_1$$$, you shouldn't make a transition in your solution (just guessing).

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you, I thinked about it and got it. My previous solution tried to use quest overflow even if you reached $$$s_1$$$ experience. I fixed it and now I have WA#7. It is better tho

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Are you sure that your comparator is correct? Shouldn't it be $$$q_1.e_1 < q_2.e_1$$$?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh my.. It was very stupid and unexpected. Thank you, I managed to got AC. Thank you again

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by zinoviev (previous revision, new revision, compare).