oj.uz

Submission #1063883

# Submission time Handle Problem Language Result Execution time Memory
1063883 2024-08-18T05:34:23 Z seoul_korea Feast (NOI19_feast) C++17
12 / 100
 557 ms 26804 KB 
// Goten2308
#include<bits/stdc++.h>

using namespace std;
#define int long long
using ll = long long;
using ii = pair <int, int>;
#define fi first
#define se second 
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define BIT(x, y) ((x >> y) & 1)
#define MASK(x) (1 << x)
#define MOD 1000000007
#define MULTI_TEST1
#define __GOTEN_WILL_BE_BETTER__ signed main()
template <class T> bool maximize(T& a, T b) { if(a < b) { a = b; return true; } return false; }
template <class T> bool minimize(T& a, T b) { if(a > b) { a = b; return true; } return false; }
template <class T> void add(T& a, T b) { a += b; if(a >= MOD) a -= MOD; }
template <class T> void sub(T& a, T b) { a -= b; if(a < 0) a += MOD; }

const int maxN = 300100, INF = (int)1e18 + 7;
int n, k;
int a[maxN];

pair<int, int> solveLambda(int x) {
    vector< vector<ii> > dp(n + 1, vector<ii>(2, mp(-INF, -INF)));
    // dp[0][0] = mp(-x, 1);
    // dp[0][1] = mp(-x, 1);
    for(int i = 1; i <= n; i++) {
        dp[i][1] = mp(a[i] - x, 1);
    }
    for(int i = 1; i <= n; i++) {
        maximize(dp[i][0], max(mp(dp[i - 1][0].fi, dp[i - 1][0].se), mp(dp[i - 1][1].fi, dp[i - 1][1].se)));
        maximize(dp[i][1], max(mp(dp[i - 1][0].fi + a[i] - x, dp[i - 1][0].se + 1), mp(dp[i - 1][1].fi + a[i], dp[i - 1][1].se)));
    }
    return max(dp[n][0], dp[n][1]);
}

void solve() {
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    int l = 0, r = (int)1e9 + 7;
    while(r - l > 1) {
        int m = l + r >> 1;
        if(solveLambda(m).se >= k) l = m;
        else r = m;
    }
    cout << solveLambda(l).fi + k * l << endl;
}

__GOTEN_WILL_BE_BETTER__ {
    #define task ""
    if(fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    if(fopen("task.inp", "r")){
        freopen("task.inp", "r", stdin);
        freopen("task.out", "w", stdout);
    }
    cin.tie(0)->ios_base::sync_with_stdio(0);
    int nTest = 1;
    #ifdef MULTI_TEST
    cin >> nTest;
    #endif
    while(nTest--) {
        solve();
    }
    cout << endl;
    return 0;
}

Compilation message

feast.cpp: In function 'void solve()':
feast.cpp:47:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |         int m = l + r >> 1;
      |                 ~~^~~
feast.cpp: In function 'int main()':
feast.cpp:57:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:58:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:61:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         freopen("task.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen("task.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 26012 KB Output is correct
2 Correct 453 ms 26508 KB Output is correct
3 Correct 474 ms 26804 KB Output is correct
4 Correct 462 ms 26660 KB Output is correct
5 Correct 448 ms 26508 KB Output is correct
6 Correct 459 ms 26060 KB Output is correct
7 Correct 436 ms 26056 KB Output is correct
8 Correct 463 ms 26604 KB Output is correct
9 Correct 487 ms 26212 KB Output is correct
10 Correct 451 ms 26388 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 449 ms 24544 KB Output is correct
2 Correct 464 ms 25084 KB Output is correct
3 Correct 502 ms 24500 KB Output is correct
4 Correct 444 ms 24916 KB Output is correct
5 Correct 448 ms 26096 KB Output is correct
6 Correct 455 ms 24472 KB Output is correct
7 Correct 441 ms 25088 KB Output is correct
8 Correct 471 ms 26724 KB Output is correct
9 Correct 527 ms 26084 KB Output is correct
10 Correct 429 ms 24988 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 557 ms 26776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 447 ms 26012 KB Output is correct
2 Correct 453 ms 26508 KB Output is correct
3 Correct 474 ms 26804 KB Output is correct
4 Correct 462 ms 26660 KB Output is correct
5 Correct 448 ms 26508 KB Output is correct
6 Correct 459 ms 26060 KB Output is correct
7 Correct 436 ms 26056 KB Output is correct
8 Correct 463 ms 26604 KB Output is correct
9 Correct 487 ms 26212 KB Output is correct
10 Correct 451 ms 26388 KB Output is correct
11 Correct 449 ms 24544 KB Output is correct
12 Correct 464 ms 25084 KB Output is correct
13 Correct 502 ms 24500 KB Output is correct
14 Correct 444 ms 24916 KB Output is correct
15 Correct 448 ms 26096 KB Output is correct
16 Correct 455 ms 24472 KB Output is correct
17 Correct 441 ms 25088 KB Output is correct
18 Correct 471 ms 26724 KB Output is correct
19 Correct 527 ms 26084 KB Output is correct
20 Correct 429 ms 24988 KB Output is correct
21 Incorrect 557 ms 26776 KB Output isn't correct
22 Halted 0 ms 0 KB -