oj.uz

Submission #380198

# Submission time Handle Problem Language Result Execution time Memory
380198 2021-03-20T13:27:00 Z bibabas Holding (COCI20_holding) C++14
110 / 110
 232 ms 104172 KB 
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
// #define _FORTIFY_SOURCE 0 
// #pragma GCC optimize("Ofast") 
// #pragma GCC optimize("no-stack-protector") 
// #pragma GCC optimize("unroll-loops") 
// //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native") 
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx") 
// #pragma GCC optimize("inline") 
// #pragma GCC optimize("-fgcse") 
// #pragma GCC optimize("-fgcse-lm") 
// #pragma GCC optimize("-fipa-sra") 
// #pragma GCC optimize("-ftree-pre") 
// #pragma GCC optimize("-ftree-vrp") 
// #pragma GCC optimize("-fpeephole2") 
// #pragma GCC optimize("-ffast-math") 
// #pragma GCC optimize("-fsched-spec") 
// #pragma GCC optimize("unroll-loops") 
// #pragma GCC optimize("-falign-jumps") 
// #pragma GCC optimize("-falign-loops") 
// #pragma GCC optimize("-falign-labels") 
// #pragma GCC optimize("-fdevirtualize") 
// #pragma GCC optimize("-fcaller-saves") 
// #pragma GCC optimize("-fcrossjumping") 
// #pragma GCC optimize("-fthread-jumps") 
// #pragma GCC optimize("-funroll-loops") 
// #pragma GCC optimize("-fwhole-program") 
// #pragma GCC optimize("-freorder-blocks") 
// #pragma GCC optimize("-fschedule-insns") 
// #pragma GCC optimize("inline-functions") 
// #pragma GCC optimize("-ftree-tail-merge") 
// #pragma GCC optimize("-fschedule-insns2") 
// #pragma GCC optimize("-fstrict-aliasing") 
// #pragma GCC optimize("-fstrict-overflow") 
// #pragma GCC optimize("-falign-functions") 
// #pragma GCC optimize("-fcse-skip-blocks") 
// #pragma GCC optimize("-fcse-follow-jumps") 
// #pragma GCC optimize("-fsched-interblock") 
// #pragma GCC optimize("-fpartial-inlining") 
// #pragma GCC optimize("no-stack-protector") 
// #pragma GCC optimize("-freorder-functions") 
// #pragma GCC optimize("-findirect-inlining") 
// #pragma GCC optimize("-fhoist-adjacent-loads") 
// #pragma GCC optimize("-frerun-cse-after-loop") 
// #pragma GCC optimize("inline-small-functions") 
// #pragma GCC optimize("-finline-small-functions") 
// #pragma GCC optimize("-ftree-switch-conversion") 
// #pragma GCC optimize("-foptimize-sibling-calls") 
// #pragma GCC optimize("-fexpensive-optimizations") 
// #pragma GCC optimize("-funsafe-loop-optimizations") 
// #pragma GCC optimize("inline-functions-called-once") 
// #pragma GCC optimize("-fdelete-null-pointer-checks")
#include <bits/stdc++.h>

using namespace std;
         
#define ll long long
#define ull unsigned ll
#define vi vector<int>
#define vvi vector<vi>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define ld long double
#define pii pair<ll, ll>
#define mt make_tuple
#define mn(a, b) a = min(a, b)
#define mx(a, b) a = max(a, b)
#define base complex<ld>
 
using namespace std;
const ll INF = (ll)2e9;
const ll inf = (ll)1e18;
const ld eps = (ld)1e-12;
const ll mod = (ll)1e9 + 7;
const ll p = 31;
const ll mod2 = (ll)1e9 + 7;
const ll MAXN = (ll)51;
const ll MAXC = (ll)1e6 + 11;
const ll MAXE = (ll)100;
const ll MAXLOG = (ll)19;
const ll asci = (ll)256;
const ll block = 31623;
const ld PI = acos(-1LL);
const ld e = 2.7182818284;
         
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<
// pii,
// null_type,
// less<pii>,
// rb_tree_tag,
// tree_order_statistics_node_update>
// ordered_set;

ll int_rand() {
    if (RAND_MAX == (1LL << 15) - 1LL) {
        return (rand() << 15) + rand();
    }
    return rand();
}

ll ll_rand() {
    return ((ll)int_rand() << 30LL) + int_rand();
}

istream& operator >>(istream &in, pii &x) {
    cin >> x.first >> x.second;
    return in;
}
         
template <class T>
istream& operator >>(istream &in, vector<T> &arr){
    for (T &cnt : arr) {
        in >> cnt;
    }
    return in;
}

void solve() {
    int n, l, r, k; cin >> n >> l >> r >> k;
    --l, --r;
    vi a(n); cin >> a;
    int dp1[l + 1][r - l + 2][k + 1];
    int dp2[r - l + 2][n - r][k + 1];
    for (int i = 0; i < l + 1; ++i) {
        for (int j = 0; j < r - l + 2; ++j) {
            for (int q = 0; q < k + 1; ++q) {
                dp1[i][j][q] = INF;
            }
        }
    }
    dp1[0][0][0] = 0;
    for (int i = 0; i < r - l + 2; ++i) {
        for (int j = 0; j < n - r; ++j) {
            for (int q = 0; q < k + 1; ++q) {
                dp2[i][j][q] = INF;
            }
        }
    }
    dp2[0][0][0] = 0;
    for (int i = 0; i <= l; ++i) {
        for (int j = 0; j <= r - l + 1; ++j) {
            for (int pay = 0; pay <= k; ++pay) {
                if (i < l) mn(dp1[i + 1][j][pay], dp1[i][j][pay]);
                if (j < r - l + 1) mn(dp1[i][j + 1][pay], dp1[i][j][pay]);
                if (pay < k) mn(dp1[i][j][pay + 1], dp1[i][j][pay]);
                if (i < l && j < r - l + 1 && pay + i + j + 1 <= k) mn(
                dp1[i + 1][j + 1][pay + i + j + 1], 
                dp1[i][j][pay] + a[l - i - 1] - a[l + j]
                );
            }
        }
    }
    for (int i = 0; i <= r - l + 1; ++i) {
        for (int j = 0; j <= n - r - 1; ++j) {
            for (int pay = 0; pay <= k; ++pay) {
                if (i < r - l + 1) mn(dp2[i + 1][j][pay], dp2[i][j][pay]);
                if (j < n - r - 1) mn(dp2[i][j + 1][pay], dp2[i][j][pay]);
                if (pay < k) mn(dp2[i][j][pay + 1], dp2[i][j][pay]);
                if (i < r - l + 1 && j < n - r - 1 && pay + i + j + 1 <= k) mn(
                dp2[i + 1][j + 1][pay + i + j + 1],
                dp2[i][j][pay] - a[r - i] + a[r + j + 1]
                );
            }
        }
    }
    int cnt = 0, ans = INF;
    for (int i = l; i <= r; ++i) cnt += a[i];
    for (int mid = l - 1; mid <= r; ++mid) {
        for (int pay = 0; pay <= k; ++pay) {
            mn(ans, cnt +
            dp1[l][mid + 1 - l][pay] +
            dp2[r - mid][n - r - 1][k - pay]);
        }
    }
    cout << ans << "\n";
}

signed main() {
    srand(time(0LL));
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr); 
#endif
    cout.precision(30);
    
    solve();

    return 0LL;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 5 ms 2540 KB Output is correct

Subtask #2
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 5 ms 2540 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 2 ms 876 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 59 ms 27756 KB Output is correct

Subtask #3
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 5 ms 2540 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 2 ms 876 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 59 ms 27756 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 2 ms 904 KB Output is correct
19 Correct 59 ms 27756 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 5 ms 2540 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 2 ms 876 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 59 ms 27756 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 2 ms 904 KB Output is correct
19 Correct 59 ms 27756 KB Output is correct
20 Correct 5 ms 2156 KB Output is correct
21 Correct 4 ms 1516 KB Output is correct
22 Correct 1 ms 512 KB Output is correct
23 Correct 9 ms 4716 KB Output is correct
24 Correct 7 ms 3180 KB Output is correct
25 Correct 232 ms 104172 KB Output is correct