Submission #1091221

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091221		kolorvxl	Giraffes (JOI22_giraffes)	C11	59 / 100	252 ms	218964 KiB

giraffes

#include <stdio.h>

int n;
int arr[302];

int cost[302][302][302] = {0};

void apply(int *a, int b) {
    if (*a > b) {
        *a = b;
    }
}

int get_cost(int start, int end, int offset) {
    if (end == start) {
        return arr[start - 1] != (offset + 1);
    }
    
    if (cost[start][end][offset] == -1) {
        int length = end - start + 1;
        int min = offset + 1;
        int max = length + offset; 
        
        int costtmp = 10000;
        
        apply(&costtmp, get_cost(start + 1, end, offset + 1) + (min != arr[start- 1]));
        apply(&costtmp, get_cost(start + 1, end, offset) + (max != arr[start- 1]));
        apply(&costtmp, get_cost(start, end - 1, offset + 1) + (min != arr[end- 1]));
        apply(&costtmp, get_cost(start, end - 1, offset) + (max != arr[end- 1]));
        
        cost[start][end][offset] = costtmp;
        // printf("%d %d  %d %d   %d\n", start, end, min, max, costtmp);
    }
    
    return cost[start][end][offset];
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }
    
    for (int i = 0; i < n + 1; i++) {
        for (int j = 0; j < n + 1; j++) {
            for (int k = 0; k < n + 1; k++) {
                cost[i][j][k] = -1;
            }
        }
    }
    
    printf("%d", get_cost(1, n, 0));
    
    return 0;
}

Compilation message (stderr)

giraffes.c: In function 'main':
giraffes.c:39:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf("%d", &n);
      |     ^~~~~~~~~~~~~~~
giraffes.c:41:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf("%d", &arr[i]);
      |         ^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 0 / 41