Submission #423827

#	Time	Username	Problem	Language	Result	Execution time	Memory
423827		tqbfjotld	Treatment Project (JOI20_treatment)	C++14	35 / 100	319 ms	185924 KiB

treatment

#include <bits/stdc++.h>
using namespace std;
#define int long long

int T[5005];
int L[5005];
int R[5005];
int C[5005];
vector<int> adjl[5005];
int dist[5005];

 main(){
    int n,m;
    scanf("%lld%lld",&n,&m);
    for (int x = 0; x<m; x++){
        scanf("%lld%lld%lld%lld",&T[x],&L[x],&R[x],&C[x]);
    }
    for (int x = 0; x<m; x++){
        for (int y = 0; y<m; y++){
            if (T[y]>T[x]){
                if (L[x]-T[x]-1<=R[y]-T[y]){
                    adjl[x].push_back(y);
                }
            }
            else{
                if (L[x]+T[x]-1<=R[y]+T[y]){
                    adjl[x].push_back(y);
                }
            }
        }
    }
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > pq;
    for (int x = 0; x<m; x++){
        if (R[x]==n){
            dist[x] = C[x];
            pq.push({C[x],x});
        }
        else{
            dist[x] = 999999999999999999LL;
        }
    }
    while (!pq.empty()){
        int node = pq.top().second;
        int d = pq.top().first;
        pq.pop();
        if (d>dist[node]) continue;
        for (auto x : adjl[node]){
            if (d+C[x]<dist[x]){
               // printf("node %lld go to %lld\n",node,x);
                dist[x] = d+C[x];
                pq.push({d+C[x],x});
            }
        }
    }
    int ans = 999999999999999999LL;
    for (int x = 0; x<m; x++){
        if (L[x]==1){
            ans = min(ans,dist[x]);
        }
    }
    printf("%lld",ans==999999999999999999LL?-1LL:ans);
}

Compilation message (stderr)

treatment.cpp:12:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   12 |  main(){
      |  ^~~~
treatment.cpp: In function 'int main()':
treatment.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     scanf("%lld%lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
treatment.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |         scanf("%lld%lld%lld%lld",&T[x],&L[x],&R[x],&C[x]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 5 / 5
• Subtask 3: 30 / 30
• Subtask 4: 0 / 61