제출 #592998

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
592998		czhang2718	무지개나라 (APIO17_rainbow)	C++17	38 / 100	71 ms	20628 KiB

rainbow

#include "bits/stdc++.h"
#include "rainbow.h"
using namespace std;

const int N=1001;
int r, c, sx, sy, m;
string s;
bool g[N][N];
int ex[N][N], ey[N][N], v[N][N], two[N][N];
int lx, ly, rx, ry;

void init(int R, int C, int sr, int sc, int M, char *S) {
    r=R; c=C; sx=sr; sy=sc; m=M; s=S;
    int x=sx, y=sy;
    lx=rx=x;
    ly=ry=y;
    g[x][y]=1;
    for(char c:s){
        if(c=='N') x--;
        if(c=='S') x++;
        if(c=='W') y--;
        if(c=='E') y++;
        g[x][y]=1;
        lx=min(lx, x);
        rx=max(rx, x);
        ly=min(ly, y);
        ry=max(ry, y);
    }

    for(int i=1; i<=r; i++){
        for(int j=1; j<=c; j++){
            ex[i][j]=ex[i-1][j]+ex[i][j-1]-ex[i-1][j-1]+(!g[i][j]&&!g[i-1][j]);
            ey[i][j]=ey[i-1][j]+ey[i][j-1]-ey[i-1][j-1]+(!g[i][j]&&!g[i][j-1]);
            v[i][j]=v[i-1][j]+v[i][j-1]-v[i-1][j-1]+!g[i][j];
            two[i][j]=two[i-1][j]+two[i][j-1]-two[i-1][j-1]+(!g[i][j]&&!g[i-1][j]&&!g[i][j-1]&&!g[i-1][j-1]);
        }
    }
}

int rect(int a[][N], int x1, int y1, int x2, int y2){
    return a[x2][y2]-a[x1-1][y2]-a[x2][y1-1]+a[x1-1][y1-1];
}

int colour(int ar, int ac, int br, int bc) {
    int V=rect(v,ar,ac,br,bc);
    int E=rect(ex,ar+1,ac,br,bc)+rect(ey,ar,ac+1,br,bc);
    int F=rect(two,ar+1,ac+1,br,bc)+(ar<lx&&br>rx&&ac<ly&&bc>ry);
    // cout << V << "-" << E << "+" << F << '\n';
    return V-E+F;
}
// add 1 face if rectangles covers region!

• Subtask 1: 11 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 24
• Subtask 4: 27 / 27
• Subtask 5: 0 / 26