oj.uz

Submission #846918

# Submission time Handle Problem Language Result Execution time Memory
846918 2023-09-08T16:20:39 Z BamshooT Feast (NOI19_feast) C++14
22 / 100
 77 ms 13392 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:54:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |         ll mid = lo + hi >> 1;
      |                  ~~~^~~~
feast.cpp:52:31: warning: unused variable 'ans' [-Wunused-variable]
   52 |     ll lo = -1e14, hi = 1e14, ans = 0;
      |                               ^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 12876 KB Output is correct
2 Correct 45 ms 13136 KB Output is correct
3 Correct 47 ms 13268 KB Output is correct
4 Correct 47 ms 13248 KB Output is correct
5 Correct 45 ms 13136 KB Output is correct
6 Correct 44 ms 12884 KB Output is correct
7 Correct 44 ms 12880 KB Output is correct
8 Correct 45 ms 13136 KB Output is correct
9 Correct 50 ms 12884 KB Output is correct
10 Correct 48 ms 13228 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 12184 KB Output is correct
2 Correct 53 ms 12416 KB Output is correct
3 Correct 42 ms 12112 KB Output is correct
4 Correct 36 ms 12220 KB Output is correct
5 Correct 47 ms 12880 KB Output is correct
6 Correct 46 ms 12176 KB Output is correct
7 Incorrect 45 ms 12116 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 77 ms 13372 KB Output is correct
2 Correct 73 ms 13200 KB Output is correct
3 Correct 73 ms 13228 KB Output is correct
4 Correct 74 ms 13392 KB Output is correct
5 Correct 73 ms 13136 KB Output is correct
6 Correct 74 ms 13136 KB Output is correct
7 Correct 74 ms 13164 KB Output is correct
8 Correct 70 ms 13136 KB Output is correct
9 Correct 73 ms 13136 KB Output is correct
10 Correct 72 ms 13136 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 44 ms 12876 KB Output is correct
2 Correct 45 ms 13136 KB Output is correct
3 Correct 47 ms 13268 KB Output is correct
4 Correct 47 ms 13248 KB Output is correct
5 Correct 45 ms 13136 KB Output is correct
6 Correct 44 ms 12884 KB Output is correct
7 Correct 44 ms 12880 KB Output is correct
8 Correct 45 ms 13136 KB Output is correct
9 Correct 50 ms 12884 KB Output is correct
10 Correct 48 ms 13228 KB Output is correct
11 Correct 47 ms 12184 KB Output is correct
12 Correct 53 ms 12416 KB Output is correct
13 Correct 42 ms 12112 KB Output is correct
14 Correct 36 ms 12220 KB Output is correct
15 Correct 47 ms 12880 KB Output is correct
16 Correct 46 ms 12176 KB Output is correct
17 Incorrect 45 ms 12116 KB Output isn't correct
18 Halted 0 ms 0 KB -