oj.uz

Submission #545300

# Submission time Handle Problem Language Result Execution time Memory
545300 2022-04-04T08:20:52 Z balbit Visiting Singapore (NOI20_visitingsingapore) C++14
23 / 100
 79 ms 716 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][2][maxn][2];

signed main(){
    IOS();
    int K,n,m,A,B;
    cin>>K>>n>>m>>A>>B;
    REP1(i,K) cin>>V[i];
    REP1(i,n) cin>>S[i];
    REP1(i,m) cin>>T[i];

    REP(a,2)REP(b,maxn)REP(c,2) dp[0][a][b][c] = -inf;

    dp[0][1][0][1] = 0;
    // calculate cost of not even visiting singapore
    ll re = (A + B*m);

    REP1(i,n) {
        int I = i%2;
        REP(a,2)REP(b,maxn)REP(c,2) dp[I][a][b][c] = -inf;
        dp[I][1][0][1] = 0;

        REP1(j, m) {
            if (T[j] == S[i]) {
                // take
                REP(f1, 2) REP(f2, 2) if (dp[I^1][f1][j-1][f2] != -inf) MX(dp[I][1][j][1], V[T[j]] + dp[I^1][f1][j-1][f2]);
            }
            // sacrifice S
            REP(f2, 2) {
                MX(dp[I][0][j][f2], dp[I^1][1][j][f2] + A+B);
                MX(dp[I][0][j][f2], dp[I^1][0][j][f2] + 0+B);
            }

            // sacrifice T
            REP(f1, 2) {
                MX(dp[I][f1][j][0], dp[I][f1][j-1][1] + A + B);
                MX(dp[I][f1][j][0], dp[I][f1][j-1][0] + 0 + B);
            }
        }

        // extract dp[i][?][m][?]
        REP(f1,2)REP(f2,2) {
            MX(re, dp[I][f1][m][f2]);
        }
    }
    cout<<re<<endl;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 18 ms 596 KB Output is correct
3 Correct 3 ms 644 KB Output is correct
4 Correct 7 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 9 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 14 ms 656 KB Output is correct
10 Correct 21 ms 596 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 6 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 11 ms 596 KB Output is correct
7 Correct 11 ms 660 KB Output is correct
8 Correct 15 ms 660 KB Output is correct
9 Correct 3 ms 644 KB Output is correct
10 Correct 20 ms 668 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 668 KB Output is correct
2 Correct 24 ms 596 KB Output is correct
3 Incorrect 79 ms 716 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 668 KB Output is correct
2 Correct 24 ms 596 KB Output is correct
3 Incorrect 79 ms 716 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 668 KB Output is correct
2 Correct 24 ms 596 KB Output is correct
3 Incorrect 79 ms 716 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 18 ms 596 KB Output is correct
3 Correct 3 ms 644 KB Output is correct
4 Correct 7 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 9 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 14 ms 656 KB Output is correct
10 Correct 21 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 6 ms 596 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 3 ms 596 KB Output is correct
16 Correct 11 ms 596 KB Output is correct
17 Correct 11 ms 660 KB Output is correct
18 Correct 15 ms 660 KB Output is correct
19 Correct 3 ms 644 KB Output is correct
20 Correct 20 ms 668 KB Output is correct
21 Correct 40 ms 668 KB Output is correct
22 Correct 24 ms 596 KB Output is correct
23 Incorrect 79 ms 716 KB Output isn't correct
24 Halted 0 ms 0 KB -