Submission #388941

#	Time	Username	Problem	Language	Result	Execution time	Memory
388941		cpp219	Boxes with souvenirs (IOI15_boxes)	C++14	100 / 100	792 ms	254340 KiB

boxes

#pragma GCC optimization "Ofast"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")

#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 1e7 + 6;
const ll lim = 3e5 + 6;
const ll inf = 1e16 + 7;
typedef pair<ll,ll> LL;

vector<int> v[2];
ll f[2][N],lens,k;

ll Dist(ll x,ll y){
    return min(abs(x - y),lens - abs(x - y));
}

void cal(ll cond){
    ll sz = v[cond].size();
    for (ll i = 0;i < min(sz,k);i++){
        ll now = 0;
        for (ll j = i;j < sz;j += k){
            now += Dist(0,v[cond][j]); f[cond][j] = 2*now;
        }
    }
}

ll delivery(int n,int K,int L,int pos[]){
    lens = L; k = K;
    for (ll i = 0;i < n;i++){
        if (pos[i] <= L/2) v[0].push_back(pos[i]);
        else v[1].push_back(pos[i]);
    }
    reverse(v[1].begin(),v[1].end());
    ll sz0 = v[0].size() - 1,sz1 = v[1].size() - 1;
    cal(0); cal(1); ll ans = f[0][max(0ll,sz0)] + f[1][max(0ll,sz1)];
    //cout<<f[0][2]; exit(0);
    //cout<<f[1][2]; exit(0);
    for (ll i = 1;i < k;i++){
        ll p = 0,q = 0;
        //if (sz1 - i + 1 < 0||sz0 - k + i + 1 < 0) break;
        if (sz1 - i >= 0) q = f[1][sz1 - i];
        if (sz0 - k + i >= 0) p = f[0][sz0 - k + i];
        ll now = p + L + q;
        //cout<<sz0 - k<<"x"; exit(0);
        ans = min(ans,now);
    }
    return ans;
}

Compilation message (stderr)

boxes.cpp:1: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    1 | #pragma GCC optimization "Ofast"
      | 
boxes.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      |

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