oj.uz

답안 #946362

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
946362 2024-03-14T14:28:08 Z Pring 치료 계획 (JOI20_treatment) C++17
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 5005, INF = 3.9e18;
int m, n;
int ans = INF;

struct P {
    int t, l, r, c;
    int time, bound, pos, exp;
    P() {}
    P(int _t, int _l, int _r, int _c) : t(_t), l(_l), r(_r), c(_c) {
        time = r + t;
        bound = r - t;
        pos = l - t;
        exp = l + t;
    }
} p[MXN];

ostream &operator<<(ostream &ss, P p) {
    ss << '<' << p.t << ' ' << p.l << ' ' << p.r << ' ' << p.c << '>';
    return ss;
}

vector<P> head, tail;

struct Q {
    int t, b, c;
    Q() {}
    Q(int _t, int _b, int _c) : t(_t), b(_b), c(_c) {}
};

vector<Q> sen;

int CIN(int n) {
    int t, l, r, c;
    int C = 0;
    FOR(i, 0, n) {
        cin >> t >> l >> r >> c;
        if (l == 1 && r == m) {
            ans = min(ans, c);
            continue;
        }
        // if (l == 1) head.push_back(P(t, l - 1, r, c));
        if (r == m) tail.push_back(P(t, l - 1, r, c));
        else {
            p[C] = P(t, l - 1, r, c);
            if (l == 1) p[C].exp = -INF;
            C++;
        }
    }
    return C;
}

void miku() {
    cin >> m >> n;
    if (n >= MXN) return;
    n = CIN(n);
    sort(p, p + n, [](P a, P b) -> bool {
        return a.time < b.time;
    });
    // for (auto &p : head) sen.push_back(Q(p.time, p.bound, p.c));
    sen.push_back(Q(0, 0, 0));
    FOR(i, 0, n) {
        // debug(i, p[i]);
        // debug(p[i].exp);
        int sml = INF;
        for (auto &j : sen) {
            if (j.t < p[i].exp) continue;
            if (j.t == p[i].time) continue;
            if (j.b < p[i].pos) continue;
            sml = min(sml, j.c);
        }
        // debug(sml);
        sen.push_back(Q(p[i].time, p[i].bound, sml + p[i].c));
    }
    for (auto &p : tail) {
        for (auto &j : sen) {
            if (j.t < p.exp) continue;
            if (j.b < p.pos) continue;
            ans = min(ans, p.c + j.c);
        }
    }
    cout << (ans == INF ? -1 : ans) << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

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