oj.uz

Submission #545306

# Submission time Handle Problem Language Result Execution time Memory
545306 2022-04-04T08:36:00 Z balbit Visiting Singapore (NOI20_visitingsingapore) C++14
12 / 100
 121 ms 480 KB 
#include <bits/stdc++.h>
#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 5005+5;

ll V[maxn], S[maxn], T[maxn];
ll dp[2][maxn];

signed main(){
    IOS();
    int K,n,m,A,B;
    cin>>K>>n>>m>>A>>B;
    assert(A == 0 && B == 0);

    REP1(i,K) cin>>V[i];
    REP1(i,n) cin>>S[i];
    REP1(i,m) cin>>T[i];

//    dp[0][1][0][1] = 0;-
    // calculate cost of not even visiting singapore
//    ll re = (A + B*m);
    ll re = 0;
    REP1(i,n) {
        int I = i%2;
        REP1(j,m) {
            dp[I][j] = -inf;
            dp[I][j] = max(dp[I^1][j], dp[I][j-1]);
            if (S[i] == T[j]) {
                MX(dp[I][j], dp[I^1][j-1] + V[S[i]]);
            }
            MX(re, dp[I][j]);
        }
    }
    cout<<re<<endl;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 388 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 29 ms 340 KB Output is correct
4 Correct 76 ms 468 KB Output is correct
5 Correct 23 ms 452 KB Output is correct
6 Correct 33 ms 340 KB Output is correct
7 Correct 59 ms 440 KB Output is correct
8 Correct 20 ms 340 KB Output is correct
9 Correct 38 ms 448 KB Output is correct
10 Correct 91 ms 468 KB Output is correct
11 Correct 97 ms 480 KB Output is correct
12 Correct 90 ms 480 KB Output is correct
13 Correct 90 ms 468 KB Output is correct
14 Correct 119 ms 476 KB Output is correct
15 Correct 121 ms 476 KB Output is correct

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 388 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 29 ms 340 KB Output is correct
4 Correct 76 ms 468 KB Output is correct
5 Correct 23 ms 452 KB Output is correct
6 Correct 33 ms 340 KB Output is correct
7 Correct 59 ms 440 KB Output is correct
8 Correct 20 ms 340 KB Output is correct
9 Correct 38 ms 448 KB Output is correct
10 Correct 91 ms 468 KB Output is correct
11 Correct 97 ms 480 KB Output is correct
12 Correct 90 ms 480 KB Output is correct
13 Correct 90 ms 468 KB Output is correct
14 Correct 119 ms 476 KB Output is correct
15 Correct 121 ms 476 KB Output is correct
16 Runtime error 1 ms 468 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 388 KB Output is correct
2 Correct 4 ms 340 KB Output is correct
3 Correct 29 ms 340 KB Output is correct
4 Correct 76 ms 468 KB Output is correct
5 Correct 23 ms 452 KB Output is correct
6 Correct 33 ms 340 KB Output is correct
7 Correct 59 ms 440 KB Output is correct
8 Correct 20 ms 340 KB Output is correct
9 Correct 38 ms 448 KB Output is correct
10 Correct 91 ms 468 KB Output is correct
11 Correct 97 ms 480 KB Output is correct
12 Correct 90 ms 480 KB Output is correct
13 Correct 90 ms 468 KB Output is correct
14 Correct 119 ms 476 KB Output is correct
15 Correct 121 ms 476 KB Output is correct
16 Runtime error 1 ms 468 KB Execution killed with signal 6
17 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -