Submission #423741

#	Time	Username	Problem	Language	Result	Execution time	Memory
423741		lyc	Treatment Project (JOI20_treatment)	C++14	5 / 100	401 ms	2428 KiB

treatment

#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef pair<int,int> ii;

const int mxN = 100001;

int N, M;
struct Treatment {
    int T, L, R, C;
};
vector<Treatment> treat;

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

    cin >> N >> M;
    FOR(i,1,M){
        int T, L, R, C;
        cin >> T >> L >> R >> C;
        treat.push_back({T,L,R,C});
    }
    sort(ALL(treat),[](Treatment &a, Treatment &b){ return a.T < b.T; });

    ll ans = 1e18;
    FOR(b,0,(1<<M)-1){
        set<ii> ranges, tmp;
        ranges.insert(ii(1,N));
        int t = 1;
        ll cost = 0;
        FOR(i,0,M-1) if (b&(1<<i)) {
            auto tr = treat[i];
            cost += tr.C;
            if (t < tr.T) {
                int e = tr.T - t;
                t = tr.T;
                tmp.clear();
                for (auto it = ranges.begin(), y = it; it != ranges.end(); ++it) {
                    auto x = *it;
                    x.first = max(1,x.first-e);
                    x.second = min(N,x.second+e);
                    while ((y = next(it)) != ranges.end()) {
                        if (x.second >= y->first-e) {
                            x.second = min(N,y->second+e);
                            ranges.erase(y);
                        } else break;
                    }
                    tmp.insert(x);
                }
                ranges = tmp;
            }

            tmp.clear();
            for (auto& x : ranges) {
                if (x.second < tr.L || x.first > tr.R) tmp.insert(x);
                else {
                    if (x.first < tr.L) tmp.insert(ii(x.first,tr.L-1));
                    if (x.second > tr.R) tmp.insert(ii(tr.R+1,x.second));
                }
            }
            ranges = tmp;
        }
        if (ranges.empty()) {
            //TRACE(b _ cost);
            ans = min(ans,cost);
        }
    }
    if (ans == 1e18) cout << -1 << '\n';
    else cout << ans << '\n';
}

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