oj.uz

Submission #545307

# Submission time Handle Problem Language Result Execution time Memory
545307 2022-04-04T08:36:31 Z balbit Visiting Singapore (NOI20_visitingsingapore) C++14
16 / 100
 265 ms 724 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;
//    assert(A == 0 && B == 0);

    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] = 0;

    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] = 0;
        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[S[i]] + 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 15 ms 664 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 7 ms 596 KB Output is correct
5 Correct 4 ms 648 KB Output is correct
6 Correct 8 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 11 ms 652 KB Output is correct
10 Correct 18 ms 596 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 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 40 ms 596 KB Output is correct
2 Correct 25 ms 596 KB Output is correct
3 Correct 85 ms 596 KB Output is correct
4 Correct 150 ms 596 KB Output is correct
5 Correct 47 ms 596 KB Output is correct
6 Correct 73 ms 672 KB Output is correct
7 Correct 138 ms 696 KB Output is correct
8 Correct 57 ms 596 KB Output is correct
9 Correct 85 ms 688 KB Output is correct
10 Correct 200 ms 696 KB Output is correct
11 Correct 194 ms 708 KB Output is correct
12 Correct 181 ms 704 KB Output is correct
13 Correct 204 ms 724 KB Output is correct
14 Correct 260 ms 716 KB Output is correct
15 Correct 265 ms 696 KB Output is correct

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 596 KB Output is correct
2 Correct 25 ms 596 KB Output is correct
3 Correct 85 ms 596 KB Output is correct
4 Correct 150 ms 596 KB Output is correct
5 Correct 47 ms 596 KB Output is correct
6 Correct 73 ms 672 KB Output is correct
7 Correct 138 ms 696 KB Output is correct
8 Correct 57 ms 596 KB Output is correct
9 Correct 85 ms 688 KB Output is correct
10 Correct 200 ms 696 KB Output is correct
11 Correct 194 ms 708 KB Output is correct
12 Correct 181 ms 704 KB Output is correct
13 Correct 204 ms 724 KB Output is correct
14 Correct 260 ms 716 KB Output is correct
15 Correct 265 ms 696 KB Output is correct
16 Incorrect 114 ms 696 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 596 KB Output is correct
2 Correct 25 ms 596 KB Output is correct
3 Correct 85 ms 596 KB Output is correct
4 Correct 150 ms 596 KB Output is correct
5 Correct 47 ms 596 KB Output is correct
6 Correct 73 ms 672 KB Output is correct
7 Correct 138 ms 696 KB Output is correct
8 Correct 57 ms 596 KB Output is correct
9 Correct 85 ms 688 KB Output is correct
10 Correct 200 ms 696 KB Output is correct
11 Correct 194 ms 708 KB Output is correct
12 Correct 181 ms 704 KB Output is correct
13 Correct 204 ms 724 KB Output is correct
14 Correct 260 ms 716 KB Output is correct
15 Correct 265 ms 696 KB Output is correct
16 Incorrect 180 ms 596 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 15 ms 664 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 7 ms 596 KB Output is correct
5 Correct 4 ms 648 KB Output is correct
6 Correct 8 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 11 ms 652 KB Output is correct
10 Correct 18 ms 596 KB Output is correct
11 Incorrect 1 ms 596 KB Output isn't correct
12 Halted 0 ms 0 KB -