Submission #843769

#	Time	Username	Problem	Language	Result	Execution time	Memory
843769		fanwen	Visiting Singapore (NOI20_visitingsingapore)	C++17	0 / 100	32 ms	262144 KiB

VisitingSingapore

/**
*   NAME : PHAM VAN SAM
*   DATE : 12.01.2023 17:17:45
*  ┌───┐   ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐
*  │Esc│   │ F1│ F2│ F3│ F4│ │ F5│ F6│ F7│ F8│ │ F9│F10│F11│F12│ │P/S│S L│P/B│  ┌┐    ┌┐    ┌┐
*  └───┘   └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘  └┘    └┘    └┘
*  ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐
*  │~ `│! 1│@ 2│# 3│$ 4│% 5│^ 6│& 7│* 8│( 9│) 0│_ -│+ =│ BacSp │ │Ins│Hom│PUp│ │Num│ / │ * │ - │
*  ├───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─────┤ ├───┼───┼───┤ ├───┼───┼───┼───┤
*  │ Tab │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │{ [│} ]│ | \ │ │Del│End│PDn│ │ 7 │ 8 │ 9 │   │
*  ├─────┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴─────┤ └───┴───┴───┘ ├───┼───┼───┤ + │
*  │ Caps │ A │ S │ D │ F │ G │ H │ J │ K │ L │: ;│" '│ Enter  │               │ 4 │ 5 │ 6 │   │
*  ├──────┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴────────┤     ┌───┐     ├───┼───┼───┼───┤
*  │ Shift  │ Z │ X │ C │ V │ B │ N │ M │< ,│> .│? /│  Shift   │     │ ↑ │     │ 1 │ 2 │ 3 │   │
*  ├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││
*  │ Ctrl│ Win│ Alt│         Space         │ Alt│ Win│Menu│Ctrl│ │ ← │ ↓ │ → │ │   0   │ . │←─┘│
*  └─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘
**/
#pragma GCC optimize("O3")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define MASK(x) (1LL << (x))
#define BIT(x, k) (((x) >> (k)) & 1LL)
#define all(x) (x).begin(),(x).end()
#define For(i, a, b) for (int i = (a); i <= (b); ++i)
#define Fod(i, a, b) for (int i = (a); i >= (b); --i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define Fore(i, a) for (__typeof((a).begin()) i = (a).begin(); i != (a).end(); ++i)
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define file(TASK) if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); }

template <class U, class V> bool maximize(U &A, const V &B){ return (A < B) ? (A = B, true) : false;}
template <class U, class V> bool minimize(U &A, const V &B){ return (A > B) ? (A = B, true) : false;}

using namespace std;

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int l, int r) { return l + rnd() % (r - l + 1); }
const int MAXN = 5e3 + 5;
int N, M, K, A, B;
int v[MAXN / 5], s[MAXN], t[MAXN];
int dp[MAXN][MAXN], Max[MAXN][MAXN], Max_i[MAXN][MAXN], Max_j[MAXN][MAXN];
signed main() {
    // file("TASK");
    file("funtour");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> K >> N >> M >> A >> B;
    For (i, 1, K) cin >> v[i];
    For (i, 1, N) cin >> s[i];
    For (i, 1, M) cin >> t[i];
    memset(dp, -0x3f, sizeof dp);
    memset(Max, -0x3f, sizeof Max);
    memset(Max_i, -0x3f, sizeof Max_i);
    memset(Max_j, -0x3f, sizeof Max_j);
    long long ans = M * B + A;
    For (i, 1, N) For (j, 1, M) {
    	if(s[i] == t[j]) dp[i][j] = v[s[i]] + A * (j != 1) + (j - 1) * B;
   	}
    For (i, 1, N) For (j, 1, M) {
    	maximize(dp[i][j], Max[i - 1][j - 1] + (i + j) * B + 2 * A);
    	maximize(dp[i][j], Max_i[i][j - 1] + (i + j) * B + A);
    	maximize(dp[i][j], Max_j[i - 1][j] + (i + j) * B + A);
    	if(s[i] == t[j]) maximize(dp[i][j], dp[i - 1][j - 1] + v[s[i]]), maximize(ans, dp[i][j] + A * (j != M) + (M - j) * B);
    	maximize(Max[i][j], max(Max[i - 1][j], Max[i][j - 1]));
    	maximize(Max[i][j], dp[i][j] - (i + j) * B);
    	maximize(Max_i[i][j], dp[i][j] - (i + j) * B);maximize(Max_i[i][j], Max_i[i][j - 1]);
    	maximize(Max_j[i][j], dp[i][j] - (i + j) * B);maximize(Max_j[i][j], Max_j[i - 1][j]);
    }
    cout << ans;
    // cerr << "Time elapsed: " << TIME << " s.\n";
    return (0 ^ 0);
}
/*
Max[i][j] = max(dp[x][y]) x <= i && y <= j
Max_i[i][j] = max(dp[i][y]) y <= j
Max_j[i][j] = max(dp[x][j]) x <= i
*/
/*
A + (q - p + 1) * B
A + q * B - (p - 1) * B

*/

Compilation message (stderr)

VisitingSingapore.cpp: In function 'int main()':
VisitingSingapore.cpp:30:56: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 | #define file(TASK) if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); }
      |                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
VisitingSingapore.cpp:45:5: note: in expansion of macro 'file'
   45 |     file("funtour");
      |     ^~~~
VisitingSingapore.cpp:30:89: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 | #define file(TASK) if(fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); }
      |                                                                                  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
VisitingSingapore.cpp:45:5: note: in expansion of macro 'file'
   45 |     file("funtour");
      |     ^~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 6
• Subtask 3: 0 / 12
• Subtask 4: 0 / 7
• Subtask 5: 0 / 8
• Subtask 6: 0 / 13
• Subtask 7: 0 / 50