답안 #64969 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
64969	2018-08-06T10:21:59 Z	gs18115	물탱크 (KOI18_watertank)	C++14	100 / 100	1681 ms	204840 KB

watertank

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL INF=1e18;
const LL SC=1002;
const LL MAXN=1005;
vector<pair<pair<LL,LL>,LL> >adj[MAXN][MAXN];
LL adjN[MAXN][MAXN];
LL dist[MAXN][MAXN];
LL N,M,i,j,H,a,s;
void makeedge(LL i1,LL j1,LL i2,LL j2,LL w)
{
    adj[i1][j1].push_back(make_pair(make_pair(i2,j2),w));
    adj[i2][j2].push_back(make_pair(make_pair(i1,j1),w));
    return;
}
void path()
{
    priority_queue<pair<LL,pair<LL,LL> >,vector<pair<LL,pair<LL,LL> > >,greater<pair<LL,pair<LL,LL> > > >PQ;
    LL i;
    for(i=0;i<MAXN;i++)
        fill(dist[i],dist[i]+MAXN,INF);
    PQ.push(make_pair(0,make_pair(SC,SC)));
    while(!PQ.empty())
    {
        LL hi=PQ.top().second.first;
        LL hj=PQ.top().second.second;
        LL dis=PQ.top().first;
        PQ.pop();
        if(dist[hi][hj]!=INF)
            continue;
        dist[hi][hj]=dis;
        for(i=0;i<adj[hi][hj].size();i++)
        {
            LL ti=adj[hi][hj][i].first.first;
            LL tj=adj[hi][hj][i].first.second;
            LL wei=adj[hi][hj][i].second;
            if(dist[ti][tj]==INF)
                PQ.push(make_pair(max(wei,dist[hi][hj]),make_pair(ti,tj)));
        }
    }
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>N>>M>>H;
    for(i=0;i<=N;i++)
    {
        for(j=0;j<M;j++)
        {
            cin>>a;
            if(a==-1)
                continue;
            else if(i==0)
                makeedge(i,j,SC,SC,a);
            else if(i==N)
                makeedge(i-1,j,SC,SC,a);
            else
                makeedge(i,j,i-1,j,a);
        }
    }
    for(i=0;i<N;i++)
    {
        for(j=0;j<=M;j++)
        {
            cin>>a;
            if(a==-1)
                continue;
            else if(j==0)
                makeedge(i,j,SC,SC,a);
            else if(j==M)
                makeedge(i,j-1,SC,SC,a);
            else
                makeedge(i,j,i,j-1,a);
        }
    }
    path();
    for(i=0;i<N;i++)
        for(j=0;j<M;j++)
            s+=(dist[i][j]==INF?H:dist[i][j]);
    cout<<s<<endl;
    return 0;
}

Compilation message

watertank.cpp: In function 'void path()':
watertank.cpp:36:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(i=0;i<adj[hi][hj].size();i++)
                 ~^~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	33 ms	31992 KB	Output is correct
2	Correct	35 ms	32104 KB	Output is correct
3	Correct	36 ms	32268 KB	Output is correct
4	Correct	34 ms	32268 KB	Output is correct
5	Correct	34 ms	32268 KB	Output is correct
6	Correct	32 ms	32268 KB	Output is correct
7	Correct	31 ms	32308 KB	Output is correct
8	Correct	38 ms	32308 KB	Output is correct
9	Correct	34 ms	32340 KB	Output is correct
10	Correct	37 ms	32340 KB	Output is correct
11	Correct	37 ms	32340 KB	Output is correct

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	32340 KB	Output is correct
2	Correct	31 ms	32340 KB	Output is correct
3	Correct	42 ms	32340 KB	Output is correct
4	Correct	32 ms	32472 KB	Output is correct
5	Correct	40 ms	32472 KB	Output is correct
6	Correct	38 ms	32472 KB	Output is correct
7	Correct	35 ms	32472 KB	Output is correct
8	Correct	29 ms	32472 KB	Output is correct
9	Correct	30 ms	32472 KB	Output is correct
10	Correct	30 ms	32472 KB	Output is correct
11	Correct	37 ms	32472 KB	Output is correct
12	Correct	37 ms	32472 KB	Output is correct
13	Correct	36 ms	32472 KB	Output is correct
14	Correct	34 ms	32472 KB	Output is correct
15	Correct	33 ms	32472 KB	Output is correct
16	Correct	33 ms	32472 KB	Output is correct
17	Correct	36 ms	32500 KB	Output is correct
18	Correct	37 ms	32500 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	224 ms	38004 KB	Output is correct
2	Correct	29 ms	38104 KB	Output is correct
3	Correct	186 ms	42728 KB	Output is correct
4	Correct	383 ms	69072 KB	Output is correct
5	Correct	32 ms	69072 KB	Output is correct
6	Correct	691 ms	107352 KB	Output is correct
7	Correct	263 ms	107352 KB	Output is correct
8	Correct	784 ms	148056 KB	Output is correct
9	Correct	244 ms	148056 KB	Output is correct
10	Correct	34 ms	148056 KB	Output is correct
11	Correct	957 ms	148056 KB	Output is correct
12	Correct	32 ms	148056 KB	Output is correct

Subtask #4
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	39 ms	148056 KB	Output is correct
2	Correct	34 ms	148056 KB	Output is correct
3	Correct	33 ms	148056 KB	Output is correct
4	Correct	34 ms	148056 KB	Output is correct
5	Correct	37 ms	148056 KB	Output is correct
6	Correct	35 ms	148056 KB	Output is correct
7	Correct	34 ms	148056 KB	Output is correct
8	Correct	35 ms	148056 KB	Output is correct
9	Correct	36 ms	148056 KB	Output is correct
10	Correct	52 ms	148056 KB	Output is correct
11	Correct	32 ms	148056 KB	Output is correct
12	Correct	30 ms	148056 KB	Output is correct
13	Correct	34 ms	148056 KB	Output is correct
14	Correct	31 ms	148056 KB	Output is correct
15	Correct	33 ms	148056 KB	Output is correct
16	Correct	35 ms	148056 KB	Output is correct
17	Correct	34 ms	148056 KB	Output is correct
18	Correct	38 ms	148056 KB	Output is correct
19	Correct	46 ms	148056 KB	Output is correct

Subtask #5
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	35 ms	148056 KB	Output is correct
2	Correct	34 ms	148056 KB	Output is correct
3	Correct	36 ms	148056 KB	Output is correct
4	Correct	43 ms	148056 KB	Output is correct
5	Correct	36 ms	148056 KB	Output is correct
6	Correct	207 ms	148056 KB	Output is correct
7	Correct	34 ms	148056 KB	Output is correct
8	Correct	31 ms	148056 KB	Output is correct
9	Correct	192 ms	148056 KB	Output is correct
10	Correct	35 ms	148056 KB	Output is correct
11	Correct	36 ms	148056 KB	Output is correct
12	Correct	174 ms	148056 KB	Output is correct
13	Correct	214 ms	148056 KB	Output is correct
14	Correct	33 ms	148056 KB	Output is correct
15	Correct	419 ms	148056 KB	Output is correct
16	Correct	32 ms	148056 KB	Output is correct
17	Correct	36 ms	148056 KB	Output is correct
18	Correct	30 ms	148056 KB	Output is correct
19	Correct	336 ms	148056 KB	Output is correct
20	Correct	31 ms	148056 KB	Output is correct
21	Correct	1681 ms	172724 KB	Output is correct
22	Correct	33 ms	172724 KB	Output is correct
23	Correct	32 ms	172724 KB	Output is correct
24	Correct	38 ms	172724 KB	Output is correct
25	Correct	36 ms	172724 KB	Output is correct
26	Correct	43 ms	172724 KB	Output is correct
27	Correct	35 ms	172724 KB	Output is correct
28	Correct	857 ms	172724 KB	Output is correct
29	Correct	786 ms	172724 KB	Output is correct
30	Correct	268 ms	172724 KB	Output is correct
31	Correct	805 ms	172724 KB	Output is correct
32	Correct	347 ms	172724 KB	Output is correct
33	Correct	36 ms	172724 KB	Output is correct
34	Correct	268 ms	172724 KB	Output is correct
35	Correct	39 ms	172724 KB	Output is correct
36	Correct	36 ms	172724 KB	Output is correct
37	Correct	36 ms	172724 KB	Output is correct
38	Correct	885 ms	172724 KB	Output is correct
39	Correct	1497 ms	204840 KB	Output is correct
40	Correct	44 ms	204840 KB	Output is correct
41	Correct	35 ms	204840 KB	Output is correct
42	Correct	39 ms	204840 KB	Output is correct
43	Correct	35 ms	204840 KB	Output is correct
44	Correct	272 ms	204840 KB	Output is correct
45	Correct	1436 ms	204840 KB	Output is correct
46	Correct	31 ms	204840 KB	Output is correct

답안 #64969

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 18.0 / 18.0

Subtask #3 15.0 / 15.0

Subtask #4 21.0 / 21.0

Subtask #5 40.0 / 40.0

Subtask #1
6.0 / 6.0

Subtask #2
18.0 / 18.0

Subtask #3
15.0 / 15.0

Subtask #4
21.0 / 21.0

Subtask #5
40.0 / 40.0