Submission #1103397

#TimeUsernameProblemLanguageResultExecution timeMemory
1103397underwaterkillerwhaleSemiexpress (JOI17_semiexpress)C++17
100 / 100
29 ms46420 KiB
#include <bits/stdc++.h> #define ll long long #define rep(i,m,n) for(int i=(m); i<=(n); i++) #define reb(i,m,n) for(int i=(m); i>=(n); i--) #define pii pair<int,int> #define pll pair<ll,ll> #define MP make_pair #define fs first #define se second #define bit(msk, i) ((msk >> i) & 1) #define iter(id, v) for(auto id : v) #define pb push_back #define SZ(v) (ll)v.size() #define ALL(v) v.begin(),v.end() using namespace std; mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count()); ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); } const int N = 2e3 + 2; const int Mod = 1e9 + 7;///lon const int INF = 1e9 + 7; const ll BASE = 137; const int szBL = 450; int n, m, K; ll A, B, C; ll T; int a[N]; int dp[N][N], Cost[N][N], opt[N][N]; void solution () { cin >> n >> m >> K >> A >> B >> C >> T; rep (i, 1, m) { cin >> a[i]; } K -= m; rep (i, 0, m) rep (j, 0, K) dp[i][j] = -INF, opt[i][j] = -1; function<void(int, int, int, int, int)> dnc = [&] (int Row, int L, int R, int optL, int optR) { if (L > R) return; int mid = L + R >> 1; int best = -1; rep (i, optL, min(optR, mid)) { if (dp[Row][mid] < dp[Row - 1][i] + Cost[Row - 1][mid - i] + 1) { dp[Row][mid] = dp[Row - 1][i] + Cost[Row - 1] [mid - i] + 1; best = i; } } opt[Row][mid] = best; // cout << Row <<" "<<mid<<" "<<dp[Row][mid] <<"\n"; dnc(Row, L, mid - 1, optL, opt[Row][mid]); dnc(Row, mid + 1, R, opt[Row][mid], optR); }; int res = 0; dp[1][0] = 0; rep (i, 2, m) { if (B * (a[i - 1] - 1) > T) { break; } ll remT_to_Ai = T - B * (a[i - 1] - 1); int nNode = a[i] - a[i - 1] - 1; int lstR = a[i - 1]; rep (j, 0, K) { ll remT_to_lstR = remT_to_Ai - C * (lstR - a[i - 1]); if (lstR >= a[i] || remT_to_lstR < 0) { break; } int nNodeA = min(1LL * nNode - (lstR - a[i - 1]), remT_to_lstR / A); ///largest number of node can travel from a[i] using A Cost[i - 1][j] = lstR - a[i - 1] + nNodeA; // cout << "COST: "<<i<<" "<<j<<" "<<Cost[i][j] <<"\n"; lstR = lstR + nNodeA + 1; } rep (j, 1, K) { Cost[i - 1][j] = max(Cost[i - 1][j], Cost[i - 1][j - 1]); } dnc(i, 0, K, 0, K); } rep (i, 1, m) { if (B * (a[i] - 1) > T) break; rep (j, 0, K) res = max(res, dp[i][j] + Cost[i][K - j]); } cout << res <<"\n"; } #define file(name) freopen(name".inp","r",stdin); \ freopen(name".out","w",stdout); int main () { // file("c"); ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); int num_Test = 1; // cin >> num_Test; while (num_Test--) solution(); } /* no bug challenge +12 8 5 1 5 2 4 8 3 6 7 RRLLRRRL 4 3 5 3 4 bai toan lú lú cần sự tỉnh táo thì nên chia nhỏ bài toán ra và giải quyết từng bài toán xác định từng bước */

Compilation message (stderr)

semiexpress.cpp: In lambda function:
semiexpress.cpp:46:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |         int mid = L + R >> 1;
      |                   ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...