답안 #38824

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
38824 2018-01-06T19:33:07 Z alenam0161 UFO (IZhO14_ufo) C++14
35 / 100
2000 ms 150456 KB
#include <bits/stdc++.h>

using  namespace std;
const int inf =1e9;
int ro,cl,p,k,r;
long long **a;
int **col,**row;
void build_col(int cl,int l=1,int r= ro,int v=1){
    if(l==r){
        col[cl][v]=a[l][cl];
    }
    else{
        int m=(l+r)/2;
        build_col(cl,l,m,v+v);
        build_col(cl,m+1,r,v+v+1);
        col[cl][v]=max(col[cl][v+v],col[cl][v+v+1]);
    }
}
void build_row(int R,int l=1,int r=cl,int v=1){
    if(l==r){
        row[R][v]=a[R][l];
    }
    else{
        int m=(l+r)/2;
        build_row(R,l,m,v+v);
        build_row(R,m+1,r,v+v+1);
        row[R][v]=max(row[R][v+v],row[R][v+v+1]);
    }
}
void update_row(int rr,int val,int pos,int l=1,int r=cl,int v=1){
    if(l==r){
        row[rr][v]=val;
    }
    else{
        int m=(l+r)/2;
        if(pos<=m)update_row(rr,val,pos,l,m,v+v);
        else update_row(rr,val,pos,m+1,r,v+v+1);
        row[rr][v]=max(row[rr][v+v],row[rr][v+v+1]);
    }
}
void update_col(int cc,int val,int pos,int l=1,int r=ro,int v=1){
    if(l==r){
        col[cc][v]=val;
    }
    else{
        int m=(l+r)/2;
        if(pos<=m)update_col(cc,val,pos,l,m,v+v);
        else update_col(cc,val,pos,m+1,r,v+v+1);
        col[cc][v]=max(col[cc][v+v],col[cc][v+v+1]);
    }
}
int get_rowl(int rr,int tl,int tr,int high,int l=1,int r=cl,int v=1){
    if(tl<=l&&r<=tr){
        if(row[rr][v]>=high){
            if(l==r)return l;
            int m=(l+r)/2;
            if(row[rr][v+v]>=high)return get_rowl(rr,tl,tr,high,l,m,v+v);
            else return get_rowl(rr,tl,tr,high,m+1,r,v+v+1);
        }
        else{
            return inf;
        }
    }
    else{
        int m=(l+r)/2;
        int gf=inf;
        if(tl<=m)gf=get_rowl(rr,tl,tr,high,l,m,v+v);
        if(gf!=inf)return gf;
        return get_rowl(rr,tl,tr,high,m+1,r,v+v+1);
    }
}
int get_rowr(int rr,int tl,int tr,int high,int l=1,int r=cl,int v=1){
    if(tl<=l&&r<=tr){
        if(row[rr][v]>=high){
            if(l==r)return l;
            int m=(l+r)/2;
            if(row[rr][v+v+1]>=high)return get_rowr(rr,tl,tr,high,m+1,r,v+v+1);
            else return get_rowr(rr,tl,tr,high,l,m,v+v);
        }
        else{
            return inf;
        }
    }
    else{
        int m=(l+r)/2;
        int gf=inf;
        if(tr>m)gf=get_rowr(rr,tl,tr,high,m+1,r,v+v+1);
        if(gf!=inf)return gf;
        return get_rowr(rr,tl,tr,high,l,m,v+v);
    }
}
int get_coll(int cc,int tl,int tr,int high,int l=1,int r=ro,int v=1){
    if(tl<=l&&r<=tr){
        if(col[cc][v]>=high){
           if(l==r)return l;
           int m=(l+r)/2;
           if(col[cc][v+v]>=high)return get_coll(cc,tl,tr,high,l,m,v+v);
           else return get_coll(cc,tl,tr,high,m+1,r,v+v+1);
        }
        else return inf;
    }
    else{
        int m=(l+r)/2;
        int gf=inf;
        if(tl<=m)gf=get_coll(cc,tl,tr,high,l,m,v+v);
        if(gf!=inf)return gf;
        return get_coll(cc,tl,tr,high,m+1,r,v+v+1);
    }
}
int get_colr(int cc,int tl,int tr,int high,int l=1,int r=ro,int v=1){
    if(tl<=l&&r<=tr){
        if(col[cc][v]>=high){
           if(l==r)return l;
           int m=(l+r)/2;
           if(col[cc][v+v+1]>=high)return get_coll(cc,tl,tr,high,m+1,r,v+v+1);
           else return get_colr(cc,tl,tr,high,l,m,v+v);
        }
        else return inf;
    }
    else{
        int m=(l+r)/2;
        int gf=inf;
        if(tr>m)gf=get_colr(cc,tl,tr,high,m+1,r,v+v+1);
        if(gf!=inf)return gf;
        return get_colr(cc,tl,tr,high,l,m,v+v);
    }
}
void update(int x,int r){
    a[x][r]--;
    update_col(r,a[x][r],x);
    update_row(x,a[x][r],r);
}

int main(){
    scanf("%d%d%d%d%d",&ro,&cl,&r,&k,&p);
    a=new long long*[ro+15];
    for(int i=0;i<=ro;++i)a[i]=new long long[cl+15];
    for(int i=0;i<=ro;++i)for(int j=0;j<=cl;++j)a[i][j]=0;
    for(int i=1;i<=ro;++i)for(int j=1;j<=cl;++j){
        scanf("%d",&a[i][j]);
    }
    col=new int*[cl+10];
    for(int i=0;i<=cl;++i)col[i]=new int[ro*10];
    row=new int*[ro+10];
    for(int i=0;i<=ro;++i)row[i]=new int[cl*10];
    for(int i=1;i<=cl;++i)build_col(i);
    for(int i=1;i<=ro;++i)build_row(i);
    for(int i=1;i<=k;++i){
        char u;
        int coord,high;
       // scanf("%c",&u);
        scanf(" %c %d %d",&u,&coord,&high);
        if(u=='N'){
            int l=1;
            for(int j=1;j<=r;++j){
                int index=get_coll(coord,l,ro,high);
                if(index==inf)break;
                l=index+1;
                update(index,coord);
                if(l>ro)break;
            }
        }
        else if(u=='S'){
            int r=ro;
            for(int j=1;j<=r;++j){
                int index=get_colr(coord,1,r,high);
                if(index==inf)break;
                update(index,coord);
                r=index-1;
                if(r<1)break;
            }
        }
        else if(u=='W'){
            int l=1;
            for(int j=1;j<=r;++j){
                int index=get_rowl(coord,l,cl,high);
                if(index==inf)break;
                l=index+1;
                update(coord,index);
                if(l>cl)break;
            }
        }
        else {
            int r=cl;
            for(int j=1;j<=r;++j){
                int index=get_rowr(coord,1,r,high);
                if(index==inf)break;
                r=index-1;
                update(coord,index);
                if(r<1)break;
            }
        }

    }
    long long ans=0;
    for(int i=1;i<=ro;++i)
        for(int j=1;j<=cl;++j){
            a[i][j]=a[i][j]+a[i-1][j]+a[i][j-1]-a[i-1][j-1];
            if(i>=p&&j>=p)ans=max(ans,a[i][j]-a[i-p][j]-a[i][j-p]+a[i-p][j-p]);
        }
    cout<<ans<<endl;

    return 0;
}

Compilation message

ufo.cpp: In function 'int main()':
ufo.cpp:140:28: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'long long int*' [-Wformat=]
         scanf("%d",&a[i][j]);
                            ^
ufo.cpp:135:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d%d%d",&ro,&cl,&r,&k,&p);
                                         ^
ufo.cpp:140:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i][j]);
                             ^
ufo.cpp:152:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c %d %d",&u,&coord,&high);
                                           ^
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 2020 KB Output is correct
2 Correct 0 ms 2020 KB Output is correct
3 Incorrect 0 ms 2284 KB Output isn't correct
4 Incorrect 26 ms 2944 KB Output isn't correct
5 Execution timed out 2000 ms 6756 KB Execution timed out
6 Incorrect 1373 ms 44336 KB Output isn't correct
7 Execution timed out 2000 ms 95072 KB Execution timed out
8 Incorrect 1526 ms 95072 KB Output isn't correct
9 Correct 639 ms 91584 KB Output is correct
10 Execution timed out 2000 ms 95072 KB Execution timed out
11 Correct 536 ms 92948 KB Output is correct
12 Execution timed out 2000 ms 95072 KB Execution timed out
13 Correct 889 ms 107560 KB Output is correct
14 Execution timed out 2000 ms 92948 KB Execution timed out
15 Execution timed out 2000 ms 95072 KB Execution timed out
16 Incorrect 1923 ms 92948 KB Output isn't correct
17 Incorrect 1129 ms 107560 KB Output isn't correct
18 Correct 319 ms 97636 KB Output is correct
19 Execution timed out 2000 ms 100520 KB Execution timed out
20 Correct 1676 ms 150456 KB Output is correct