void part1(std::vector<int> dm)
{
    Timer t;

    long long unsigned int result = 0;
    int i = 0,j,id_first = 0, id_last;
    j = (dm.size() % 2) ? dm.size() - 1 : dm.size() - 2;
    id_last = j / 2;
    // An individual file/empty space is different from file/empty block. Files in same block have same id.
    // i is the position of individual file/empty space
    // j is the position of file block starting from the end (decrements by 2 to keep pointing to file block)
    // id_first and id_last is the ids of files blocks.

    for(int pos = 0; pos < dm.size(); ++pos)
    {
        if( pos % 2 == 0) // even position i.e it is file block
        {
            for(int k = 0; k < dm[pos]; ++k)  // for files in block at pos
            {
                result += (id_first*i);
                ++i;
            }
            ++id_first;
        }
        else // odd position i.e. empty block
        {
            for(int k = 0; k < dm[pos]; ++k) // for empty spaces in block at pos
            {
                while(dm[j] == 0 && j > pos) //  shift j left until
                {
                    j-=2;
                    --id_last;
                }
                if(j<pos) break;

                --dm[j];
                result += (id_last*i);
                ++i;
            }
        }
        if(j<pos) break;
    }
    cout << "Part 1: " << result << endl;
}