oj.uz

Submission #693256

# Submission time Handle Problem Language Result Execution time Memory
693256 2023-02-02T14:00:34 Z true22 Visiting Singapore (NOI20_visitingsingapore) C++14
16 / 100
 199 ms 195868 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long int ll;
typedef long double ld;

typedef pair<ll, ll> pl;
typedef vector<ll> vl;   
typedef vector<pl> vp;

#define nl "\n"
#define fr first
#define sc second
#define pb push_back

#define all(x) x.begin(), x.end()
#define fur(i, a, b) for(ll i = a; i <= b; ++i)
#define ruf(i, a, b) for(ll i = a; i >= b; --i)
#define pv(x) for(auto k : x){cout << k << " ";} cout << nl

const ll inf = 1e17;

ll K, n, m, A, B;
vl val, s, t;

/*
    There are K types of events
    We know the values of each type of event
    N of them will occur
    M of them you want to attend (in the given order, you can attend a type of event more than once)
    if you miss x consecutive normal events, you will lose points
    if you miss x consecutive special events, you will lose points
    now, what is the maximum score you can get?
*/

void solve(){
    // a = b = 0;
    ll dp[n + 1][m + 1];
    fur(i, 0, n)
        fur(j, 0, m)
            dp[i][j] = -inf;
    fur(i, 0, n)
        dp[i][0] = 0;
    fur(i, 0, m)
        dp[0][i] = 0;
    
    fur(i, 1, n){
        fur(j, 1, m){
            if (s[i] == t[j])
                dp[i][j] = val[t[j]] + dp[i-1][j-1];
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    cout << dp[n][m] << nl;
}

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

    cin >> K >> n >> m >> A >> B;
    val.resize(K + 1);
    s.resize(n + 1);
    t.resize(m + 1);
    fur(i, 1, K)
        cin >> val[i];
    fur(i, 1, n)
        cin >> s[i];
    fur(i, 1, m)
        cin >> t[i];

    
    solve();

    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 4 ms 6868 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 2 ms 2132 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 2 ms 3924 KB Output is correct
10 Correct 5 ms 8148 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 19 ms 19260 KB Output is correct
2 Correct 8 ms 7920 KB Output is correct
3 Correct 58 ms 64572 KB Output is correct
4 Correct 146 ms 156420 KB Output is correct
5 Correct 42 ms 45652 KB Output is correct
6 Correct 61 ms 66496 KB Output is correct
7 Correct 115 ms 124480 KB Output is correct
8 Correct 39 ms 40712 KB Output is correct
9 Correct 80 ms 79844 KB Output is correct
10 Correct 171 ms 195200 KB Output is correct
11 Correct 172 ms 194804 KB Output is correct
12 Correct 199 ms 195788 KB Output is correct
13 Correct 182 ms 195868 KB Output is correct
14 Correct 133 ms 195532 KB Output is correct
15 Correct 130 ms 195276 KB Output is correct

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19260 KB Output is correct
2 Correct 8 ms 7920 KB Output is correct
3 Correct 58 ms 64572 KB Output is correct
4 Correct 146 ms 156420 KB Output is correct
5 Correct 42 ms 45652 KB Output is correct
6 Correct 61 ms 66496 KB Output is correct
7 Correct 115 ms 124480 KB Output is correct
8 Correct 39 ms 40712 KB Output is correct
9 Correct 80 ms 79844 KB Output is correct
10 Correct 171 ms 195200 KB Output is correct
11 Correct 172 ms 194804 KB Output is correct
12 Correct 199 ms 195788 KB Output is correct
13 Correct 182 ms 195868 KB Output is correct
14 Correct 133 ms 195532 KB Output is correct
15 Correct 130 ms 195276 KB Output is correct
16 Incorrect 93 ms 101996 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 19260 KB Output is correct
2 Correct 8 ms 7920 KB Output is correct
3 Correct 58 ms 64572 KB Output is correct
4 Correct 146 ms 156420 KB Output is correct
5 Correct 42 ms 45652 KB Output is correct
6 Correct 61 ms 66496 KB Output is correct
7 Correct 115 ms 124480 KB Output is correct
8 Correct 39 ms 40712 KB Output is correct
9 Correct 80 ms 79844 KB Output is correct
10 Correct 171 ms 195200 KB Output is correct
11 Correct 172 ms 194804 KB Output is correct
12 Correct 199 ms 195788 KB Output is correct
13 Correct 182 ms 195868 KB Output is correct
14 Correct 133 ms 195532 KB Output is correct
15 Correct 130 ms 195276 KB Output is correct
16 Incorrect 147 ms 162836 KB Output isn't correct
17 Halted 0 ms 0 KB -

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 0 ms 340 KB Output is correct
2 Correct 4 ms 6868 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 2 ms 2132 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 2 ms 3924 KB Output is correct
10 Correct 5 ms 8148 KB Output is correct
11 Incorrect 1 ms 340 KB Output isn't correct
12 Halted 0 ms 0 KB -