Submission #19427940


Source Code Expand

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

typedef struct 
{
    long long int priority;
    long long int value; 
} heapdata;

typedef struct 
{ 
    long long int max_size; 
    long long int size; 
    heapdata *A;
} heap;

long long int left(long long int i);
long long int right(long long int i);
long long int parent(long long int i);
void heap_swap(heap *H, long long int i, long long int j);
void heapify(heap *H, long long int i);
heapdata *heapdata_new(long long int priority, long long int value);
heap *heap_build(long long int n, heapdata *A, long long int max_size);
heap *read_heap();
heapdata extract_min(heap *H);
void heap_insert(heap *H, heapdata x);
int main();

#define mymalloc(p,n) {p = malloc((n)*sizeof(*p));if ((p)==NULL) {printf("not enough memory¥n"); exit(1);};}
#define INFINITY 9999999999


long long int left(long long int i)
{
    return 2*i;
}

long long int right(long long int i)
{
    return 2*i+1;
}

long long int parent(long long int i)
{
    return i/2;
}

void heap_swap(heap *H, long long int i, long long int j)
{
    heapdata x;
    x = H->A[i];
    H->A[i] = H->A[j];
    H->A[j] = x;
}

void heapify(heap *H, long long int i)
{
    long long int l, r, smallest, size;
    heapdata *A;
    A = H->A; 
    size = H->size;
    l = left(i); 
    r = right(i);
    if (l <= size && A[l].priority < A[i].priority) 
    {
        smallest = l; 
    }
    else
    {
        smallest = i;
    }    
    if (r <= size && A[r].priority < A[smallest].priority)
    {
        smallest = r; 
    }
    if (smallest != i) 
    {
        heap_swap(H, i, smallest); 
        heapify(H, smallest); 
    }
}

heapdata *heapdata_new(long long int priority, long long int value)
{
    heapdata *x;
    x = malloc(sizeof(heapdata));
    x->priority = priority;
    x->value = value;
    return x;
}

heap *heap_build(long long int n, heapdata *A, long long int max_size)
{
    long long int i;
    heap *H;
    H = malloc(sizeof(heap)); 
    H->max_size = max_size; 
    H->size = n;
    H->A = A;
    for (i = n/2; i >= 1; i--) 
    { 
        heapify(H,i);
    }
    return H;
}

heap *read_heap()
{
    long long int n;
    long long int priority;
    long long int value;
    scanf("%lld", &n);
    heapdata *A; 
    for (long long int i=1; i <= n; i++)
    {
        scanf("%lld %lld", &priority, &value);
        A[i] = *heapdata_new(priority, value);
    }
    heap *H;
    H = heap_build(n, A, n);
    return H;
}

heapdata extract_min(heap *H)
{
    heapdata x;
    x = H->A[1];
    heap_swap(H, 1, H->size);
    H->size -= 1;
    heapify(H, 1);
    return x;
}

void heap_insert(heap *H, heapdata x) 
{
    heapdata *A;
    long long int i;
    A = H->A;
    H->size = H->size + 1;
    if (H->size > H->max_size) 
    {
        printf("ERROR ヒープのオーバーフロー¥n");
        exit(1); 
    }
    i = H->size;
    A[i] = x; // ヒープの最後に入れる (注: x はポインタでは無く実体) 
    while (i > 1 && A[i].priority < A[parent(i)].priority) 
    {
        heap_swap(H, i, parent(i));
        i = parent(i); 
    }
}

int main()
{
    int N, K, *a, *b;
    long long int total;
    heapdata *A, x, y;
    heap *H;
    scanf("%d %d", &N, &K);
    a=malloc((N+1)*sizeof(long long int));
    b=malloc((N+1)*sizeof(long long int));
    for(long long int i=1; i<=N; i++)
    {
        scanf("%d %d", &a[i], &b[i]);
    }
    A=malloc((N+1)*sizeof(heapdata));
    for (long long int i=1; i<=N; i++)
    {
        A[i].priority=a[i];
        A[i].value=i;
    }
    H=heap_build(N, A, N);
    total=0;
    for (int i=1; i<=K; i++)
    {
        x=extract_min(H);
        total+=x.priority;
        y=*heapdata_new(x.priority+b[x.value], x.value);
        heap_insert(H,y);
    }
    printf("%lld\n", total);
    free(a);free(b);free(H->A);free(H);
    return 0;
}

Submission Info

Submission Time
Task C - Factory
User Keita_S
Language C (GCC 9.2.1)
Score 300
Code Size 4006 Byte
Status AC
Exec Time 52 ms
Memory 6976 KB

Compile Error

./Main.c: In function ‘read_heap’:
./Main.c:112:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
  112 |     scanf("%lld", &n);
      |     ^~~~~~~~~~~~~~~~~
./Main.c:116:9: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
  116 |         scanf("%lld %lld", &priority, &value);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
./Main.c: In function ‘main’:
./Main.c:160:5: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
  160 |     scanf("%d %d", &N, &K);
      |     ^~~~~~~~~~~~~~~~~~~~~~
./Main.c:165:9: warning: ignoring return value of ‘scanf’, declared with attribute warn_unused_result [-Wunused-result]
  165 |         scanf("%d %d", &a[i], &b[i]);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
AC × 3
AC × 21
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_2.txt, subtask_1_3.txt, subtask_1_4.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
Case Name Status Exec Time Memory
sample_01.txt AC 7 ms 1660 KB
sample_02.txt AC 12 ms 4804 KB
sample_03.txt AC 19 ms 4736 KB
subtask_1_1.txt AC 1 ms 1704 KB
subtask_1_10.txt AC 32 ms 5900 KB
subtask_1_11.txt AC 1 ms 1628 KB
subtask_1_12.txt AC 32 ms 3768 KB
subtask_1_13.txt AC 3 ms 1696 KB
subtask_1_14.txt AC 17 ms 3080 KB
subtask_1_15.txt AC 49 ms 6976 KB
subtask_1_16.txt AC 13 ms 4732 KB
subtask_1_17.txt AC 11 ms 4748 KB
subtask_1_18.txt AC 44 ms 6960 KB
subtask_1_2.txt AC 25 ms 4828 KB
subtask_1_3.txt AC 24 ms 2516 KB
subtask_1_4.txt AC 15 ms 4784 KB
subtask_1_5.txt AC 36 ms 3772 KB
subtask_1_6.txt AC 22 ms 4944 KB
subtask_1_7.txt AC 13 ms 4180 KB
subtask_1_8.txt AC 52 ms 6932 KB
subtask_1_9.txt AC 46 ms 6572 KB