oj.uz

Submission #846870

# Submission time Handle Problem Language Result Execution time Memory
846870 2023-09-08T14:55:23 Z BamshooT Feast (NOI19_feast) C++14
22 / 100
 76 ms 11600 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <cstdlib>

#define ll long long
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define inf -1e18
#define fi first
#define se second

using namespace std;

typedef pair <ll, int> li;

const int N = 3e5 + 9, M = 2e3 + 9;
int n, k;
ll a[N], pre[N], dp[M][M];

void sub1(){

    for (int i = 1; i <= k; ++i){
        ll cur = 0;
        for (int j = 1; j <= n; ++j) {
            cur = max(cur, dp[i-1][j] - pre[j]);
            dp[i][j] = max(dp[i][j-1], cur + pre[j]);
        }
    }
    cout << dp[k][n];
}

pair<ll, int> f[N];

void maximize(li &a, li b){
    if (a.fi < b.fi) a = b;
    if (a.fi == b.fi && a.se > b.se) a = b;
}

li calc(ll cost){
    li best = {0, 0};
    for (int i = 1; i <= n; ++i) {
        f[i] = f[i-1];
        maximize(f[i], {pre[i] + best.fi - cost , best.se + 1});
        maximize(best, {f[i].fi - pre[i], f[i].se});
    }
    //f[n].se *= -1;
    return f[n];
}

void sub2(){
    ll lo = -1e14, hi = 1e14, ans = 0;
    while (lo < hi) {
        ll mid = lo + hi >> 1;
        li tmp = calc(mid);
        if (tmp.se <= k) {
            hi = mid;
        } else lo = mid + 1;
    }
    li tmp = calc(lo);
    cout << tmp.fi + k*lo;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
   // freopen("nhap.inp", "r", stdin);
  //  freopen("xuat.out", "w", stdout);
    cin >> n >> k;
    FOR(i, 1, n) {
        cin >> a[i];
        pre[i] = pre[i-1] + a[i];
    }
  //  if (max(k, n) <= 2000) sub1(); //else
    sub2();
    return 0;
}

Compilation message

feast.cpp: In function 'void sub2()':
feast.cpp:55:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |         ll mid = lo + hi >> 1;
      |                  ~~~^~~~
feast.cpp:53:31: warning: unused variable 'ans' [-Wunused-variable]
   53 |     ll lo = -1e14, hi = 1e14, ans = 0;
      |                               ^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 11600 KB Output is correct
2 Correct 44 ms 11344 KB Output is correct
3 Correct 45 ms 11472 KB Output is correct
4 Correct 43 ms 11344 KB Output is correct
5 Correct 46 ms 11352 KB Output is correct
6 Correct 44 ms 11344 KB Output is correct
7 Correct 43 ms 11352 KB Output is correct
8 Correct 44 ms 11448 KB Output is correct
9 Correct 43 ms 11344 KB Output is correct
10 Correct 45 ms 11344 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 11352 KB Output is correct
2 Correct 45 ms 11352 KB Output is correct
3 Correct 42 ms 11352 KB Output is correct
4 Correct 38 ms 11352 KB Output is correct
5 Correct 44 ms 11344 KB Output is correct
6 Correct 41 ms 11412 KB Output is correct
7 Incorrect 47 ms 11472 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 11344 KB Output is correct
2 Correct 71 ms 11352 KB Output is correct
3 Correct 76 ms 11348 KB Output is correct
4 Correct 69 ms 11344 KB Output is correct
5 Correct 71 ms 11344 KB Output is correct
6 Correct 70 ms 11344 KB Output is correct
7 Correct 72 ms 11464 KB Output is correct
8 Correct 69 ms 11344 KB Output is correct
9 Correct 70 ms 11360 KB Output is correct
10 Correct 71 ms 11464 KB Output is correct

Subtask #4
0 / 10.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 11600 KB Output is correct
2 Correct 44 ms 11344 KB Output is correct
3 Correct 45 ms 11472 KB Output is correct
4 Correct 43 ms 11344 KB Output is correct
5 Correct 46 ms 11352 KB Output is correct
6 Correct 44 ms 11344 KB Output is correct
7 Correct 43 ms 11352 KB Output is correct
8 Correct 44 ms 11448 KB Output is correct
9 Correct 43 ms 11344 KB Output is correct
10 Correct 45 ms 11344 KB Output is correct
11 Correct 46 ms 11352 KB Output is correct
12 Correct 45 ms 11352 KB Output is correct
13 Correct 42 ms 11352 KB Output is correct
14 Correct 38 ms 11352 KB Output is correct
15 Correct 44 ms 11344 KB Output is correct
16 Correct 41 ms 11412 KB Output is correct
17 Incorrect 47 ms 11472 KB Output isn't correct
18 Halted 0 ms 0 KB -