Submission

Score: 0

User: Gaygun

Problemset: รถยนต์ รถไฟ เรือเมล์ ลิเก ตำรวจ

Language: cpp

Time: 0.002 second

Submitted On: 2026-03-07 16:07:50

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

const int maxn = 30+10;
int heap[maxn];
int n;

void insertHeap(int size, int newval){
    int hold = size;
    int parent = size/2;
    while(heap[parent] < newval){
        heap[hold] = heap[parent];
        hold = parent;
        parent = hold/2;
    }
    heap[hold] = newval;
}

int deleteHeap(int size){
    int maxElement = heap[1];
    int lastElement = heap[size];
    size = size-1;
    int hold = 1;
    while(hold*2 <= size){
        int LeftChild = hold*2;
        int RightChild = hold*2+1;
        int child;
        if(heap[RightChild] < heap[LeftChild]) child = LeftChild;
        else child = RightChild; 
        // cout << LeftChild << ' ' << RightChild << ' ' << child << '\n';
        if(lastElement < heap[child]) {
            heap[hold] = heap[child];
            hold = child;
        }
        else break;
    }
    heap[hold] = lastElement;
    heap[size+1] = 0;
    return maxElement;
}


int main(){
    // cin.tie(nullptr)->sync_with_stdio(0);
    cin >> n;

    heap[0] = 2e9; // set heap[0] depend on max/min heap
    vector<int> stone(n+1);
    for(int i=1; i<=n; i++){
        cin >> stone[i];
        if(i == 1) {
            heap[i] = stone[i];
            continue;
        }
        insertHeap(i, stone[i]);
    } 
    for(int i=1; i<=n; i++){
        cout << heap[i] << ' ' ;
    }
    int i = n;
    while(i > 1){
        int x = deleteHeap(i);
        int y = deleteHeap(--i);
        if(x == y) {
            if(i == 1){
                cout << 0 << '\n';
                return 0;
            }
            --i;
            continue;
        }
        insertHeap(i, x-y);
    }
    cout << heap[1];

}

/*
11
23 15 17 13 31 10 2 4 29 14 5
*/

/*
class Solution {
public:


    void insertHeap(int size, int newval, int heap[]){
        int hold = size;
        int parent = size/2;
        while(heap[parent] < newval){
            heap[hold] = heap[parent];
            hold = parent;
            parent = hold/2;
        }
        heap[hold] = newval;
    }

    int deleteHeap(int size, int heap[]){
        int maxElement = heap[1];
        int lastElement = heap[size];
        size = size-1;
        int hold = 1;
        while(hold*2 <= size){
            int LeftChild = hold*2;
            int RightChild = hold*2+1;
            int child;
            if(heap[RightChild] < heap[LeftChild]) child = LeftChild;
            else child = RightChild; 
            if(lastElement < heap[child]) {
                heap[hold] = heap[child];
                hold = child;
            }
            else break;
        }
        heap[hold] = lastElement;
        heap[size+1] = 0;
        return maxElement;
    }
    int lastStoneWeight(vector<int>& stones) {
        int n = stones.size();
        int heap[30+10];
        heap[0] = 2e9; // set heap[0] depend on max/min heap
        for(int i=1; i<=n; i++){
            if(i == 1) {
                heap[i] = stones[i-1];
                continue;
            }
            insertHeap(i, stones[i-1],heap);
        } 

        int i = n;
        while(i > 1){
            int x = deleteHeap(i, heap);
            int y = deleteHeap(--i, heap);
            if(x == y) {
                if(i == 1){
                    return 0;
                }
                --i;
                continue;
            }
            insertHeap(i, x-y, heap);
        }
        return heap[1];
    }
};
*/