Submission #12898

#	Time	Username	Problem	Language	Result	Execution time	Memory
12898		baneling100	수족관 1 (KOI13_aqua1)	C++98	100 / 100	4 ms	1192 KiB

aqua1

#include <stdio.h>
#define INF 0x7fffffff

struct line {
    int X1;
    int X2;
    int Y;
    int Hole;
} Line[5000];
int N, K, Ans;

int divideConquer(int Left, int Right, int H) {

    int i, Min=INF, Mid, res1=0, res2=0;

    if(Left==Right) {
        if(Line[Left].Hole)
            return 1;
        Ans+=(Line[Left].Y-H)*(Line[Left].X2-Line[Left].X1);
        return 0;
    }
    else {
        for(i=Left ; i<=Right ; i++)
            if(Min>Line[i].Y) {
                Min=Line[i].Y;
                Mid=i;
            }
        if(Left<=Mid-1)
            res1=divideConquer(Left ,Mid-1,Min);
        if(Mid+1<=Right)
            res2=divideConquer(Mid+1,Right,Min);
        if(res1 || res2 || Line[Mid].Hole)
            return 1;
        Ans+=(Min-H)*(Line[Right].X2-Line[Left].X1);
        return 0;
    }
}

int main(void) {

    int i, j, in1, in2, in3, in4, temp;

    scanf("%d",&N);
    scanf("%d %d",&in1,&in2);
    for(i=2 ; i<N ; i+=2) {
        scanf("%d %d %d %d",&in1,&in2,&in3,&in4);
        Line[i>>1]={in1,in3,in2,0};
    }
    scanf("%d %d %d",&in1,&in2,&K);
    for(i=1 ; i<=K ; i++) {
        scanf("%d %d %d %d",&in1,&in2,&in3,&in4);
        for(j=1 ; j<(N>>1) ; j++)
            if(Line[j].X1==in1 && Line[j].X2==in3 && Line[j].Y==in2) {
                Line[j].Hole=1;
                break;
            }
    }
    temp=divideConquer(1,(N>>1)-1,0);
    printf("%d",Ans);
    return 0;
}

• Subtask 1: 23 / 23
• Subtask 2: 19 / 19
• Subtask 3: 22 / 22
• Subtask 4: 36 / 36