제출 #91917

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
91917		Retro3014	Treasure (different grader from official contest) (CEOI13_treasure2)	C++17	0 / 100	2 ms	504 KiB

treasure

#include "treasure.h"
#define MAX_N 100


int sumx[MAX_N+1], sumy[MAX_N+1];
int arr[MAX_N+1][MAX_N+1];
int dp[MAX_N+1][MAX_N+1];
int vst[MAX_N+1][MAX_N+1];
int all;
int c(int x, int y, int z, int w){
    return countTreasure(x, y, z, w);
}
int n;

int calc(int x, int y, int z, int w){
    if(z==n && w==n){
        if(!vst[x][y]){
            dp[x][y]=c(x, y, z, w); vst[x][y]=true;
        }return dp[x][y];
    }
    if(x==1 && y==1){
        if(!vst[z][w]){
            dp[z][w]=c(x, y, z, w); vst[z][w]=true;
        }return dp[z][w];
    }
    if(x==1 && w==n){
        if(!vst[z][y]){
            dp[z][y]=c(x, y, z, w); vst[z][y]=true;
        }return dp[z][y];
    }
    if(y==n && z==1){
        if(!vst[x][w]){
            dp[x][w]=c(x, y, z, w); vst[x][w]=true;
        }return dp[x][w];
    }
    return 0;
}

void set(int x, int y, int z, int w, int t){
    if(z==n && w==n){
        vst[x][y]=true;
        dp[x][y]=t; return;
    }
    if(x==1 && y==1){
        vst[z][w]=true;
        dp[z][w]=t;
        return;
    }
    if(x==1 && w==n){
        vst[z][y]=true;
        dp[z][y]=t;
        return;
    }
    if(y==n && z==1){
        vst[x][w]=true;
        dp[x][w]=t;
        return;
    }
    return;
}

int kx, ky, k;

void findTreasure (int N) {n=N;
    all=calc(1, 1, N, N);
    int T = (N+1)/2;
    kx=0; ky=0;
    for(int i=1; i<T; i++){
        sumx[i]=calc(i+1, 1, N, N); sumy[i]=calc(1, i+1, N, N);
        sumx[i]=all-sumx[i]-kx; sumy[i]=all-sumy[i]-ky;
        kx+=sumx[i]; ky+=sumy[i];
    }
    sumx[T]=all-kx;  sumy[T]=all-ky;
    kx=0; ky=0;
    for(int i=N; i>T; i--){
        sumx[i]=calc(1, 1, i-1, N); sumy[i]=calc(1, 1, N, i-1);
        sumx[i]=all-sumx[i]-kx; sumy[i]=all-sumy[i]-ky;
        kx+=sumx[i]; ky+=sumy[i];
    }
    kx=0;   ky=0;
    sumx[T]-=kx; sumy[T]-=ky;
    k=0;    for(int i=1; i<=T; i++){k+=sumy[i];} set(1, 1, N, T, k);
    k=0;    for(int i=T; i<=N; i++){k+=sumy[i];} set(1, T, N, N, k);
    k=0;    for(int i=1; i<=T; i++){k+=sumx[i];} set(1, 1, T, N, k);
    k=0;    for(int i=T; i<=N; i++){k+=sumx[i];} set(T, 1, N, N, k);
    
    
    
    
    for(int i=1; i<T; i++){
        for(int j=1; j<T; j++){
            arr[i][j]=calc(i, j, N, N)-calc(i+1, j, N, N)-calc(i, j+1, N, N)+calc(i+1, j+1, N, N);
            if(arr[i][j]==1)    Report(i, j);
        }
    }
    for(int i=1; i<T; i++){
        for(int j=T+1; j<=N; j++){
            arr[i][j]=calc(i, 1, N, j)-calc(i+1, 1, N, j)-calc(i, 1, N, j-1)+calc(i+1, 1, N, j-1);
            if(arr[i][j]==1)    Report(i, j);
        }
    }
    for(int i=T+1; i<=N; i++){
        for(int j=1; j<T; j++){
            arr[i][j]=calc(1, j, i, N)-calc(1, j, i-1, N)-calc(1, j+1, i, N)+calc(1, j+1, i-1, N);
            if(arr[i][j]==1)    Report(i, j);
        }
    }
    for(int i=T+1; i<=N; i++){
        for(int j=T+1; j<=N; j++){
            arr[i][j]=calc(1, 1, i, j)-calc(1, 1, i-1, j)-calc(1, 1, i, j-1)+calc(1, 1, i-1, j-1);
            if(arr[i][j]==1)    Report(i, j);
        }
    }
    for(int i=1; i<=N; i++){
        if(i!=T){
            k=sumx[i];
            for(int j=1; j<=N; j++){
                if(j!=T){
                    k-=arr[i][j];
                }
            }
            arr[i][T]=k;
            if(arr[i][T]==1)    Report(i, T);
            k=sumy[i];
            for(int j=1; j<=N; j++){
                if(j!=T){
                    k-=arr[j][i];
                }
            }
            arr[T][i]=k;
            if(arr[T][i]==1)    Report(T, i);
        }
    }
    k=all;
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            if(!(i==T && j==T)){
                k-=arr[i][j];
            }
        }
    }
    arr[T][T]=k;
    if(arr[T][T]==1)    Report(T, T);
}

• Subtask 1: 0 / 100