글 읽기 - 어디가 틀린걸까요

andy627 7년 전 0

예제도 맞고 다른 예시를 넣어도 맞는거 같은데...

틀린 예시나 어디가 틀렸는지 알려주세요ㅜㅜ

#include <stdio.h>
#include <queue>
using namespace std;

int qst[1111][1111];
int qx[1111][1111],qy[1111][1111];
int qdp[1111][1111];

int cnt[1111][1111];
int cx[1111][1111],cy[1111][1111];
int cdp[1111][1111];

bool is_gone[1111][1111];
queue<int> xx,yy;

int bfs(){
    int mx=cdp[1][1];
    while(!xx.empty()){
        int nx=xx.front();
        int ny=yy.front();
        if(2+qdp[nx][ny]>=2000) return cdp[1000][1000];

        for(int i=nx;i<=2+qdp[nx][ny]-nx;i++){
            if(i>1000) break;
            if(2+qdp[nx][ny]-i<ny) break;
            if(!is_gone[i][2+qdp[nx][ny]-i]){
                xx.push(i);
                yy.push(2+qdp[nx][ny]-i);
                is_gone[i][2+qdp[nx][ny]-i]=1;
                mx=max(mx,cdp[i][2+qdp[nx][ny]-i]);
            }
        }
        xx.pop();
        yy.pop();
    }
    return mx;
}

int main(){
    int n,st,in,po,sum=0;
    
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d %d %d",&st,&in,&po);
        qst[st][in]+=po;
        cnt[st][in]++;
        sum+=po;
    }

    for(int i=1000;i>0;i--){
        for(int j=1000;j>0;j--) qx[i][j]=qx[i][j+1]+qst[i][j];
    }
    for(int j=1000;j>0;j--){
        for(int i=1000;i>0;i--) qy[i][j]=qy[i+1][j]+qst[i][j];
    }

    for(int i=1000;i>0;i--){
        for(int j=1000;j>0;j--) cx[i][j]=cx[i][j+1]+cnt[i][j];
    }
    for(int j=1000;j>0;j--){
        for(int i=1000;i>0;i--) cy[i][j]=cy[i+1][j]+cnt[i][j];
    }

    qdp[1000][1000]=sum;
    for(int i=1000;i>0;i--){
        for(int j=1000;j>0;j--){
            qdp[i-1][j]=max(qdp[i-1][j],qdp[i][j]-qx[i][j+1]);
            qdp[i][j-1]=max(qdp[i][j-1],qdp[i][j]-qy[i+1][j]);
        }
    }

    cdp[1000][1000]=n;
    for(int i=1000;i>0;i--){
        for(int j=1000;j>0;j--){
            cdp[i-1][j]=max(cdp[i-1][j],cdp[i][j]-cx[i][j+1]);
            cdp[i][j-1]=max(cdp[i][j-1],cdp[i][j]-cy[i+1][j]);
        }
    }

    xx.push(1);
    yy.push(1);
    is_gone[1][1]=1;

    printf("%d",bfs());

    return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

어디가 틀린걸까요

andy627 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말