oj.uz

Submission #854421

# Submission time Handle Problem Language Result Execution time Memory
854421 2023-09-27T15:04:59 Z fanwen Treatment Project (JOI20_treatment) C++17
35 / 100
 500 ms 524288 KB 
#include <bits/stdc++.h>

using namespace std;

#define MASK(x) (1LL << (x))
#define BIT(x, i) (((x) >> (i)) & 1)
#define ALL(x) (x).begin(), (x).end()
#define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define FORE(i, a, b) for (int i = (a), _b = (b); i < _b; ++i)
#define debug(...) "[" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }

template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }

template <class num_t>
struct Dijkstra {
    int n; bool undirected;
    const num_t INF = (num_t) 1e18;
    vector <vector <pair <int, num_t>>> adj;
    vector <num_t> dist;
    priority_queue <pair <num_t, int>, vector <pair <num_t, int>>, greater <pair <num_t, int>>> q;

    Dijkstra(int _n = 0, bool undirected = true) : undirected(undirected) {
        resize(_n);
    } 

    void resize(int _n) {
        n = _n;
        dist.resize(n + 1);
        adj.assign(n + 1, vector <pair <int, num_t>>{});
    }

    void addedges(int u, int v, num_t w) {
        adj[u].emplace_back(v, w);
        if(undirected) adj[v].emplace_back(u, w);
    }

    num_t min_dist(int source, int sink) {
        fill(dist.begin(), dist.end(), INF);
        q.emplace(dist[source] = 0, source);
        while(!q.empty()) {
            auto [du, u] = q.top(); q.pop();
            if(dist[u] != du) continue;
            for (auto [v, w] : adj[u]) if(dist[v] > du + w) {
                dist[v] = du + w;
                q.emplace(dist[v], v);
            }
        }
        return dist[sink];
    }
};

const int MAXN = 1e5 + 5;

struct Data {
	int T, L, R, C;
} A[MAXN];

int N, M;
long long dp[MAXN];

void you_make_it(void) {
    cin >> N >> M;
    Dijkstra <long long> T(M + 1, false);
    FOR(i, 1, M) {
    	cin >> A[i].T >> A[i].L >> A[i].R >> A[i].C;
    	if(A[i].L == 1) T.addedges(0, i, A[i].C);
    	if(A[i].R == N) T.addedges(i, M + 1, 0);
    }
    FOR(i, 1, M) FOR(j, 1, M) if(i != j) {
    	if(A[i].R - abs(A[i].T - A[j].T) + 1 >= A[j].L) {
    		T.addedges(i, j, A[j].C);
    	}
    }
    long long ans = T.min_dist(0, M + 1);
    cout << (ans >= 1E18 ? -1 : ans);
}


signed main() {

#ifdef LOCAL
    freopen("TASK.inp", "r", stdin);
    freopen("TASK.out", "w", stdout);
#endif
    auto start_time = chrono::steady_clock::now();

    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

    you_make_it();

    auto end_time = chrono::steady_clock::now();

    cerr << "\nExecution time : " << chrono::duration_cast <chrono::milliseconds> (end_time - start_time).count() << "[ms]" << endl;

    return (0 ^ 0);
}

// Dream it. Wish it. Do it.

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 500 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2496 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2512 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2512 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Correct 0 ms 2396 KB Output is correct
17 Correct 1 ms 2392 KB Output is correct
18 Correct 1 ms 2648 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2496 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2652 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2512 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 1 ms 2512 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Correct 0 ms 2396 KB Output is correct
17 Correct 1 ms 2392 KB Output is correct
18 Correct 1 ms 2648 KB Output is correct
19 Correct 1 ms 2396 KB Output is correct
20 Correct 250 ms 247952 KB Output is correct
21 Correct 251 ms 247928 KB Output is correct
22 Correct 34 ms 7812 KB Output is correct
23 Correct 46 ms 7764 KB Output is correct
24 Correct 164 ms 176468 KB Output is correct
25 Correct 115 ms 119696 KB Output is correct
26 Correct 100 ms 114348 KB Output is correct
27 Correct 118 ms 140048 KB Output is correct
28 Correct 164 ms 175184 KB Output is correct
29 Correct 110 ms 118276 KB Output is correct
30 Correct 100 ms 133720 KB Output is correct
31 Correct 108 ms 142672 KB Output is correct
32 Correct 245 ms 228756 KB Output is correct
33 Correct 300 ms 357200 KB Output is correct
34 Correct 243 ms 228692 KB Output is correct
35 Correct 263 ms 228900 KB Output is correct
36 Correct 303 ms 356948 KB Output is correct
37 Correct 234 ms 228232 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Runtime error 500 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -