fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int maxn = 2e5;
  5. const ll LLINF = 1e18;
  6.  
  7. int n, t, a, b, k[maxn+5];
  8. ll dp[1001][1001], f[maxn+5];
  9.  
  10. void read() {
  11.     cin >> n >> t >> a >> b;
  12.     for (int i = 1; i<=n; ++i) cin >> k[i];
  13. }
  14.  
  15. void sub1() {
  16.     int cur_time = 0;
  17.     ll res = 0;
  18.     for (int i = 1; i<=n; ++i) {
  19.         if (cur_time + a <= t) {
  20.             cur_time += a;
  21.             res += 1LL * k[i];
  22.         } else break;
  23.     }
  24.     cout << res;
  25. }
  26.  
  27. void sub2() {
  28.     for (int i = 0; i<=n; ++i) {
  29.         for (int j = 0; j<=t; ++j) dp[i][j] = -LLINF;
  30.     }
  31.     dp[0][0] = 0;
  32.  
  33.     for (int i = 1; i<=n; ++i) {
  34.         for (int time = 0; time <= t; ++time) {
  35.             if (time >= a && dp[i-1][time-a] != -LLINF)
  36.                 dp[i][time] = max(dp[i][time], 1LL * dp[i-1][time-a] + k[i]);
  37.             if (time >= b && dp[i-1][time-b] != -LLINF)
  38.                 dp[i][time] = max(dp[i][time], dp[i-1][time-b]);
  39.         }
  40.     }
  41.  
  42.     ll res = 0;
  43.     for (int i = 1; i<=n; ++i) {
  44.         for (int j = 0; j<=t; ++j) res = max(res, dp[i][j]);
  45.     }
  46.     cout << res;
  47. }
  48. void sub3() {
  49.     for (int i = 1; i<=n; ++i) {
  50.         f[i] = 1LL * f[i-1] + k[i];
  51.     }
  52.  
  53.     ll res = 0;
  54.     for (int g = 1; g<=n; ++g) {
  55.         int lo = g, hi = n;
  56.         while (lo <= hi) {
  57.             int mid = (lo + hi) / 2;
  58.             ll reward = f[mid] - f[g-1];
  59.             int time = (g-1)*b + (mid-g+1)*a;
  60.             if (time <= t) {
  61.                 res = max(res, reward);
  62.                 lo = mid+1;
  63.             } else hi = mid-1;
  64.         }
  65.     }
  66.     cout << res;
  67. }
  68. void solve() {
  69.     bool check_sub1 = true;
  70.     for (int i = 1; i<n; ++i) {
  71.         if (k[i] < k[i+1]) {
  72.             check_sub1 = false;
  73.             break;
  74.         }
  75.     }
  76.     if (check_sub1) {
  77.         sub1();
  78.         return;
  79.     }
  80.     if (n <= 1000 && t <= 1000) {
  81.         sub2();
  82.         return;
  83.     }
  84.     sub3();
  85. }
  86. int main() {
  87.     ios_base::sync_with_stdio(false);
  88.     cin.tie(0); cout.tie(0);
  89.     freopen("game.inp", "r", stdin);
  90.     freopen("game.out", "w", stdout);
  91.     read();
  92.     solve();
  93.     return 0;
  94. }
  95.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/2FByLG
bài 1
language:
C++ (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!