oj.uz

답안 #537396

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
537396 2022-03-15T04:35:29 Z wiwiho 치료 계획 (JOI20_treatment) C++14
0 / 100
 42 ms 2112 KB 
#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 << ')';
}

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

    int n, m;
    cin >> n >> m;

    map<int, ll> dp;
    vector<pair<int, pii>> ev;
    for(int i = 1; i <= m; i++){
        int l, r, c, t;
        cin >> t >> l >> r >> c;
        assert(t == 1);
        ev.eb(mp(l, mp(r, c)));
    }
    //cerr << "ok\n";
    lsort(ev);

    dp[0] = 0;
    for(auto i : ev){
        int l = i.F;
        int r = i.S.F;
        ll c = i.S.S;
        while(!dp.empty() && dp.begin()->F < l - 1) dp.erase(dp.begin());
        if(dp.empty()) break;
        if(r <= dp.begin()->S) continue;
        c += dp.begin()->S;
        if(dp.find(r) == dp.end()) dp[r] = c;
        else dp[r] = min(dp[r], c);
        auto it = dp.lower_bound(r);
        while(it != dp.begin() && prev(it)->S >= c){
            it = dp.erase(prev(it));
        }
        if(next(it) != dp.end() && next(it)->S <= c) dp.erase(it);
        //cerr << "test " << l << " " << r << " " << c << "\n";
        //printv(dp, cerr);
    }

    if(dp.empty() || dp.rbegin()->F != n){
        cout << "-1\n";
        return 0;
    }
    cout << dp.rbegin()->S << "\n";

    return 0;
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 2112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 42 ms 2112 KB Output isn't correct
2 Halted 0 ms 0 KB -