Submission #1195909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195909		nikulid	Boxes with souvenirs (IOI15_boxes)	C++20	10 / 100	0 ms	400 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
[solved]
    Newest Lemma:
    I think maybe some more why not
*/

vector<bool> haps;
ll gL;

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;
    // perhaps we can get 50...
    // pick different places to start? 

    vector<int> ns(N);
    for(int i=0; i<N; i++){
        ns[i] = p[i];
    }
    ll ans = 10000000000000000;
    ll nA;
    int tS, tE, pS, pE;
    for(int s=0; s<K; s++){
        // different starting places...
        nA=0;
        for(int i=s; i<N; i+=K){
            tS = i; // index of starting participant
            tE = (i+K-1)%N; // index of ending participant
            pS = ns[tS];
            pE = ns[tE];
            nA += dist(0, pS);
            nA += dist(pS, pE);
            nA += dist(pE, 0);
        }
        ans = min(ans, nA);
    }
    return ans;
}

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