Submission #408630

#	Time	Username	Problem	Language	Result	Execution time	Memory
408630		doowey	Treatment Project (JOI20_treatment)	C++14	35 / 100	3077 ms	4292 KiB

treatment

#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(T[nex] >= T[low]){
                    if(R[low] + 1 + T[low] >= L[nex] + T[nex]){
                        dist[nex] = min(dist[nex], dist[low] + C[nex]);
                    }
                }
                else{
                    if(L[nex] - 1 - T[nex] <= R[low] - T[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
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 0 / 61