제출 #1171116

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1171116		aentrenus	Two Dishes (JOI19_dishes)	C++20	3 / 100	10099 ms	1114112 KiB

dishes

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using str = string;
#define all(a) a.begin(), a.end()
#define print(a) for (auto elem:a) cout<<elem<<' '; cout<<'\n'
#define segprep(b) resize(1<<((int)ceil(log2(b.size()))+1))
#define FOR(a) for (int _ = 0; _ < a; _++)

struct Phase{
    ll duration, time_limit, reward;
};
int n, m;
vector<Phase> dish_1, dish_2;
/*
void solve1(){
    int tl_1 = dish_1.front().time_limit,
        tl_2 = dish_2.front().time_limit;
    vector<pll> pref_sums_1, pref_sums_2; // {time, reward}
    bool f_empty = dish_1.front().duration > tl_1,
        s_empty = dish_2.front().duration > tl_2;
    
    if (tl_1 || tl_2){
        if (tl_1){
            swap(dish_1, dish_2);
            swap(n, m);
        }

        int best_score = 0, score = 0, curr_dur;
        for (int i = 0; i < n && curr_dur+dish_1.at(i).duration <= tl_1; i++){
            score += dish_1.at(i).reward;
            best_score = max(best_score, score);
        }

        cout<<best_score;
        return;
    }

    pref_sums_1.front() = {dish_1.front().duration, dish_1.front().reward};
    pref_sums_2.front() = {dish_2.front().duration, dish_2.front().reward};
}
*/
ll solve2(deque<Phase> phases_1, deque<Phase> phases_2, ll time){
    if (phases_1.empty() && phases_2.empty()) return 0;

    if (phases_1.empty()) swap(phases_1, phases_2);
    auto [dur, tl, rew] = phases_1.front();
    phases_1.pop_front();
    bool can_score = (time+dur) <= tl;
    ll sc = (can_score ? rew : 0);
    ll score_f = solve2(phases_1, phases_2, time+dur)+sc;
    phases_1.push_front({dur, tl, rew});
    if (phases_2.empty()) return score_f;

    swap(phases_1, phases_2);
    auto [dur_, tl_, rew_] = phases_1.front();
    phases_1.pop_front();
    can_score = (time+dur_) <= tl_;
    sc = (can_score ? rew_ : 0);
    ll score_s = solve2(phases_1, phases_2, time+dur_)+sc;

    return max(score_f, score_s);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>m;
    Phase c;
    deque<Phase> phases_1, phases_2;
    FOR(n){
        cin>>c.duration>>c.time_limit>>c.reward;
        phases_1.push_back(c);
    }
    FOR(m){
        cin>>c.duration>>c.time_limit>>c.reward;
        phases_2.push_back(c);
    }
    // dish_1.resize(n);
    // dish_2.resize(m);
    // for (auto &[dur, tl, rew]:dish_1) cin>>dur>>tl>>rew;
    // for (auto &[dur, tl, rew]:dish_2) cin>>dur>>tl>>rew;

    // solve1();

    cout<<solve2(phases_1, phases_2, 0)<<'\n';
}

• Subtask 1: 0 / 5
• Subtask 2: 3 / 3
• Subtask 3: 0 / 7
• Subtask 4: 0 / 39
• Subtask 5: 0 / 11
• Subtask 6: 0 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9