oj.uz

Submission #545309

# Submission time Handle Problem Language Result Execution time Memory
545309 2022-04-04T08:37:56 Z balbit Visiting Singapore (NOI20_visitingsingapore) C++14
16 / 100
 268 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] = -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[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 14 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 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 644 KB Output is correct
9 Correct 10 ms 596 KB Output is correct
10 Correct 17 ms 668 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 35 ms 596 KB Output is correct
2 Correct 24 ms 596 KB Output is correct
3 Correct 81 ms 668 KB Output is correct
4 Correct 149 ms 596 KB Output is correct
5 Correct 46 ms 596 KB Output is correct
6 Correct 70 ms 596 KB Output is correct
7 Correct 129 ms 696 KB Output is correct
8 Correct 57 ms 596 KB Output is correct
9 Correct 80 ms 596 KB Output is correct
10 Correct 184 ms 596 KB Output is correct
11 Correct 182 ms 704 KB Output is correct
12 Correct 186 ms 724 KB Output is correct
13 Correct 193 ms 724 KB Output is correct
14 Correct 268 ms 704 KB Output is correct
15 Correct 255 ms 700 KB Output is correct

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 596 KB Output is correct
2 Correct 24 ms 596 KB Output is correct
3 Correct 81 ms 668 KB Output is correct
4 Correct 149 ms 596 KB Output is correct
5 Correct 46 ms 596 KB Output is correct
6 Correct 70 ms 596 KB Output is correct
7 Correct 129 ms 696 KB Output is correct
8 Correct 57 ms 596 KB Output is correct
9 Correct 80 ms 596 KB Output is correct
10 Correct 184 ms 596 KB Output is correct
11 Correct 182 ms 704 KB Output is correct
12 Correct 186 ms 724 KB Output is correct
13 Correct 193 ms 724 KB Output is correct
14 Correct 268 ms 704 KB Output is correct
15 Correct 255 ms 700 KB Output is correct
16 Incorrect 108 ms 596 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 596 KB Output is correct
2 Correct 24 ms 596 KB Output is correct
3 Correct 81 ms 668 KB Output is correct
4 Correct 149 ms 596 KB Output is correct
5 Correct 46 ms 596 KB Output is correct
6 Correct 70 ms 596 KB Output is correct
7 Correct 129 ms 696 KB Output is correct
8 Correct 57 ms 596 KB Output is correct
9 Correct 80 ms 596 KB Output is correct
10 Correct 184 ms 596 KB Output is correct
11 Correct 182 ms 704 KB Output is correct
12 Correct 186 ms 724 KB Output is correct
13 Correct 193 ms 724 KB Output is correct
14 Correct 268 ms 704 KB Output is correct
15 Correct 255 ms 700 KB Output is correct
16 Incorrect 169 ms 692 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 14 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 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 644 KB Output is correct
9 Correct 10 ms 596 KB Output is correct
10 Correct 17 ms 668 KB Output is correct
11 Incorrect 1 ms 596 KB Output isn't correct
12 Halted 0 ms 0 KB -