Submission #46837144

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = (1LL << 60);

int main() {
    ll n; cin >> n;
    vector<ll> d(n);
    for(int i = 0; i < n; i ++) cin >> d[i];
    ll l1, c1, k1, l2, c2, k2;
    cin >> l1 >> c1 >> k1 >> l2 >> c2 >> k2;
    vector dp(k1 + 1, vector(k2 + 1, make_pair(0LL, 0LL)));
    for(int i = 0; i <= k1; i ++) {
        for(int j = 0; j <= k2; j ++) {
            auto [id, len] = dp[i][j];
            if(i != k1) {
                pair<ll, ll> nx = {id, len};
                if(id != n) {
                    nx.second = min(d[id], len + l1);
                    if(nx.second == d[id]) nx = {id + 1, 0};
                }
                dp[i + 1][j] = max(dp[i + 1][j], nx);
            }
            if(j != k2) {
                pair<ll, ll> nx = {id, len};
                if(id != n) {
                    nx.second = min(d[id], len + l2);
                    if(nx.second == d[id]) nx = {id + 1, 0};
                }
                dp[i][j + 1] = max(dp[i][j + 1], nx);
            }
        }
    }
    ll ans = INF;
    for(int i = 0; i <= k1; i ++) for(int j = 0; j <= k2; j ++) {
        if(dp[i][j].first == n) ans = min(ans, c1 * i + c2 * j);
    }
    cout << (ans == INF ? -1 : ans) << endl;
    return 0;
}

Submission Info

Submission Time
Task F - Sensor Optimization Dilemma
User shinchan
Language C++ 20 (gcc 12.2)
Score 500
Code Size 1323 Byte
Status AC
Exec Time 10 ms
Memory 18988 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 60
Set Name Test Cases
Sample 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt
All 00_sample_00.txt, 00_sample_01.txt, 00_sample_02.txt, 01_random_00.txt, 01_random_01.txt, 01_random_02.txt, 01_random_03.txt, 01_random_04.txt, 01_random_05.txt, 01_random_06.txt, 01_random_07.txt, 01_random_08.txt, 01_random_09.txt, 01_random_10.txt, 01_random_11.txt, 01_random_12.txt, 01_random_13.txt, 01_random_14.txt, 01_random_15.txt, 01_random_16.txt, 01_random_17.txt, 01_random_18.txt, 01_random_19.txt, 01_random_20.txt, 01_random_21.txt, 01_random_22.txt, 01_random_23.txt, 01_random_24.txt, 01_random_25.txt, 01_random_26.txt, 01_random_27.txt, 01_random_28.txt, 01_random_29.txt, 01_random_30.txt, 01_random_31.txt, 01_random_32.txt, 01_random_33.txt, 01_random_34.txt, 01_random_35.txt, 01_random_36.txt, 01_random_37.txt, 01_random_38.txt, 01_random_39.txt, 01_random_40.txt, 01_random_41.txt, 01_random_42.txt, 01_random_43.txt, 01_random_44.txt, 02_random2_00.txt, 02_random2_01.txt, 02_random2_02.txt, 02_random2_03.txt, 02_random2_04.txt, 02_random2_05.txt, 02_random2_06.txt, 02_random2_07.txt, 02_random2_08.txt, 02_random2_09.txt, 03_handmade_00.txt, 03_handmade_01.txt
Case Name Status Exec Time Memory
00_sample_00.txt AC 1 ms 3516 KiB
00_sample_01.txt AC 1 ms 3492 KiB
00_sample_02.txt AC 1 ms 3716 KiB
01_random_00.txt AC 1 ms 3508 KiB
01_random_01.txt AC 9 ms 18748 KiB
01_random_02.txt AC 1 ms 3608 KiB
01_random_03.txt AC 1 ms 3500 KiB
01_random_04.txt AC 9 ms 18728 KiB
01_random_05.txt AC 9 ms 18760 KiB
01_random_06.txt AC 1 ms 3692 KiB
01_random_07.txt AC 2 ms 5020 KiB
01_random_08.txt AC 1 ms 3624 KiB
01_random_09.txt AC 1 ms 3564 KiB
01_random_10.txt AC 3 ms 7036 KiB
01_random_11.txt AC 3 ms 6864 KiB
01_random_12.txt AC 2 ms 5208 KiB
01_random_13.txt AC 3 ms 7580 KiB
01_random_14.txt AC 1 ms 4648 KiB
01_random_15.txt AC 1 ms 3732 KiB
01_random_16.txt AC 1 ms 3596 KiB
01_random_17.txt AC 3 ms 7472 KiB
01_random_18.txt AC 5 ms 10560 KiB
01_random_19.txt AC 10 ms 18692 KiB
01_random_20.txt AC 4 ms 9512 KiB
01_random_21.txt AC 2 ms 6020 KiB
01_random_22.txt AC 5 ms 11284 KiB
01_random_23.txt AC 2 ms 5748 KiB
01_random_24.txt AC 9 ms 18816 KiB
01_random_25.txt AC 6 ms 13660 KiB
01_random_26.txt AC 4 ms 9940 KiB
01_random_27.txt AC 6 ms 12876 KiB
01_random_28.txt AC 5 ms 11168 KiB
01_random_29.txt AC 6 ms 12424 KiB
01_random_30.txt AC 9 ms 18732 KiB
01_random_31.txt AC 4 ms 8740 KiB
01_random_32.txt AC 9 ms 18808 KiB
01_random_33.txt AC 10 ms 18748 KiB
01_random_34.txt AC 9 ms 18756 KiB
01_random_35.txt AC 10 ms 18752 KiB
01_random_36.txt AC 1 ms 3908 KiB
01_random_37.txt AC 9 ms 17164 KiB
01_random_38.txt AC 10 ms 18824 KiB
01_random_39.txt AC 9 ms 18684 KiB
01_random_40.txt AC 1 ms 3756 KiB
01_random_41.txt AC 2 ms 5528 KiB
01_random_42.txt AC 1 ms 4416 KiB
01_random_43.txt AC 4 ms 8928 KiB
01_random_44.txt AC 5 ms 11304 KiB
02_random2_00.txt AC 3 ms 7308 KiB
02_random2_01.txt AC 3 ms 6820 KiB
02_random2_02.txt AC 6 ms 13016 KiB
02_random2_03.txt AC 3 ms 7668 KiB
02_random2_04.txt AC 3 ms 7400 KiB
02_random2_05.txt AC 7 ms 14608 KiB
02_random2_06.txt AC 2 ms 5548 KiB
02_random2_07.txt AC 2 ms 4864 KiB
02_random2_08.txt AC 3 ms 6536 KiB
02_random2_09.txt AC 5 ms 11520 KiB
03_handmade_00.txt AC 1 ms 3488 KiB
03_handmade_01.txt AC 10 ms 18988 KiB