oj.uz

Submission #692934

# Submission time Handle Problem Language Result Execution time Memory
692934 2023-02-02T07:35:38 Z saayan007 Visiting Singapore (NOI20_visitingsingapore) C++17
24 / 100
 494 ms 844 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pi>;
using vpl = vector<pl>;

#define fur(i, a, b) for(ll i = a; i <= (ll) b; ++i)
#define ruf(i, a, b) for(ll i = a; i >= (ll) b; --i)
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define nl "\n"

const ll inf = 1e15L;

ll cost(ll y) {
    ll ans = 0;
    ans += y % 2;
    y /= 2;
    ans += y % 2;
    return ans;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll k, n, m, a, b;
    cin >> k >> n >> m >> a >> b;
    a = -a;
    b = -b;

    ll v[k + 1], s[n + 1], t[m + 1];

    fur(i, 1, k) {
        cin >> v[i];
    }
    fur(i, 1, n) {
        cin >> s[i];
    }
    fur(i, 1, m) {
        cin >> t[i];
    }

    ll dp[2][m + 1][4];
    fur(i, 0, 1)
        fur(j, 0, m)
            fur(x, 0, 3)
                dp[i][j][x] = -inf;

    ll res = -a;

    fur(i, 1, n) {
        ll cur = i % 2;
        ll prv = 1 - cur;
        fur(j, 1, m) {
            if(s[i] == t[j]) {
                fur(y, 0, 3) {
                    dp[cur][j][3] = max({dp[cur][j][3], dp[prv][j - 1][y] + v[t[j]], v[t[j]] - a * (j > 1ll ? 1ll : 0ll)});
                    res = max(res, dp[cur][j][3] - a * (j < m ? 1ll : 0ll));
                }
            }

            dp[cur][j][0] = max({dp[cur][j][0], dp[prv][j][0], dp[prv][j][2] - a, dp[cur][j - 1][0], dp[cur][j - 1][1] - a});
            fur(y, 0, 3) {
                dp[cur][j][0] = max(dp[cur][j][0], dp[prv][j - 1][y] - a * cost(y));
            }
            dp[cur][j][1] = max({dp[cur][j][1], dp[prv][j][1], dp[prv][j][3] - a});
            dp[cur][j][2] = max({dp[cur][j][2], dp[cur][j - 1][2], dp[cur][j - 1][3] - a});
        }

        fur(j, 0, m) {
            fur(x, 0, 3) {
                dp[prv][j][x] = -inf;
            }
        }
    }
    cout << res << nl;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 19 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 10 ms 468 KB Output is correct
10 Correct 21 ms 340 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 400 KB Output is correct
2 Correct 13 ms 372 KB Output is correct
3 Correct 108 ms 472 KB Output is correct
4 Correct 255 ms 644 KB Output is correct
5 Correct 78 ms 596 KB Output is correct
6 Correct 111 ms 468 KB Output is correct
7 Correct 202 ms 568 KB Output is correct
8 Correct 73 ms 436 KB Output is correct
9 Correct 136 ms 572 KB Output is correct
10 Correct 320 ms 692 KB Output is correct
11 Correct 320 ms 684 KB Output is correct
12 Correct 320 ms 700 KB Output is correct
13 Correct 323 ms 692 KB Output is correct
14 Correct 491 ms 688 KB Output is correct
15 Correct 491 ms 692 KB Output is correct

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 400 KB Output is correct
2 Correct 13 ms 372 KB Output is correct
3 Correct 108 ms 472 KB Output is correct
4 Correct 255 ms 644 KB Output is correct
5 Correct 78 ms 596 KB Output is correct
6 Correct 111 ms 468 KB Output is correct
7 Correct 202 ms 568 KB Output is correct
8 Correct 73 ms 436 KB Output is correct
9 Correct 136 ms 572 KB Output is correct
10 Correct 320 ms 692 KB Output is correct
11 Correct 320 ms 684 KB Output is correct
12 Correct 320 ms 700 KB Output is correct
13 Correct 323 ms 692 KB Output is correct
14 Correct 491 ms 688 KB Output is correct
15 Correct 491 ms 692 KB Output is correct
16 Incorrect 166 ms 468 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 400 KB Output is correct
2 Correct 13 ms 372 KB Output is correct
3 Correct 108 ms 472 KB Output is correct
4 Correct 255 ms 644 KB Output is correct
5 Correct 78 ms 596 KB Output is correct
6 Correct 111 ms 468 KB Output is correct
7 Correct 202 ms 568 KB Output is correct
8 Correct 73 ms 436 KB Output is correct
9 Correct 136 ms 572 KB Output is correct
10 Correct 320 ms 692 KB Output is correct
11 Correct 320 ms 684 KB Output is correct
12 Correct 320 ms 700 KB Output is correct
13 Correct 323 ms 692 KB Output is correct
14 Correct 491 ms 688 KB Output is correct
15 Correct 491 ms 692 KB Output is correct
16 Correct 277 ms 632 KB Output is correct
17 Correct 133 ms 500 KB Output is correct
18 Correct 40 ms 488 KB Output is correct
19 Correct 11 ms 388 KB Output is correct
20 Correct 5 ms 340 KB Output is correct
21 Correct 8 ms 596 KB Output is correct
22 Correct 128 ms 596 KB Output is correct
23 Correct 25 ms 340 KB Output is correct
24 Correct 220 ms 596 KB Output is correct
25 Correct 315 ms 744 KB Output is correct
26 Correct 320 ms 720 KB Output is correct
27 Correct 316 ms 844 KB Output is correct
28 Correct 314 ms 732 KB Output is correct
29 Correct 486 ms 596 KB Output is correct
30 Correct 494 ms 704 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 19 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 5 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 10 ms 468 KB Output is correct
10 Correct 21 ms 340 KB Output is correct
11 Incorrect 1 ms 340 KB Output isn't correct
12 Halted 0 ms 0 KB -