oj.uz

Submission #481764

# Submission time Handle Problem Language Result Execution time Memory
481764 2021-10-21T18:15:43 Z Lobo Boxes with souvenirs (IOI15_boxes) C++17
10 / 100
 47 ms 29404 KB 
#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 = 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])));
    }

    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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Incorrect 7 ms 16424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 29380 KB Output is correct
2 Correct 33 ms 29364 KB Output is correct
3 Correct 40 ms 29360 KB Output is correct
4 Correct 34 ms 29404 KB Output is correct
5 Correct 35 ms 29324 KB Output is correct
6 Correct 34 ms 29312 KB Output is correct
7 Correct 35 ms 29336 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB Output is correct
2 Incorrect 0 ms 428 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Incorrect 7 ms 16424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Incorrect 7 ms 16424 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Incorrect 7 ms 16424 KB Output isn't correct
3 Halted 0 ms 0 KB -