Submission #1195789

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195789		nikulid	Boxes with souvenirs (IOI15_boxes)	C++20	35 / 100	2093 ms	328 KiB

boxes

/*


IOI2015 BOXES.CPP


*/


#include "boxes.h"
#include <vector>
#include <math.h>
#include <algorithm>

using namespace std;
#define ll long long

/*
    Lemma: 
    this is dp and I will move on to q2 after getting the first subtask
[solved]
    New Lemma:
    the second subtask does not use dp.
    hence I will only move on to q2 after solving the first two subtasks
[solved]
    Even newer Lemma:
    the third subtask is brute force. 
    brute force > dp
    hence I will only move on to q2 after solving the first three subtasks
[working]
*/

vector<bool> haps;
ll gL;
bool teams_satisfied(){
    for(auto b:haps){
        if(!b)return false;
    }
    return true;
}

ll dist(ll a, ll b){
    ll A = max(a,b);
    ll B = min(a,b);
    return min(A-B, gL-A+B);
}

// pseudocode-ahh solution
// so goofy

long long delivery(int N, int K, int L, int p[]) {
    if(K==1){
        vector<int> ns;
        for(int i=0; i<N; i++){
            ns.push_back(p[i]);
        }
        ll ans=0;
        
        ll cur, furthest=0;
        for(auto e:ns){
            cur = min(e, L-e);
            ans += 2*cur;
            furthest = max(cur, furthest);
        }
        
        return ans;
    } else if(K==N){
        vector<int> ns;
        ns = {0};
        for(int i=0; i<N; i++){
            ns.push_back(p[i]);
        }

        ll ans=0;

        int biggest_gap=L-ns[N-1];

        for(int i=1; i<N; i++){
            biggest_gap = max(biggest_gap, ns[i]-ns[i-1]);
        }
        return min(L, (L-biggest_gap)*2);
    } else if(N<=10){
        // subtask 3
        gL=L;
        
        vector<int> ns;
        ll ans = 1000000000000000000;
        for(int i=0; i<N; i++){
            ns.push_back(p[i]);
        }
        //reverse(ns.begin(), ns.end());

        ll current_pos, current_steps, current_sweets, nt_it;

        //int count=0;
        do{
            //count++;
            // try to get to the teams in this specific order...
            current_pos=0;
            current_steps=0;
            current_sweets=K;
            nt_it = 0;
            while(nt_it <= N){
                if(current_sweets > 0){
                    current_steps += dist(current_pos, ns[nt_it]);
                    current_pos = ns[nt_it];
                    current_sweets--;
                    nt_it++;
                } else{
                    current_steps += dist(current_pos, 0);
                    current_pos = 0;
                    current_sweets = K;
                }
            }
            current_steps += dist(current_pos, 0);
            ans = min(ans, current_steps);
        } while(next_permutation(ns.begin(), ns.end()));

        return ans;
    }

}

Compilation message (stderr)

boxes.cpp: In function 'long long int delivery(int, int, int, int*)':
boxes.cpp:122:1: warning: control reaches end of non-void function [-Wreturn-type]
  122 | }
      | ^

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30