Submission #481765

#	Time	Username	Problem	Language	Result	Execution time	Memory
481765		Lobo	Boxes with souvenirs (IOI15_boxes)	C++17	50 / 100	60 ms	49736 KiB

boxes

#include "boxes.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
 
#define maxn 1100
 
ll n, kt;
ll mark1[maxn][maxn], dp1[maxn][maxn], x1[maxn];
ll mark2[maxn][maxn], dp2[maxn][maxn], x2[maxn];
 
ll sol1(ll i, ll k) {
    if(i == 0) return 0;
 
    if(mark1[i][k]) return dp1[i][k];
    mark1[i][k] = 1;
 
    ll ans = INFll;
    if(k != 0) {
        ans = min(ans, sol1(i,0) + 2*min(x1[i],x2[n-i+1]));
    }
 
    if(k != kt) ans = min(ans, sol1(i-1,k+1));
 
    return dp1[i][k] = ans;
 
}
 
ll sol2(ll i, ll k) {
    if(i == 0) return 0;
 
    if(mark2[i][k]) return dp2[i][k];
    mark2[i][k] = 1;
 
    ll ans = INFll;
    if(k != 0) {
        ans = min(ans, sol2(i,0) + 2*min(x1[n-i+1],x2[i]));
    }
 
    if(k != kt) ans = min(ans, sol2(i-1,k+1));
 
    return dp2[i][k] = ans;
}
 
long long delivery(int N, int K, int L, int p[]) {
    L--;
    n = N;
    kt = K;
    for(ii i = 1; i <= n; i++) {
        x1[i] = p[i-1];
        x2[i] = L-x1[i]+1;
    }
 
    reverse(x2+1,x2+1+n);
 
    ll ans = INFll;
    for(ii i = 0; i <= n; i++) {
        ans = min(ans, (sol1(i,0) + x1[i] + min(x1[i],x2[n-i+1])) + (sol2(n-i,0) + x2[n-i] + min(x2[n-i],x1[i+1])));
    }
 
    return ans;
}
 
/*
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    freopen("in.in", "r", stdin);
    //freopen("out.out", "w", stdout);
 
    ii N, K, L;
    cin >> N >> K >> L;
    vector<ii> p;
    for(ii i = 0; i < N; i++) {
        ii aa; cin >> aa;
        p.pb(aa);
    }
 
    L--;
    n = N;
    kt = K;
    for(ii i = 1; i <= n; i++) {
        x1[i] = p[i-1];
        x2[i] = L-x1[i]+1;
    }
 
    reverse(x2+1,x2+1+n);
 
    ll ans = INFii;
    for(ii i = 0; i <= n; i++) {
        ans = min(ans, (sol1(i,0) + x1[i] + min(x1[i],x2[n-i+1])) + (sol2(n-i,0) + x2[n-i] + min(x2[n-i],x1[i+1])));
    }
 
    cout << ans << endl;
 
}
*/

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