Submission #1315684

#	Time	Username	Problem	Language	Result	Execution time	Memory
1315684		vixtor	Global Warming (NOI13_gw)	C11	12 / 40	1095 ms	12044 KiB

gw

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

int count_islands(int N, int *H, int threshold) {
    int islands = 0;
    int in_island = 0;
    
    for (int i = 0; i < N; i++) {
        if (H[i] >= threshold) {
            if (!in_island) {
                islands++;
                in_island = 1;
            }
        } else {
            in_island = 0;
        }
    }
    
    return islands;
}

int gw(int N, int *H) {
    if (N == 0) return 0;
    
    // Create array of unique altitudes
    int *unique = (int*)malloc(N * sizeof(int));
    for (int i = 0; i < N; i++) {
        unique[i] = H[i];
    }
    
    // Sort to find unique values
    qsort(unique, N, sizeof(int), compare);
    
    // Count unique values
    int unique_count = 0;
    for (int i = 0; i < N; i++) {
        if (i == 0 || unique[i] != unique[i-1]) {
            unique[unique_count++] = unique[i];
        }
    }
    
    int max_islands = 0;
    
    // Try sea level just below each unique altitude
    for (int i = 0; i < unique_count; i++) {
        int islands = count_islands(N, H, unique[i]);
        if (islands > max_islands) {
            max_islands = islands;
        }
    }
    
    // Also try sea level at 0 (everything above water)
    int islands = count_islands(N, H, 0);
    if (islands > max_islands) {
        max_islands = islands;
    }
    
    free(unique);
    return max_islands;
}

int main() {
    int N;
    scanf("%d", &N);
    
    int *H = (int*)malloc(N * sizeof(int));
    for (int i = 0; i < N; i++) {
        scanf("%d", &H[i]);
    }
    
    int result = gw(N, H);
    printf("%d\n", result);
    
    free(H);
    return 0;
}

Compilation message (stderr)

gw.c: In function 'main':
gw.c:68:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     scanf("%d", &N);
      |     ^~~~~~~~~~~~~~~
gw.c:72:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         scanf("%d", &H[i]);
      |         ^~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 0 / 7
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11