oj.uz

Submission #1103397

# Submission time Handle Problem Language Result Execution time Memory
1103397 2024-10-20T18:28:15 Z underwaterkillerwhale Semiexpress (JOI17_semiexpress) C++17
100 / 100
 29 ms 46420 KB 
#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

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

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4436 KB Output is correct
2 Correct 1 ms 4584 KB Output is correct
3 Correct 1 ms 6484 KB Output is correct
4 Correct 1 ms 4436 KB Output is correct
5 Correct 1 ms 4436 KB Output is correct
6 Correct 2 ms 6484 KB Output is correct
7 Correct 1 ms 4436 KB Output is correct
8 Correct 2 ms 6484 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4436 KB Output is correct
2 Correct 1 ms 4584 KB Output is correct
3 Correct 1 ms 6484 KB Output is correct
4 Correct 1 ms 4436 KB Output is correct
5 Correct 1 ms 4436 KB Output is correct
6 Correct 2 ms 6484 KB Output is correct
7 Correct 1 ms 4436 KB Output is correct
8 Correct 2 ms 6484 KB Output is correct
9 Correct 1 ms 4436 KB Output is correct
10 Correct 2 ms 4436 KB Output is correct
11 Correct 2 ms 6736 KB Output is correct
12 Correct 2 ms 6484 KB Output is correct
13 Correct 2 ms 6484 KB Output is correct
14 Correct 1 ms 4604 KB Output is correct
15 Correct 1 ms 4436 KB Output is correct
16 Correct 1 ms 6484 KB Output is correct
17 Correct 1 ms 6484 KB Output is correct
18 Correct 2 ms 6484 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4436 KB Output is correct
2 Correct 1 ms 4584 KB Output is correct
3 Correct 1 ms 6484 KB Output is correct
4 Correct 1 ms 4436 KB Output is correct
5 Correct 1 ms 4436 KB Output is correct
6 Correct 2 ms 6484 KB Output is correct
7 Correct 1 ms 4436 KB Output is correct
8 Correct 2 ms 6484 KB Output is correct
9 Correct 1 ms 4436 KB Output is correct
10 Correct 2 ms 4436 KB Output is correct
11 Correct 2 ms 6736 KB Output is correct
12 Correct 2 ms 6484 KB Output is correct
13 Correct 2 ms 6484 KB Output is correct
14 Correct 1 ms 4604 KB Output is correct
15 Correct 1 ms 4436 KB Output is correct
16 Correct 1 ms 6484 KB Output is correct
17 Correct 1 ms 6484 KB Output is correct
18 Correct 2 ms 6484 KB Output is correct
19 Correct 6 ms 29268 KB Output is correct
20 Correct 9 ms 29268 KB Output is correct
21 Correct 4 ms 27220 KB Output is correct
22 Correct 6 ms 33364 KB Output is correct
23 Correct 29 ms 43204 KB Output is correct
24 Correct 4 ms 33364 KB Output is correct
25 Correct 3 ms 19048 KB Output is correct
26 Correct 7 ms 46420 KB Output is correct
27 Correct 5 ms 39508 KB Output is correct
28 Correct 6 ms 41572 KB Output is correct
29 Correct 9 ms 16980 KB Output is correct
30 Correct 6 ms 6904 KB Output is correct