Submission #1315702

#TimeUsernameProblemLanguageResultExecution timeMemory
1315702vixtorGlobal Warming (NOI13_gw)C11
12 / 40
1097 ms37240 KiB
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int flood(int *h, int n, int sea) {
    int land = 0, cnt = 0;
    for(int i=0; i<n; i++) {
        if(h[i]>sea && land == 0) {
            land = 1;
            cnt++;
        }
        if(h[i]<=sea) land=0;
    }
    return cnt;
}

int pow2(int i) {
    switch(i) {
        case 0: return 1;
        case 1: return 2;
        case 2: return 4;
        case 3: return 8;
        case 4: return 16;
        case 5: return 32;
        case 6: return 64;
        case 7: return 128;
    }
}

void printv(int *h, int n) {
    for(int i=0; i<n; i++) printf("%d ", h[i]);
    printf("\n");
}

int main() {
    int n, N, *h, hh, *topo, cmin=INT_MAX, cmax=0, c, r, i, j, res, resmax=0;
    char *f;
    scanf("%d", &N);
    h = (int *)calloc(N, sizeof(int));
    topo = (int *)calloc(N, sizeof(int));
    f = (char *)calloc(134217728, sizeof(char));
    scanf("%d", &h[0]); n=1;
    for(i=1; i<N; i++) {
        scanf("%d", &hh);
        if(h[n-1]!=hh) {
            h[n] = hh;
            n++;
        }
    }

    //printv(h, n);

    N=0;
    if(h[0]>h[1]) {
        topo[N++] = h[0];
    }

    for(i=1; i<n-1; i++) {
        if(topo[N-1]<h[i] && h[i]>h[i+1]) { //avem un varf;
            topo[N++] = h[i];
        } else if(topo[N-1]>h[i] && h[i]<h[i+1]) {
            topo[N++] = h[i];
        }
    }
    
    if(h[n-1]>h[n-2]) {
        topo[N++] = h[n-1];
    }

    //printv(topo, N);
    
    for(i=0; i<N; i++) {
        c = topo[i]/8;
        r = topo[i]%8;
        f[c] = f[c] | pow2(r);
        if(c>cmax) cmax=c;
        if(c<cmin) cmin=c;
    }

    for(i=cmax; i>=cmin; i--) {
        if(f[i]!=0) {
            for(j=7; j>=0; j--) {
                if(f[i]&pow2(j)) {
                    res = flood(topo, N, i*8+j);
                    if(res>resmax) resmax=res;
                    //printf("cu apa la h=%d avem %d insule\n", i*8+j, res);
                }
            }
        }
    }
    printf("%d\n", resmax);
    
}

Compilation message (stderr)

gw.c: In function 'main':
gw.c:38:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |     scanf("%d", &N);
      |     ^~~~~~~~~~~~~~~
gw.c:42:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%d", &h[0]); n=1;
      |     ^~~~~~~~~~~~~~~~~~
gw.c:44:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |         scanf("%d", &hh);
      |         ^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...