oj.uz

Submission #1113184

# Submission time Handle Problem Language Result Execution time Memory
1113184 2024-11-16T02:55:53 Z minhvule Feast (NOI19_feast) C++17
41 / 100
 42 ms 61000 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define freo(task) if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); }
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i ++)
#define FORD(i, a, b) for(int i = (a), _b = (b); i >= _b; i --)
#define bit(x, i) ((x >> i) & 1)
#define oo 1e18
#define all(v) v.begin(), v.end()

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
// mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
// ll rand(ll l, ll r) { assert(l <= r); return uniform_int_distribution<ll>(l, r)(rd); }
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const int base = 31;
int n, k, a[N], dp[N];
/*
dp[i][j] là tổng lớn nhất khi chia i món cho j thằng
sub5: dp O(n ^ 3)
dp[i][j] = max(dp[i - 1][j], max(dp[k - 1][j]) + (a[k] -> i)
sub6: O(n ^ 2)
for(j 1->k)
    dp_divide()
sub7: dp alien trick O(nlog(n))

*/
int dp1[305][305];
void sub5(){
    FOR(i, 1, n) cin>>a[i], a[i] += a[i - 1];
    FOR(i, 1, n)
        FOR(j, 1, k){
            dp1[i][j] = dp1[i - 1][j];
            FOR(t, 1, i - 1)
                dp1[i][j] = max(dp1[i][j], dp1[t - 1][j - 1] + a[i] - a[t - 1]);
        }
    // FOR(i, 1, n) cout<<dp1[i][k]<<" ";
    cout<<dp1[n][k];
}
int dp2[2005][2005], g[2005][2005];
void sub6(){
    FOR(i, 1, n) cin>>a[i];
    FOR(i, 1, n)
        FOR(j, 1, k){
            dp2[i][j] = dp2[i - 1][j] + a[i];
            dp2[i][j] = max(dp2[i][j], g[i - 1][j - 1] + a[i]);
            g[i][j] = max(g[i - 1][j], dp2[i][j]);
        }
    int ans = 0;
    FOR(j, 1, k) ans = max(ans, g[n][j]);
    cout<<ans;
}
void solve(){
    cin>>n>>k;
    sub6();
}
int32_t main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    // freo("");
    int nTest = 1;
    // cin>>nTest;
    while(nTest --) solve();
    // cerr << "\nTime: " << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
    return 0;
}
/*



*/

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 3152 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 2640 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 3408 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1104 KB Output is correct
2 Correct 1 ms 1104 KB Output is correct
3 Correct 2 ms 848 KB Output is correct
4 Correct 1 ms 848 KB Output is correct
5 Correct 1 ms 1104 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 1 ms 1104 KB Output is correct
8 Correct 1 ms 848 KB Output is correct
9 Correct 1 ms 848 KB Output is correct
10 Correct 1 ms 848 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1104 KB Output is correct
2 Correct 1 ms 1104 KB Output is correct
3 Correct 2 ms 848 KB Output is correct
4 Correct 1 ms 848 KB Output is correct
5 Correct 1 ms 1104 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 1 ms 1104 KB Output is correct
8 Correct 1 ms 848 KB Output is correct
9 Correct 1 ms 848 KB Output is correct
10 Correct 1 ms 848 KB Output is correct
11 Correct 2 ms 2896 KB Output is correct
12 Correct 2 ms 2652 KB Output is correct
13 Correct 2 ms 2640 KB Output is correct
14 Correct 3 ms 2896 KB Output is correct
15 Correct 2 ms 2640 KB Output is correct
16 Correct 2 ms 2640 KB Output is correct
17 Correct 2 ms 3068 KB Output is correct
18 Correct 3 ms 2804 KB Output is correct
19 Correct 3 ms 2640 KB Output is correct
20 Correct 2 ms 2640 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1104 KB Output is correct
2 Correct 1 ms 1104 KB Output is correct
3 Correct 2 ms 848 KB Output is correct
4 Correct 1 ms 848 KB Output is correct
5 Correct 1 ms 1104 KB Output is correct
6 Correct 2 ms 848 KB Output is correct
7 Correct 1 ms 1104 KB Output is correct
8 Correct 1 ms 848 KB Output is correct
9 Correct 1 ms 848 KB Output is correct
10 Correct 1 ms 848 KB Output is correct
11 Correct 2 ms 2896 KB Output is correct
12 Correct 2 ms 2652 KB Output is correct
13 Correct 2 ms 2640 KB Output is correct
14 Correct 3 ms 2896 KB Output is correct
15 Correct 2 ms 2640 KB Output is correct
16 Correct 2 ms 2640 KB Output is correct
17 Correct 2 ms 3068 KB Output is correct
18 Correct 3 ms 2804 KB Output is correct
19 Correct 3 ms 2640 KB Output is correct
20 Correct 2 ms 2640 KB Output is correct
21 Correct 14 ms 22096 KB Output is correct
22 Correct 42 ms 61000 KB Output is correct
23 Correct 19 ms 27984 KB Output is correct
24 Correct 16 ms 22608 KB Output is correct
25 Correct 17 ms 25680 KB Output is correct
26 Correct 16 ms 21840 KB Output is correct
27 Correct 18 ms 24912 KB Output is correct
28 Correct 12 ms 17488 KB Output is correct
29 Correct 12 ms 17232 KB Output is correct
30 Correct 11 ms 15952 KB Output is correct

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 3152 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -