제출 #782655

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
782655		fatemetmhr	Boxes with souvenirs (IOI15_boxes)	C++17	70 / 100	2044 ms	354516 KiB

boxes

//  ~ Be Name Khoda ~  //

#include "boxes.h"
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

const int maxn  =  1e6   + 10;
const int maxn5 =  1e7   + 10;
const int maxnt =  1.2e6 + 10;
const int maxn3 =  1e3   + 10;
const int mod   =  1e9   + 7;
const ll  inf   =  1e18;

int per[2][maxn5];
ll L, dp[2][maxn5], pos[maxn5];


ll dis(int ty, int id){
    ll x = pos[id];
    if(ty)
        return x;
    return L - x;

}

bool cmp0(int x, int y){
    return mp(dis(0, x), x) < mp(dis(0, y), y);
}

bool cmp1(int x, int y){
    return mp(dis(1, x), -x) < mp(dis(1, y), -y);
}


long long delivery(int n, int k, int l, int p[]) {
    //cout << "here " << endl;
    L = l;
    for(int i = 0; i < n; i++)
        pos[i] = p[i];
    for(int i = 0; i < n; i++){
        //cout << i << ' ' << pos[i] << ' ' << sum << endl;
        per[0][i] = per[1][i] = i;
    }
    //return sum;
    sort(per[0], per[0] + n, cmp0);
    sort(per[1], per[1] + n, cmp1);
    for(int tt = 0; tt < 2; tt++){
        for(int i = 0; i < n; i++){
            dp[tt][per[tt][i]] = (i >= k ? dp[tt][per[tt][i - k]] : 0) + dis(tt, per[tt][i]) + min(dis(0, per[tt][i]), dis(1, per[tt][i]));
            //cout << tt << ' ' << i << ' ' << dp[tt][per[tt][i]] << ' ' << per[tt][i] << endl;
        }
    }
    ll ans = min(dp[1][per[1][n - 1]], dp[0][per[0][n - 1]]);
    //cout << ans << ' ' << dp[1][per[1][n - 1]] << ' ' << dp[0][per[0][n - 1]]  << ' ' << per[0][n - 1]<< endl;
    for(int i = 0; i < n - 1; i++){
        ans = min(ans, dp[0][per[0][i]] + dp[1][per[0][i + 1]]);
        //cout << "ha? " << ans << ' ' << i << ' ' << dp[0][per[0][i]] << ' ' << dp[1][per[0][i + 1]] << ' ' << per[0][i] << ' ' << per[0][i + 1] << endl;
    }
    //cout << ans << endl;
    return ans;
}

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