Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- /****************************************
- * *
- * Made by: KarleFKremen *
- * At: 5.2.16 00:41:50 ALMT *
- * For: <contest name> *
- * *
- ****************************************/
- // settings
- #define FILE "hopscotch"
- #define USE_FREOPEN 1
- #define USE_LONG 0
- #define USE_IOSOPT 0
- #define INTERACT 0
- // system
- #if USE_LONG
- typedef long long ll;
- #else
- typedef int ll;
- #endif
- #if USE_LONG
- typedef unsigned long long ull;
- #else
- typedef unsigned int ull;
- #endif
- typedef short sym;
- #if INTERACT
- #define eol endl
- #else
- #define eol '\n'
- #endif
- #define pb push_back
- #define mp make_pair
- #define p(a, b) pair < a, b >
- #define sq(x) (x * x)
- #define fi first
- #define se second
- #define rm erase
- #define ins insert
- #define rev(a) reverse(a.begin(), a.end())
- #define rs resize
- #define sz size
- #define M3 (ll)1e3
- #define M4 (ll)1e4
- #define M5 (ll)1e5
- #define M6 (ll)1e6
- #define M7 (ll)1e7
- #define M8 (ll)1e8
- #define M9 (ll)1e9
- #define stlprint(a) \
- for(auto __LEVEL_1_STL_ITERATOR = a.begin(); __LEVEL_1_STL_ITERATOR != a.end(); __LEVEL_1_STL_ITERATOR++) \
- { \
- cout << (*__LEVEL_1_STL_ITERATOR) << ' '; \
- }
- #define stlfor(a) for(auto it = a.begin(); it != a.end(); it++)
- using namespace std;
- vector < vector < ll > > dp, cost;
- vector < ll > a, b;
- map < p(ll, p(ll, ll)), bool > us;
- ll n, k, s, x, y;
- void rec(ll c, ll s = 0)
- {
- if(c < 1 || c > n)
- return;
- if(s >= k)
- return;
- if(us[mp(c, mp(s, dp[c][s]))] == 1)
- return;
- us[mp(c, mp(s, dp[c][s]))] = 1;
- if(c > x) dp[c - x][s + 1] = max(dp[c - x][s + 1], dp[c][s] + cost[c - x][s + 1]);
- rec(c - x, s + 1);
- if(c <= (n - y)) dp[c + y][s + 1] = max(dp[c + y][s + 1], dp[c][s] + cost[c + y][s + 1]);
- rec(c + y, s + 1);
- dp[c][s + 1] = max(dp[c][s + 1], dp[c][s] + cost[c][s + 1]);
- rec(c, s + 1);
- }
- int main()
- {
- // ios{
- #if USE_IOSOPT
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- #endif
- #if USE_FREOPEN
- freopen(FILE".in", "r", stdin);
- freopen(FILE".out", "w", stdout);
- #endif
- cin >> n >> k >> s;
- dp.rs(n + 1);
- cost.rs(n + 1);
- for(int i = 1; i <= n; i++)
- {
- dp[i].rs(k + 1);
- cost[i].rs(k + 1);
- }
- a.rs(n + 1);
- b.rs(n + 1);
- for(int i = 1; i <= n; i++)
- {
- cin >> a[i];
- }
- for(int i = 1; i <= n; i++)
- {
- cin >> b[i];
- }
- for(int i = 1; i <= n; i++)
- {
- for(int j = 0; j <= k; j++)
- {
- cost[i][j] = (a[i] * j + b[i]);
- }
- }
- cin >> x >> y;
- dp[s][0] = b[s];
- rec(s, 0);
- // for(int i = 1; i <= n; i++)
- // {
- // cout << i << ": ";
- // for(int j = 0; j <= k; j++)
- // {
- // cout << setw(4) << cost[i][j];
- // }
- // cout << endl;
- // }
- // cout << endl;
- // for(int i = 1; i <= n; i++)
- // {
- // cout << i << ": ";
- // for(int j = 0; j <= k; j++)
- // {
- // cout << setw(4) << dp[i][j];
- // }
- // cout << endl;
- // }
- ll mxrs = -M9;
- for(int i = 1; i <= n; i++)
- {
- mxrs = max(mxrs, dp[i][k]);
- }
- cout << mxrs << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment