oj.uz

Submission #545294

# Submission time Handle Problem Language Result Execution time Memory
545294 2022-04-04T08:06:00 Z balbit Visiting Singapore (NOI20_visitingsingapore) C++14
23 / 100
 81 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) 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 3 ms 596 KB Output is correct
2 Correct 17 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 10 ms 596 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 8 ms 664 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 5 ms 660 KB Output is correct
9 Correct 10 ms 588 KB Output is correct
10 Correct 18 ms 672 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 5 ms 672 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 13 ms 716 KB Output is correct
7 Correct 12 ms 596 KB Output is correct
8 Correct 14 ms 596 KB Output is correct
9 Correct 3 ms 596 KB Output is correct
10 Correct 18 ms 672 KB Output is correct

Subtask #3
0 / 12.0

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

Subtask #4
0 / 7.0

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

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 596 KB Output is correct
2 Correct 24 ms 596 KB Output is correct
3 Incorrect 81 ms 596 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 588 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 584 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 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 2 ms 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 2 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 3 ms 596 KB Output is correct
2 Correct 17 ms 596 KB Output is correct
3 Correct 3 ms 596 KB Output is correct
4 Correct 10 ms 596 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 8 ms 664 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 5 ms 660 KB Output is correct
9 Correct 10 ms 588 KB Output is correct
10 Correct 18 ms 672 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 5 ms 672 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 3 ms 596 KB Output is correct
16 Correct 13 ms 716 KB Output is correct
17 Correct 12 ms 596 KB Output is correct
18 Correct 14 ms 596 KB Output is correct
19 Correct 3 ms 596 KB Output is correct
20 Correct 18 ms 672 KB Output is correct
21 Correct 34 ms 596 KB Output is correct
22 Correct 24 ms 596 KB Output is correct
23 Incorrect 81 ms 596 KB Output isn't correct
24 Halted 0 ms 0 KB -