Submission #1195761

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

boxes

#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[]) {
    gL=L;
    
    vector<int> ns;
    ll ans = 10000000000000000;
    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;
    //return count;
}

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