답안 #43700 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43700	2018-03-20T13:18:24 Z	dqhungdl	The Kingdom of JOIOI (JOI17_joioi)	C++14	100 / 100	1429 ms	262144 KB

joioi

#include <bits/stdc++.h>
using namespace std;

int m,n,minn=1e9,maxn=0,a[2005][2005];
bool Free[2005][2005];

int Dist()
{
    int min1=1e9,max1=0,min2=1e9,max2=0;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(Free[i][j]==false)
            {
                min1=min(min1,a[i][j]);
                max1=max(max1,a[i][j]);
            }
            else
            {
                min2=min(min2,a[i][j]);
                max2=max(max2,a[i][j]);
            }
    return max(max1-min1,max2-min2);
}

bool CheckMin(int lim)
{
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            Free[i][j]=false;
    for(int j=1;j<=n;j++)
        Free[0][j]=true;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(a[i][j]<=minn+lim&&Free[i-1][j]==true)
                Free[i][j]=true;
            else
                break;
    if(Dist()<=lim)
        return true;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            Free[i][j]=false;
    for(int j=1;j<=n;j++)
        Free[m+1][j]=true;
    for(int i=m;i>=1;i--)
        for(int j=1;j<=n;j++)
            if(a[i][j]<=minn+lim&&Free[i+1][j]==true)
                Free[i][j]=true;
            else
                break;
    if(Dist()<=lim)
        return true;
    return false;
}

bool CheckMax(int lim)
{
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            Free[i][j]=false;
    for(int j=1;j<=n;j++)
        Free[0][j]=true;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            if(a[i][j]>=maxn-lim&&Free[i-1][j]==true)
                Free[i][j]=true;
            else
                break;
    if(Dist()<=lim)
        return true;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            Free[i][j]=false;
    for(int j=1;j<=n;j++)
        Free[m+1][j]=true;
    for(int i=m;i>=1;i--)
        for(int j=1;j<=n;j++)
            if(a[i][j]>=maxn-lim&&Free[i+1][j]==true)
                Free[i][j]=true;
            else
                break;
    if(Dist()<=lim)
        return true;
    return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("TEST.INP","r",stdin);
    cin>>m>>n;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
            minn=min(minn,a[i][j]);
            maxn=max(maxn,a[i][j]);
        }
    int res,l=0,r=1e9;
    while(l<=r)
    {
        int mid=(l+r)/2;
        if(CheckMin(mid)==true||CheckMax(mid)==true)
        {
            res=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    cout<<res;
}

Compilation message

joioi.cpp: In function 'int main()':
joioi.cpp:111:14: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
     cout<<res;
              ^

Subtask #1
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	480 KB	Output is correct
3	Correct	2 ms	680 KB	Output is correct
4	Correct	2 ms	680 KB	Output is correct
5	Correct	2 ms	720 KB	Output is correct
6	Correct	2 ms	732 KB	Output is correct
7	Correct	2 ms	732 KB	Output is correct
8	Correct	2 ms	732 KB	Output is correct
9	Correct	2 ms	732 KB	Output is correct
10	Correct	2 ms	732 KB	Output is correct
11	Correct	2 ms	732 KB	Output is correct
12	Correct	2 ms	732 KB	Output is correct
13	Correct	2 ms	732 KB	Output is correct
14	Correct	2 ms	732 KB	Output is correct

Subtask #2
45.0 / 45.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	480 KB	Output is correct
3	Correct	2 ms	680 KB	Output is correct
4	Correct	2 ms	680 KB	Output is correct
5	Correct	2 ms	720 KB	Output is correct
6	Correct	2 ms	732 KB	Output is correct
7	Correct	2 ms	732 KB	Output is correct
8	Correct	2 ms	732 KB	Output is correct
9	Correct	2 ms	732 KB	Output is correct
10	Correct	2 ms	732 KB	Output is correct
11	Correct	2 ms	732 KB	Output is correct
12	Correct	2 ms	732 KB	Output is correct
13	Correct	2 ms	732 KB	Output is correct
14	Correct	2 ms	732 KB	Output is correct
15	Correct	2 ms	736 KB	Output is correct
16	Correct	9 ms	2152 KB	Output is correct
17	Correct	13 ms	2500 KB	Output is correct
18	Correct	13 ms	2692 KB	Output is correct
19	Correct	14 ms	3096 KB	Output is correct
20	Correct	14 ms	3120 KB	Output is correct
21	Correct	18 ms	3616 KB	Output is correct
22	Correct	17 ms	4088 KB	Output is correct
23	Correct	17 ms	4516 KB	Output is correct
24	Correct	14 ms	4776 KB	Output is correct
25	Correct	19 ms	5120 KB	Output is correct
26	Correct	17 ms	5508 KB	Output is correct
27	Correct	16 ms	5912 KB	Output is correct
28	Correct	20 ms	6296 KB	Output is correct

Subtask #3
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	480 KB	Output is correct
3	Correct	2 ms	680 KB	Output is correct
4	Correct	2 ms	680 KB	Output is correct
5	Correct	2 ms	720 KB	Output is correct
6	Correct	2 ms	732 KB	Output is correct
7	Correct	2 ms	732 KB	Output is correct
8	Correct	2 ms	732 KB	Output is correct
9	Correct	2 ms	732 KB	Output is correct
10	Correct	2 ms	732 KB	Output is correct
11	Correct	2 ms	732 KB	Output is correct
12	Correct	2 ms	732 KB	Output is correct
13	Correct	2 ms	732 KB	Output is correct
14	Correct	2 ms	732 KB	Output is correct
15	Correct	2 ms	736 KB	Output is correct
16	Correct	9 ms	2152 KB	Output is correct
17	Correct	13 ms	2500 KB	Output is correct
18	Correct	13 ms	2692 KB	Output is correct
19	Correct	14 ms	3096 KB	Output is correct
20	Correct	14 ms	3120 KB	Output is correct
21	Correct	18 ms	3616 KB	Output is correct
22	Correct	17 ms	4088 KB	Output is correct
23	Correct	17 ms	4516 KB	Output is correct
24	Correct	14 ms	4776 KB	Output is correct
25	Correct	19 ms	5120 KB	Output is correct
26	Correct	17 ms	5508 KB	Output is correct
27	Correct	16 ms	5912 KB	Output is correct
28	Correct	20 ms	6296 KB	Output is correct
29	Correct	955 ms	45764 KB	Output is correct
30	Correct	1039 ms	68308 KB	Output is correct
31	Correct	1010 ms	91412 KB	Output is correct
32	Correct	1115 ms	114644 KB	Output is correct
33	Correct	873 ms	132176 KB	Output is correct
34	Correct	1072 ms	157912 KB	Output is correct
35	Correct	1317 ms	196456 KB	Output is correct
36	Correct	1429 ms	230100 KB	Output is correct
37	Correct	1429 ms	262144 KB	Output is correct

답안 #43700

Compilation message

Subtask #1 15.0 / 15.0

Subtask #2 45.0 / 45.0

Subtask #3 40.0 / 40.0

Subtask #1
15.0 / 15.0

Subtask #2
45.0 / 45.0

Subtask #3
40.0 / 40.0