oj.uz

Submission #295285

# Submission time Handle Problem Language Result Execution time Memory
295285 2020-09-09T15:02:33 Z 최은수(#5799) Treatment Project (JOI20_treatment) C++17
35 / 100
 2366 ms 524292 KB 
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
const int mx=100010;
struct query
{
    int t,l,r,c;
    bool operator<(const query&x)const
    {
        return t<x.t;
    }
};
vector<pi>adj[mx];
ll dis[mx];
bool chk[mx];
inline void dijk(int n,int s)
{
    fill(dis,dis+n,INF);
    dis[s]=0;
    for(int i=0;i<n;i++)
    {
        int c=-1;
        ll mn=INF+1;
        for(int j=0;j<n;j++)
            if(!chk[j]&&dis[j]<mn)
                mn=dis[j],c=j;
        if(c==-1)
            break;
        chk[c]=1;
        for(pi&t:adj[c])
            dis[t.fi]=min(dis[t.fi],mn+t.se);
    }
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<query>qv(m);
    for(auto&t:qv)
        cin>>t.t>>t.l>>t.r>>t.c;
    for(int i=0;i<m;i++)
    {
        if(qv[i].l==1)
            adj[m+1].eb(i,qv[i].c);
        if(qv[i].r==n)
            adj[i].eb(m,0);
    }
    for(int i=0;i<m;i++)
    {
        for(int j=i+1;j<m;j++)
        {
            int tdif=abs(qv[i].t-qv[j].t);
            if(qv[i].r+1>=qv[j].l+tdif)
                adj[i].eb(j,qv[j].c);
            if(qv[j].r+1>=qv[i].l+tdif)
                adj[j].eb(i,qv[i].c);
        }
    }
    dijk(m+2,m+1);
    if(dis[m]==INF)
        dis[m]=-1;
    cout<<dis[m]<<endl;
    return 0;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 2366 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 2 ms 2688 KB Output is correct
8 Correct 2 ms 2688 KB Output is correct
9 Correct 2 ms 2688 KB Output is correct
10 Correct 2 ms 2688 KB Output is correct
11 Correct 2 ms 2688 KB Output is correct
12 Correct 2 ms 2688 KB Output is correct
13 Correct 2 ms 2688 KB Output is correct
14 Correct 2 ms 2688 KB Output is correct
15 Correct 2 ms 2688 KB Output is correct
16 Correct 2 ms 2688 KB Output is correct
17 Correct 2 ms 2688 KB Output is correct
18 Correct 2 ms 2688 KB Output is correct
19 Correct 2 ms 2744 KB Output is correct
20 Correct 537 ms 146696 KB Output is correct
21 Correct 532 ms 146552 KB Output is correct
22 Correct 152 ms 6008 KB Output is correct
23 Correct 151 ms 5880 KB Output is correct
24 Correct 389 ms 102904 KB Output is correct
25 Correct 278 ms 73592 KB Output is correct
26 Correct 230 ms 70136 KB Output is correct
27 Correct 302 ms 84088 KB Output is correct
28 Correct 413 ms 102192 KB Output is correct
29 Correct 275 ms 72952 KB Output is correct
30 Correct 262 ms 79480 KB Output is correct
31 Correct 319 ms 86264 KB Output is correct
32 Correct 521 ms 136440 KB Output is correct
33 Correct 671 ms 216184 KB Output is correct
34 Correct 476 ms 135420 KB Output is correct
35 Correct 510 ms 137208 KB Output is correct
36 Correct 665 ms 215672 KB Output is correct
37 Correct 477 ms 135712 KB Output is correct

Subtask #4
0 / 61.0

# Verdict Execution time Memory Grader output
1 Runtime error 2366 ms 524292 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -