Submission #219377

#	Time	Username	Problem	Language	Result	Execution time	Memory
219377		ho94949	Treatment Project (JOI20_treatment)	C++17	35 / 100	315 ms	196600 KiB

treatment

#include <bits/stdc++.h>
using namespace std;
const int MAXM = 5000;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;
int N, M;
int T[MAXM+2], L[MAXM+2], R[MAXM+2], C[MAXM+2];
int XL[MAXM+2], YL[MAXM+2], XR[MAXM+2], YR[MAXM+2];
long long cost[MAXM+2][MAXM+2];
long long dist[MAXM+2];
bool vis[MAXM+2];
long long dijk(int N, int s, int e)
{
    memset(dist, 0x3f, sizeof dist);
    memset(vis, 0, sizeof vis);
    dist[s] = 0;
    for(int _=0; _<N; _++)
    {
        int mini = -1; long long minv = INF;
        for(int i=0; i<N; ++i)
            if(!vis[i] && minv>dist[i])
                mini = i, minv = dist[i];
        if(mini == -1) return -1;
        if(mini == e) return minv;
        vis[mini] = true;
        for(int i=0; i<N; ++i)
            dist[i] = min(dist[i], dist[mini]+cost[mini][i]);
    }
    return -1;
}
int main()
{
    scanf("%d%d", &N, &M);
    for(int i=1; i<=M; ++i)
    {
        scanf("%d%d%d%d", T+i, L+i, R+i, C+i);
        --L[i]; //L[i] = 0, R[i] = N covers whole
        XL[i] = L[i]-T[i], YL[i] = L[i]+T[i];
        XR[i] = R[i]-T[i], YR[i] = R[i]+T[i];
    }
    memset(cost, 0x3f, sizeof cost);
    for(int i=1; i<=M; ++i)
    {
        if(L[i] == 0) cost[0][i] = C[i];
        if(R[i] == N) cost[i][M+1] = 0;
    }
    for(int i=1; i<=M; ++i)
    {
        for(int j=1; j<=M; ++j)
        {
            if(i==j) continue;
            if(XL[j] <= XR[i] && YL[j] <= YR[i])
                cost[i][j] = C[j];
        }
    }
    long long ans = dijk(M+2, 0, M+1);
    printf("%lld\n", ans);
}

Compilation message (stderr)

treatment.cpp: In function 'int main()':
treatment.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &N, &M);
     ~~~~~^~~~~~~~~~~~~~~~
treatment.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d%d", T+i, L+i, R+i, C+i);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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