oj.uz

Submission #295146

# Submission time Handle Problem Language Result Execution time Memory
295146 2020-09-09T13:49:55 Z 반딧불(#5812) Treatment Project (JOI20_treatment) C++17
35 / 100
 1858 ms 355504 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Plan{
    int t, l, r; ll cost;
    Plan(){}
    Plan(int t, int l, int r, ll cost): t(t), l(l), r(r), cost(cost){}
};
struct dat{
    int x; ll y;
    dat(){}
    dat(int x, ll y): x(x), y(y){}

    bool operator<(const dat &r)const{
        return y>r.y;
    }
};

int n, m;
Plan arr[5002];
vector<pair<int, ll> > link[5002];
priority_queue<dat> pq;
bool chk[5002];

int main(){
    scanf("%d %d", &n, &m);
    for(int i=1; i<=m; i++){
        scanf("%d %d %d %lld", &arr[i].t, &arr[i].l, &arr[i].r, &arr[i].cost);
    }

    for(int i=1; i<=m; i++){
        for(int j=1; j<=m; j++){
            if(i==j) continue;
            if(arr[j].l - 1 <= arr[i].r - abs(arr[i].t - arr[j].t)) link[i].push_back({j, arr[j].cost});
        }
    }

    for(int i=1; i<=m; i++){
        if(arr[i].l == 1) pq.push(dat(i, arr[i].cost));
    }
    while(!pq.empty()){
        dat tmp = pq.top(); pq.pop();
        if(chk[tmp.x]) continue;
        chk[tmp.x] = 1;

        if(arr[tmp.x].r == n){
            printf("%lld", tmp.y);
            return 0;
        }
        for(auto &nxt: link[tmp.x]){
            if(chk[nxt.first]) continue;
            pq.push(dat(nxt.first, tmp.y + nxt.second));
        }
    }
    printf("-1");
}

Compilation message

treatment.cpp: In function 'int main()':
treatment.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   29 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
treatment.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |         scanf("%d %d %d %lld", &arr[i].t, &arr[i].l, &arr[i].r, &arr[i].cost);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 416 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 416 KB Output is correct
20 Correct 1858 ms 278788 KB Output is correct
21 Correct 1807 ms 278724 KB Output is correct
22 Correct 48 ms 5880 KB Output is correct
23 Correct 49 ms 5892 KB Output is correct
24 Correct 225 ms 182824 KB Output is correct
25 Correct 154 ms 118008 KB Output is correct
26 Correct 144 ms 112248 KB Output is correct
27 Correct 167 ms 137848 KB Output is correct
28 Correct 233 ms 181640 KB Output is correct
29 Correct 149 ms 116092 KB Output is correct
30 Correct 145 ms 132088 KB Output is correct
31 Correct 157 ms 140920 KB Output is correct
32 Correct 306 ms 226936 KB Output is correct
33 Correct 368 ms 355504 KB Output is correct
34 Correct 359 ms 227696 KB Output is correct
35 Correct 305 ms 227192 KB Output is correct
36 Correct 371 ms 354936 KB Output is correct
37 Correct 322 ms 226680 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 896 KB Output isn't correct
2 Halted 0 ms 0 KB -