답안 #64943 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
64943	2018-08-06T08:27:48 Z	gs18115	물탱크 (KOI18_watertank)	C++14	60 / 100	3000 ms	190744 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;
pair<pair<LL,LL>,LL>adj[MAXN][MAXN][5];
LL adjN[MAXN][MAXN];
LL dist[MAXN][MAXN];
bool inQ[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][adjN[i1][j1]++]=make_pair(make_pair(i2,j2),w);
    adj[i2][j2][adjN[i2][j2]++]=make_pair(make_pair(i1,j1),w);
    return;
}
void spfa()
{
    queue<pair<LL,LL> >Q;
    LL i;
    for(i=0;i<MAXN;i++)
        fill(dist[i],dist[i]+MAXN,INF);
    for(i=0;i<MAXN;i++)
        fill(inQ[i],inQ[i]+MAXN,false);
    dist[SC][SC]=0;
    Q.push(make_pair(SC,SC));
    while(!Q.empty())
    {
        LL hi=Q.front().first;
        LL hj=Q.front().second;
        Q.pop();
        inQ[hi][hj]=false;
        for(i=0;i<adjN[hi][hj];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]>max(wei,dist[hi][hj]))
            {
                dist[ti][tj]=max(wei,dist[hi][hj]);
                if(!inQ[ti][tj])
                {
                    inQ[ti][tj]=true;
                    Q.push(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);
        }
    }
    spfa();
    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;
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	11 ms	9208 KB	Output is correct
2	Correct	11 ms	9444 KB	Output is correct
3	Correct	14 ms	9444 KB	Output is correct
4	Correct	12 ms	9444 KB	Output is correct
5	Correct	10 ms	9444 KB	Output is correct
6	Correct	11 ms	9448 KB	Output is correct
7	Correct	11 ms	9664 KB	Output is correct
8	Correct	10 ms	9664 KB	Output is correct
9	Correct	10 ms	9724 KB	Output is correct
10	Correct	12 ms	9724 KB	Output is correct
11	Correct	10 ms	9724 KB	Output is correct

Subtask #2
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	12 ms	9724 KB	Output is correct
2	Correct	10 ms	9724 KB	Output is correct
3	Correct	14 ms	9724 KB	Output is correct
4	Correct	12 ms	9756 KB	Output is correct
5	Correct	9 ms	9756 KB	Output is correct
6	Correct	10 ms	9756 KB	Output is correct
7	Correct	9 ms	9784 KB	Output is correct
8	Correct	10 ms	9784 KB	Output is correct
9	Correct	11 ms	9784 KB	Output is correct
10	Correct	9 ms	9784 KB	Output is correct
11	Correct	10 ms	9784 KB	Output is correct
12	Correct	13 ms	9784 KB	Output is correct
13	Correct	10 ms	9864 KB	Output is correct
14	Correct	10 ms	9864 KB	Output is correct
15	Correct	9 ms	9864 KB	Output is correct
16	Correct	11 ms	9864 KB	Output is correct
17	Correct	12 ms	10016 KB	Output is correct
18	Correct	11 ms	10016 KB	Output is correct

Subtask #3
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	189 ms	10016 KB	Output is correct
2	Correct	11 ms	10016 KB	Output is correct
3	Correct	292 ms	123076 KB	Output is correct
4	Correct	406 ms	136184 KB	Output is correct
5	Correct	11 ms	136184 KB	Output is correct
6	Correct	506 ms	150448 KB	Output is correct
7	Correct	346 ms	150448 KB	Output is correct
8	Correct	449 ms	159212 KB	Output is correct
9	Correct	297 ms	159212 KB	Output is correct
10	Correct	10 ms	159212 KB	Output is correct
11	Correct	538 ms	159212 KB	Output is correct
12	Correct	10 ms	159212 KB	Output is correct

Subtask #4
21.0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	13 ms	159212 KB	Output is correct
2	Correct	10 ms	159212 KB	Output is correct
3	Correct	12 ms	159212 KB	Output is correct
4	Correct	12 ms	159212 KB	Output is correct
5	Correct	10 ms	159212 KB	Output is correct
6	Correct	10 ms	159212 KB	Output is correct
7	Correct	14 ms	159212 KB	Output is correct
8	Correct	14 ms	159212 KB	Output is correct
9	Correct	15 ms	159212 KB	Output is correct
10	Correct	15 ms	159212 KB	Output is correct
11	Correct	12 ms	159212 KB	Output is correct
12	Correct	11 ms	159212 KB	Output is correct
13	Correct	13 ms	159212 KB	Output is correct
14	Correct	10 ms	159212 KB	Output is correct
15	Correct	12 ms	159212 KB	Output is correct
16	Correct	12 ms	159212 KB	Output is correct
17	Correct	11 ms	159212 KB	Output is correct
18	Correct	14 ms	159212 KB	Output is correct
19	Correct	14 ms	159212 KB	Output is correct

Subtask #5
0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	15 ms	159212 KB	Output is correct
2	Correct	19 ms	159212 KB	Output is correct
3	Correct	12 ms	159212 KB	Output is correct
4	Correct	10 ms	159212 KB	Output is correct
5	Correct	14 ms	159212 KB	Output is correct
6	Correct	184 ms	159212 KB	Output is correct
7	Correct	12 ms	159212 KB	Output is correct
8	Correct	11 ms	159212 KB	Output is correct
9	Correct	313 ms	159212 KB	Output is correct
10	Correct	11 ms	159212 KB	Output is correct
11	Correct	11 ms	159212 KB	Output is correct
12	Correct	209 ms	159212 KB	Output is correct
13	Correct	305 ms	159212 KB	Output is correct
14	Correct	11 ms	159212 KB	Output is correct
15	Correct	329 ms	164692 KB	Output is correct
16	Correct	12 ms	164692 KB	Output is correct
17	Correct	10 ms	164692 KB	Output is correct
18	Correct	12 ms	164692 KB	Output is correct
19	Correct	433 ms	172696 KB	Output is correct
20	Correct	14 ms	172696 KB	Output is correct
21	Execution timed out	3033 ms	190744 KB	Time limit exceeded
22	Halted	0 ms	0 KB	-

답안 #64943

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 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
0 / 40.0