oj.uz

Submission #1069533

# Submission time Handle Problem Language Result Execution time Memory
1069533 2024-08-22T05:07:36 Z GrindMachine Tricks of the Trade (CEOI23_trade) C++17
25 / 100
 1886 ms 2097152 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

void solve(int test_case)
{
    ll n,k; cin >> n >> k;
    vector<ll> a(n+5), b(n+5);
    rep1(i,n) cin >> a[i];
    rep1(i,n) cin >> b[i];    

    vector<vector<ll>> dp(n+5,vector<ll>(k+5,-1));

    auto go = [&](ll i, ll j, auto &&go) -> ll{
        if(j == 0) return 0;
        if(i > n) return -inf2;
        if(dp[i][j] != -1) return dp[i][j];
        ll ans = max(go(i+1,j,go)-a[i],go(i+1,j-1,go)-a[i]+b[i]);
        return dp[i][j] = ans;
    };

    ll ans = -inf2;
    rep1(i,n){
        amax(ans,go(i,k,go));
    }

    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Partially correct
2 Partially correct 0 ms 460 KB Partially correct

Subtask #1
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB Partially correct
2 Partially correct 0 ms 408 KB Partially correct
3 Partially correct 0 ms 348 KB Partially correct
4 Partially correct 0 ms 604 KB Partially correct
5 Partially correct 0 ms 604 KB Partially correct
6 Partially correct 0 ms 348 KB Partially correct
7 Partially correct 0 ms 348 KB Partially correct
8 Partially correct 1 ms 564 KB Partially correct
9 Partially correct 1 ms 348 KB Partially correct
10 Partially correct 1 ms 348 KB Partially correct
11 Partially correct 0 ms 344 KB Partially correct

Subtask #2
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB Partially correct
2 Partially correct 0 ms 408 KB Partially correct
3 Partially correct 0 ms 348 KB Partially correct
4 Partially correct 0 ms 604 KB Partially correct
5 Partially correct 0 ms 604 KB Partially correct
6 Partially correct 0 ms 348 KB Partially correct
7 Partially correct 0 ms 348 KB Partially correct
8 Partially correct 1 ms 564 KB Partially correct
9 Partially correct 1 ms 348 KB Partially correct
10 Partially correct 1 ms 348 KB Partially correct
11 Partially correct 0 ms 344 KB Partially correct
12 Partially correct 0 ms 348 KB Partially correct
13 Partially correct 0 ms 348 KB Partially correct
14 Partially correct 0 ms 348 KB Partially correct
15 Partially correct 0 ms 604 KB Partially correct
16 Partially correct 1 ms 604 KB Partially correct
17 Partially correct 1 ms 348 KB Partially correct
18 Partially correct 1 ms 348 KB Partially correct
19 Partially correct 1 ms 600 KB Partially correct
20 Partially correct 0 ms 348 KB Partially correct
21 Partially correct 0 ms 348 KB Partially correct
22 Partially correct 0 ms 348 KB Partially correct
23 Partially correct 381 ms 283220 KB Partially correct
24 Partially correct 2 ms 1372 KB Partially correct
25 Partially correct 100 ms 48352 KB Partially correct
26 Partially correct 11 ms 5980 KB Partially correct
27 Partially correct 217 ms 122260 KB Partially correct
28 Partially correct 2 ms 1372 KB Partially correct
29 Partially correct 268 ms 142392 KB Partially correct

Subtask #3
5.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Partially correct
2 Partially correct 45 ms 40268 KB Partially correct
3 Partially correct 69 ms 42584 KB Partially correct
4 Partially correct 57 ms 42580 KB Partially correct
5 Partially correct 60 ms 42324 KB Partially correct
6 Partially correct 57 ms 42064 KB Partially correct
7 Partially correct 51 ms 41556 KB Partially correct
8 Partially correct 53 ms 42440 KB Partially correct
9 Partially correct 46 ms 41040 KB Partially correct
10 Partially correct 51 ms 41680 KB Partially correct

Subtask #4
10.0 / 25.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Partially correct
2 Partially correct 45 ms 40268 KB Partially correct
3 Partially correct 69 ms 42584 KB Partially correct
4 Partially correct 57 ms 42580 KB Partially correct
5 Partially correct 60 ms 42324 KB Partially correct
6 Partially correct 57 ms 42064 KB Partially correct
7 Partially correct 51 ms 41556 KB Partially correct
8 Partially correct 53 ms 42440 KB Partially correct
9 Partially correct 46 ms 41040 KB Partially correct
10 Partially correct 51 ms 41680 KB Partially correct
11 Partially correct 0 ms 348 KB Partially correct
12 Partially correct 44 ms 40560 KB Partially correct
13 Partially correct 63 ms 42676 KB Partially correct
14 Partially correct 55 ms 42576 KB Partially correct
15 Partially correct 56 ms 42324 KB Partially correct
16 Partially correct 51 ms 42212 KB Partially correct
17 Partially correct 51 ms 41552 KB Partially correct
18 Partially correct 55 ms 42508 KB Partially correct
19 Partially correct 47 ms 41044 KB Partially correct
20 Partially correct 52 ms 41548 KB Partially correct
21 Partially correct 0 ms 344 KB Partially correct
22 Partially correct 0 ms 348 KB Partially correct
23 Partially correct 0 ms 604 KB Partially correct
24 Partially correct 1 ms 604 KB Partially correct
25 Partially correct 0 ms 348 KB Partially correct
26 Partially correct 0 ms 348 KB Partially correct
27 Partially correct 0 ms 604 KB Partially correct
28 Partially correct 1 ms 348 KB Partially correct
29 Partially correct 0 ms 348 KB Partially correct
30 Partially correct 0 ms 348 KB Partially correct
31 Partially correct 1777 ms 430164 KB Partially correct
32 Partially correct 64 ms 46420 KB Partially correct
33 Partially correct 1878 ms 429652 KB Partially correct
34 Partially correct 1801 ms 429580 KB Partially correct
35 Partially correct 1840 ms 429136 KB Partially correct
36 Partially correct 1856 ms 428496 KB Partially correct
37 Partially correct 1848 ms 428056 KB Partially correct

Subtask #5
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 348 KB Partially correct
2 Partially correct 0 ms 460 KB Partially correct
3 Partially correct 1 ms 348 KB Partially correct
4 Partially correct 0 ms 408 KB Partially correct
5 Partially correct 0 ms 348 KB Partially correct
6 Partially correct 0 ms 604 KB Partially correct
7 Partially correct 0 ms 604 KB Partially correct
8 Partially correct 0 ms 348 KB Partially correct
9 Partially correct 0 ms 348 KB Partially correct
10 Partially correct 1 ms 564 KB Partially correct
11 Partially correct 1 ms 348 KB Partially correct
12 Partially correct 1 ms 348 KB Partially correct
13 Partially correct 0 ms 344 KB Partially correct
14 Partially correct 0 ms 348 KB Partially correct
15 Partially correct 0 ms 348 KB Partially correct
16 Partially correct 0 ms 348 KB Partially correct
17 Partially correct 0 ms 604 KB Partially correct
18 Partially correct 1 ms 604 KB Partially correct
19 Partially correct 1 ms 348 KB Partially correct
20 Partially correct 1 ms 348 KB Partially correct
21 Partially correct 1 ms 600 KB Partially correct
22 Partially correct 0 ms 348 KB Partially correct
23 Partially correct 0 ms 348 KB Partially correct
24 Partially correct 0 ms 348 KB Partially correct
25 Partially correct 381 ms 283220 KB Partially correct
26 Partially correct 2 ms 1372 KB Partially correct
27 Partially correct 100 ms 48352 KB Partially correct
28 Partially correct 11 ms 5980 KB Partially correct
29 Partially correct 217 ms 122260 KB Partially correct
30 Partially correct 2 ms 1372 KB Partially correct
31 Partially correct 268 ms 142392 KB Partially correct
32 Partially correct 0 ms 348 KB Partially correct
33 Partially correct 45 ms 40268 KB Partially correct
34 Partially correct 69 ms 42584 KB Partially correct
35 Partially correct 57 ms 42580 KB Partially correct
36 Partially correct 60 ms 42324 KB Partially correct
37 Partially correct 57 ms 42064 KB Partially correct
38 Partially correct 51 ms 41556 KB Partially correct
39 Partially correct 53 ms 42440 KB Partially correct
40 Partially correct 46 ms 41040 KB Partially correct
41 Partially correct 51 ms 41680 KB Partially correct
42 Partially correct 0 ms 348 KB Partially correct
43 Partially correct 44 ms 40560 KB Partially correct
44 Partially correct 63 ms 42676 KB Partially correct
45 Partially correct 55 ms 42576 KB Partially correct
46 Partially correct 56 ms 42324 KB Partially correct
47 Partially correct 51 ms 42212 KB Partially correct
48 Partially correct 51 ms 41552 KB Partially correct
49 Partially correct 55 ms 42508 KB Partially correct
50 Partially correct 47 ms 41044 KB Partially correct
51 Partially correct 52 ms 41548 KB Partially correct
52 Partially correct 0 ms 344 KB Partially correct
53 Partially correct 0 ms 348 KB Partially correct
54 Partially correct 0 ms 604 KB Partially correct
55 Partially correct 1 ms 604 KB Partially correct
56 Partially correct 0 ms 348 KB Partially correct
57 Partially correct 0 ms 348 KB Partially correct
58 Partially correct 0 ms 604 KB Partially correct
59 Partially correct 1 ms 348 KB Partially correct
60 Partially correct 0 ms 348 KB Partially correct
61 Partially correct 0 ms 348 KB Partially correct
62 Partially correct 1777 ms 430164 KB Partially correct
63 Partially correct 64 ms 46420 KB Partially correct
64 Partially correct 1878 ms 429652 KB Partially correct
65 Partially correct 1801 ms 429580 KB Partially correct
66 Partially correct 1840 ms 429136 KB Partially correct
67 Partially correct 1856 ms 428496 KB Partially correct
68 Partially correct 1848 ms 428056 KB Partially correct
69 Partially correct 1 ms 348 KB Partially correct
70 Partially correct 56 ms 40568 KB Partially correct
71 Partially correct 62 ms 42576 KB Partially correct
72 Partially correct 59 ms 42580 KB Partially correct
73 Partially correct 63 ms 42576 KB Partially correct
74 Partially correct 54 ms 42064 KB Partially correct
75 Partially correct 53 ms 41612 KB Partially correct
76 Partially correct 58 ms 42580 KB Partially correct
77 Partially correct 48 ms 41036 KB Partially correct
78 Partially correct 56 ms 41676 KB Partially correct
79 Partially correct 0 ms 348 KB Partially correct
80 Partially correct 0 ms 604 KB Partially correct
81 Partially correct 1 ms 612 KB Partially correct
82 Partially correct 1 ms 600 KB Partially correct
83 Partially correct 0 ms 348 KB Partially correct
84 Partially correct 0 ms 348 KB Partially correct
85 Partially correct 1 ms 604 KB Partially correct
86 Partially correct 0 ms 344 KB Partially correct
87 Partially correct 0 ms 344 KB Partially correct
88 Partially correct 0 ms 344 KB Partially correct
89 Partially correct 1886 ms 430168 KB Partially correct
90 Partially correct 68 ms 46364 KB Partially correct
91 Partially correct 1812 ms 429648 KB Partially correct
92 Partially correct 1764 ms 429476 KB Partially correct
93 Partially correct 1714 ms 429140 KB Partially correct
94 Partially correct 1794 ms 428412 KB Partially correct
95 Partially correct 1748 ms 428116 KB Partially correct
96 Partially correct 378 ms 283216 KB Partially correct
97 Partially correct 2 ms 1372 KB Partially correct
98 Partially correct 95 ms 48356 KB Partially correct
99 Partially correct 9 ms 5976 KB Partially correct
100 Partially correct 231 ms 122256 KB Partially correct
101 Partially correct 1 ms 1372 KB Partially correct
102 Partially correct 268 ms 142156 KB Partially correct
103 Runtime error 886 ms 2097152 KB Execution killed with signal 9
104 Halted 0 ms 0 KB -