Submission #57363

#	Time	Username	Problem	Language	Result	Execution time	Memory
57363		wilwxk	Land of the Rainbow Gold (APIO17_rainbow)	C++11	12 / 100	135 ms	19180 KiB

rainbow

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

const int MAXN=2e5+5;
int v[3][MAXN], cor[3][3][MAXN];
int erro[4][MAXN], soma[4][MAXN];
int kc[3][3];
int n, m;

void dfs(int k, int ind, int val) {
    for(int i=ind; i<=m; i++) {
        if(v[k][i]) return;
        cor[1][k][i]=val;
    }
}
void dfs2(int ox, int oy, int val) {
    cor[2][ox][oy]=val; int outro=((ox)%2)+1;
    if(cor[2][outro][oy]==0&&v[outro][oy]!=1) dfs2(outro, oy, val);
    if(oy+1>m) return;
    if(cor[2][ox][oy+1]==0&&v[ox][oy+1]!=1) dfs2(ox, oy+1, val);
}

void init(int R, int C, int sr, int sc, int M, char *S) {
    int cx=sr, cy=sc; n=R; m=C;
    v[cx][cy]=1;
    for(int i=0; i<M; i++) {
        if(S[i]=='N') cx--;
        if(S[i]=='S') cx++;
        if(S[i]=='W') cy--;
        if(S[i]=='E') cy++;
        v[cx][cy]=1;
    }

    kc[1][1]=1; kc[1][2]=1; kc[2][2]=1;
    for(int i=1; i<=C; i++) {
        for(int k=1; k<=2; k++) {
            if(cor[1][k][i]==0&&!v[k][i]) dfs(k, i, kc[1][k]++);
            if(cor[2][k][i]==0&&!v[k][i]) dfs2(k, i, kc[2][2]++);
        }
        soma[1][i]=max(cor[1][1][i], soma[1][i-1]);
        soma[2][i]=max(cor[1][2][i], soma[2][i-1]);
        soma[3][i]=max(soma[3][i-1], max(cor[2][1][i], cor[2][2][i]));
    }

    for(int k=1; k<=2; k++) {
        //for(int i=1; i<=m; i++) printf("%d ", soma[k][i]); printf("\n");
    }

}

int colour(int ar, int ac, int br, int bc) {
    if(ar==br) {
        int resp=soma[ar][bc]-soma[ar][ac]+1;
        if(v[ar][ac]) resp--;
        return resp;
    }
    else {
        int resp=soma[3][bc]-soma[3][ac]+1;
        if(v[1][ac]&&v[2][ac]) resp--;
        return resp;
    }

    return 0;
}

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