oj.uz

Submission #407331

# Submission time Handle Problem Language Result Execution time Memory
407331 2021-05-18T18:16:11 Z doowey Treatment Project (JOI20_treatment) C++14
0 / 100
 3000 ms 4296 KB 
#include <bits/stdc++.h>

using namespace std;

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

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)1e5 + 10;
const ll inf = (ll)1e18;
ll T[N];
ll L[N];
ll R[N];
ll C[N];

ll dist[N];
bool pro[N];

int main(){
    fastIO;
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i ++ ){
        cin >> T[i] >> L[i] >> R[i] >> C[i];
    }
    for(int i = 1; i <= m ; i ++ ){
        dist[i] = inf;
        if(L[i] == 1){
            dist[i] = C[i];
        }
    }
    int low = -1;
    ll outp = inf;
    for(int go = 1; go <= m ; go ++ ){
        low = -1;
        for(int i = 1; i <= m ; i ++ ){
            if(pro[i]) continue;
            if(dist[i] == inf) continue;
            if(low == -1 || dist[i] < dist[low]){
                low = i;
            }
        }
        if(low == -1) break;
        pro[low] = true;
        if(R[low] == n){
            outp = min(outp, dist[low]);
        }
        for(int nex = 1; nex <= m ; nex ++ ){
            if(pro[nex]) continue;
            if(L[nex] > L[low]){
                if(T[nex] >= T[low]){
                    if(R[low] + 1 - (T[nex] - T[low]) >= L[nex]){
                        dist[nex] = min(dist[nex], dist[low] + C[nex]);
                    }
                }
                else{
                    if((L[nex] - 1) + (T[low] - T[nex]) <= R[low]){
                        dist[nex] = min(dist[nex], dist[low] + C[nex]);
                    }
                }
            }
        }
    }
    if(outp == inf)
        cout << "-1\n";
    else
        cout << outp << "\n";
    return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3079 ms 4296 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3079 ms 4296 KB Time limit exceeded
2 Halted 0 ms 0 KB -