KarleFKremen

Untitled

Apr 9th, 2016
80
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.00 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. /****************************************
  4.  *                                      *
  5.  *  Made by:    KarleFKremen            *
  6.  *  At:         5.2.16 00:41:50 ALMT    *
  7.  *  For:        <contest name>          *
  8.  *                                      *
  9.  ****************************************/
  10.  
  11. // settings
  12.     #define FILE "hopscotch"
  13.     #define USE_FREOPEN 1
  14.     #define USE_LONG 0
  15.     #define USE_IOSOPT 0
  16.     #define INTERACT 0
  17.  
  18. // system
  19.     #if USE_LONG
  20.         typedef long long ll;
  21.     #else
  22.         typedef int ll;
  23.     #endif
  24.     #if USE_LONG
  25.         typedef unsigned long long ull;
  26.     #else
  27.         typedef unsigned int ull;
  28.     #endif
  29.     typedef short sym;
  30.     #if INTERACT
  31.         #define eol endl
  32.     #else
  33.         #define eol '\n'
  34.     #endif
  35.     #define pb push_back
  36.     #define mp make_pair
  37.     #define p(a, b) pair < a, b >
  38.     #define sq(x) (x * x)
  39.     #define fi first
  40.     #define se second
  41.     #define rm erase
  42.     #define ins insert
  43.     #define rev(a) reverse(a.begin(), a.end())
  44.     #define rs resize
  45.     #define sz size
  46.     #define M3 (ll)1e3
  47.     #define M4 (ll)1e4
  48.     #define M5 (ll)1e5
  49.     #define M6 (ll)1e6
  50.     #define M7 (ll)1e7
  51.     #define M8 (ll)1e8
  52.     #define M9 (ll)1e9
  53.     #define stlprint(a) \
  54.         for(auto __LEVEL_1_STL_ITERATOR = a.begin(); __LEVEL_1_STL_ITERATOR != a.end(); __LEVEL_1_STL_ITERATOR++) \
  55.         { \
  56.             cout << (*__LEVEL_1_STL_ITERATOR) << ' '; \
  57.         }
  58.     #define stlfor(a) for(auto it = a.begin(); it != a.end(); it++)
  59.  
  60. using namespace std;
  61.    
  62. vector < vector < ll > > dp, cost;
  63. vector < ll > a, b;
  64.  
  65. map < p(ll, p(ll, ll)), bool > us;
  66.  
  67. ll n, k, s, x, y;
  68.  
  69. void rec(ll c, ll s = 0)
  70. {
  71.     if(c < 1 || c > n)
  72.         return;
  73.     if(s >= k)
  74.         return;
  75.     if(us[mp(c, mp(s, dp[c][s]))] == 1)
  76.         return;
  77.     us[mp(c, mp(s, dp[c][s]))] = 1;
  78.     if(c > x) dp[c - x][s + 1] = max(dp[c - x][s + 1], dp[c][s]  + cost[c - x][s + 1]);
  79.     rec(c - x, s + 1);
  80.     if(c <= (n - y)) dp[c + y][s + 1] = max(dp[c + y][s + 1], dp[c][s] + cost[c + y][s + 1]);
  81.     rec(c + y, s + 1);
  82.     dp[c][s + 1] = max(dp[c][s + 1], dp[c][s] + cost[c][s + 1]);
  83.     rec(c, s + 1);
  84. }
  85.  
  86. int main()
  87. {
  88.     // ios{
  89.         #if USE_IOSOPT
  90.             ios_base::sync_with_stdio(false);
  91.             cin.tie(0);
  92.         #endif
  93.         #if USE_FREOPEN
  94.             freopen(FILE".in", "r", stdin);
  95.             freopen(FILE".out", "w", stdout);
  96.         #endif
  97.     cin >> n >> k >> s;
  98.     dp.rs(n + 1);
  99.     cost.rs(n + 1);
  100.     for(int i = 1; i <= n; i++)
  101.     {
  102.         dp[i].rs(k + 1);
  103.         cost[i].rs(k + 1);
  104.     }
  105.     a.rs(n + 1);
  106.     b.rs(n + 1);
  107.     for(int i = 1; i <= n; i++)
  108.     {
  109.         cin >> a[i];
  110.     }
  111.     for(int i = 1; i <= n; i++)
  112.     {
  113.         cin >> b[i];
  114.     }
  115.     for(int i = 1; i <= n; i++)
  116.     {
  117.         for(int j = 0; j <= k; j++)
  118.         {
  119.             cost[i][j] = (a[i] * j + b[i]);
  120.         }
  121.     }
  122.     cin >> x >> y;
  123.     dp[s][0] = b[s];
  124.     rec(s, 0);
  125.     // for(int i = 1; i <= n; i++)
  126.     // {
  127.     //  cout << i << ": ";
  128.     //  for(int j = 0; j <= k; j++)
  129.     //  {
  130.     //      cout << setw(4) << cost[i][j];
  131.     //  }
  132.     //  cout << endl;
  133.     // }
  134.     // cout << endl;
  135.     // for(int i = 1; i <= n; i++)
  136.     // {
  137.     //  cout << i << ": ";
  138.     //  for(int j = 0; j <= k; j++)
  139.     //  {
  140.     //      cout << setw(4) << dp[i][j];
  141.     //  }
  142.     //  cout << endl;
  143.     // }
  144.     ll mxrs = -M9;
  145.     for(int i = 1; i <= n; i++)
  146.     {
  147.         mxrs = max(mxrs, dp[i][k]);
  148.     }
  149.     cout << mxrs << endl;
  150. }
Advertisement
Add Comment
Please, Sign In to add comment