Submission #537413

#	Time	Username	Problem	Language	Result	Execution time	Memory
537413		wiwiho	Treatment Project (JOI20_treatment)	C++14	5 / 100	294 ms	2088 KiB

treatment

#include <bits/stdc++.h>

#define mp make_pair
#define F first
#define S second
#define eb emplace_back
#define iter(a) a.begin(), a.end()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(iter(a), greater<>())
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}

using namespace std;

typedef long long ll;
using pii = pair<int, int>;

template<typename A, typename B>
ostream& operator<<(ostream& o, pair<A, B> a){
    return o << '(' << a.F << ',' << a.S << ')';
}

struct seg{
    int tme, l, r, c;
    bool operator<(seg b){
        array<int, 4> ta = {tme, l, r, c};
        array<int, 4> tb = {b.tme, b.l, b.r, b.c};
        return ta < tb;
    }
};

int n, m;
vector<seg> s;

bool solve(int msk){
    set<pii> st;
    st.insert(mp(1, n));
    vector<seg> a;
    for(int i = 0; i < m; i++){
        if(1 << i & msk) a.eb(s[i]);
    }
    lsort(a);

    int lst = 1;
    for(auto i : a){
        
        int sep = i.tme - lst;
        lst = i.tme;

        set<pii> tmp;
        for(pii t : st){
            int l = t.F, r = t.S;
            l -= sep; r += sep;
            l = max(l, 1);
            r = min(r, n);
            if(!tmp.empty() && tmp.rbegin()->S >= l - 1){
                pii owo = *tmp.rbegin();
                tmp.erase(prev(tmp.end()));
                owo.S = r;
                tmp.insert(owo);
            }
            else tmp.insert(mp(l, r));
        }
        st.swap(tmp);
        tmp.clear();
        
        int l = i.l, r = i.r;
        for(pii t : st){
            if(max(t.F, l) > min(t.S, r)){
                tmp.insert(t);
                continue;
            }
            int tl = t.F, tr = t.S;
            if(l <= tl && tr <= r) continue;
            else if(tr <= r) tmp.insert(mp(tl, l - 1));
            else if(l <= tl) tmp.insert(mp(r + 1, tr));
            else tmp.insert(mp(tl, l - 1)), tmp.insert(mp(r + 1, tr));
        }
        st.swap(tmp);
    }

    return st.empty();
}

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

    cin >> n >> m;

    s.resize(m);
    for(int i = 0; i < m; i++){
        cin >> s[i].tme >> s[i].l >> s[i].r >> s[i].c;
    }

    ll ans = LLONG_MAX;
    for(int i = 0; i < (1 << m); i++){
        if(!solve(i)) continue;
        //cerr << bitset<5>(i) << "\n";
        ll sum = 0;
        for(int j = 0; j < m; j++) if(1 << j & i) sum += s[j].c;
        ans = min(ans, sum);
    }
    if(ans == LLONG_MAX) ans = -1;
    cout << ans << "\n";

    return 0;
}

• Subtask 1: 0 / 4
• Subtask 2: 5 / 5
• Subtask 3: 0 / 30
• Subtask 4: 0 / 61