oj.uz

Submission #545310

# Submission time Handle Problem Language Result Execution time Memory
545310 2022-04-04T08:39:07 Z balbit Visiting Singapore (NOI20_visitingsingapore) C++14
16 / 100
 301 ms 852 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] = -inf;
        if (a == 1 && c == 1) 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] = -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[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 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 7 ms 648 KB Output is correct
5 Correct 4 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 6 ms 652 KB Output is correct
9 Correct 10 ms 596 KB Output is correct
10 Correct 17 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 44 ms 596 KB Output is correct
2 Correct 28 ms 596 KB Output is correct
3 Correct 78 ms 596 KB Output is correct
4 Correct 150 ms 704 KB Output is correct
5 Correct 49 ms 668 KB Output is correct
6 Correct 75 ms 680 KB Output is correct
7 Correct 133 ms 716 KB Output is correct
8 Correct 55 ms 676 KB Output is correct
9 Correct 84 ms 684 KB Output is correct
10 Correct 223 ms 700 KB Output is correct
11 Correct 181 ms 704 KB Output is correct
12 Correct 188 ms 704 KB Output is correct
13 Correct 195 ms 704 KB Output is correct
14 Correct 290 ms 704 KB Output is correct
15 Correct 301 ms 852 KB Output is correct

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 596 KB Output is correct
2 Correct 28 ms 596 KB Output is correct
3 Correct 78 ms 596 KB Output is correct
4 Correct 150 ms 704 KB Output is correct
5 Correct 49 ms 668 KB Output is correct
6 Correct 75 ms 680 KB Output is correct
7 Correct 133 ms 716 KB Output is correct
8 Correct 55 ms 676 KB Output is correct
9 Correct 84 ms 684 KB Output is correct
10 Correct 223 ms 700 KB Output is correct
11 Correct 181 ms 704 KB Output is correct
12 Correct 188 ms 704 KB Output is correct
13 Correct 195 ms 704 KB Output is correct
14 Correct 290 ms 704 KB Output is correct
15 Correct 301 ms 852 KB Output is correct
16 Incorrect 112 ms 692 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 596 KB Output is correct
2 Correct 28 ms 596 KB Output is correct
3 Correct 78 ms 596 KB Output is correct
4 Correct 150 ms 704 KB Output is correct
5 Correct 49 ms 668 KB Output is correct
6 Correct 75 ms 680 KB Output is correct
7 Correct 133 ms 716 KB Output is correct
8 Correct 55 ms 676 KB Output is correct
9 Correct 84 ms 684 KB Output is correct
10 Correct 223 ms 700 KB Output is correct
11 Correct 181 ms 704 KB Output is correct
12 Correct 188 ms 704 KB Output is correct
13 Correct 195 ms 704 KB Output is correct
14 Correct 290 ms 704 KB Output is correct
15 Correct 301 ms 852 KB Output is correct
16 Correct 174 ms 692 KB Output is correct
17 Correct 110 ms 716 KB Output is correct
18 Correct 28 ms 596 KB Output is correct
19 Correct 13 ms 680 KB Output is correct
20 Correct 5 ms 596 KB Output is correct
21 Correct 5 ms 640 KB Output is correct
22 Correct 82 ms 724 KB Output is correct
23 Correct 25 ms 596 KB Output is correct
24 Correct 146 ms 724 KB Output is correct
25 Correct 184 ms 772 KB Output is correct
26 Correct 205 ms 748 KB Output is correct
27 Correct 190 ms 724 KB Output is correct
28 Correct 195 ms 732 KB Output is correct
29 Incorrect 301 ms 732 KB Output isn't correct
30 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 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 7 ms 648 KB Output is correct
5 Correct 4 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 6 ms 652 KB Output is correct
9 Correct 10 ms 596 KB Output is correct
10 Correct 17 ms 596 KB Output is correct
11 Incorrect 1 ms 596 KB Output isn't correct
12 Halted 0 ms 0 KB -