oj.uz

Submission #545305

# Submission time Handle Problem Language Result Execution time Memory
545305 2022-04-04T08:24:52 Z balbit Visiting Singapore (NOI20_visitingsingapore) C++14
12 / 100
 182 ms 196312 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[maxn][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);

    REP1(i,n) {
        REP1(j,m) {
            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]]);
            }
        }
    }
    cout<<dp[n][m]<<endl;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 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 4 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 21 ms 29908 KB Output is correct
2 Correct 12 ms 18080 KB Output is correct
3 Correct 59 ms 79780 KB Output is correct
4 Correct 147 ms 174304 KB Output is correct
5 Correct 42 ms 51404 KB Output is correct
6 Correct 58 ms 76200 KB Output is correct
7 Correct 107 ms 143444 KB Output is correct
8 Correct 41 ms 54860 KB Output is correct
9 Correct 75 ms 91340 KB Output is correct
10 Correct 152 ms 196268 KB Output is correct
11 Correct 150 ms 195692 KB Output is correct
12 Correct 157 ms 196224 KB Output is correct
13 Correct 158 ms 196196 KB Output is correct
14 Correct 176 ms 196312 KB Output is correct
15 Correct 182 ms 196308 KB Output is correct

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 29908 KB Output is correct
2 Correct 12 ms 18080 KB Output is correct
3 Correct 59 ms 79780 KB Output is correct
4 Correct 147 ms 174304 KB Output is correct
5 Correct 42 ms 51404 KB Output is correct
6 Correct 58 ms 76200 KB Output is correct
7 Correct 107 ms 143444 KB Output is correct
8 Correct 41 ms 54860 KB Output is correct
9 Correct 75 ms 91340 KB Output is correct
10 Correct 152 ms 196268 KB Output is correct
11 Correct 150 ms 195692 KB Output is correct
12 Correct 157 ms 196224 KB Output is correct
13 Correct 158 ms 196196 KB Output is correct
14 Correct 176 ms 196312 KB Output is correct
15 Correct 182 ms 196308 KB Output is correct
16 Runtime error 6 ms 472 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 21 ms 29908 KB Output is correct
2 Correct 12 ms 18080 KB Output is correct
3 Correct 59 ms 79780 KB Output is correct
4 Correct 147 ms 174304 KB Output is correct
5 Correct 42 ms 51404 KB Output is correct
6 Correct 58 ms 76200 KB Output is correct
7 Correct 107 ms 143444 KB Output is correct
8 Correct 41 ms 54860 KB Output is correct
9 Correct 75 ms 91340 KB Output is correct
10 Correct 152 ms 196268 KB Output is correct
11 Correct 150 ms 195692 KB Output is correct
12 Correct 157 ms 196224 KB Output is correct
13 Correct 158 ms 196196 KB Output is correct
14 Correct 176 ms 196312 KB Output is correct
15 Correct 182 ms 196308 KB Output is correct
16 Runtime error 4 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 3 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 5 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -