oj.uz

Submission #892797

# Submission time Handle Problem Language Result Execution time Memory
892797 2023-12-26T02:05:04 Z votranngocvy Feast (NOI19_feast) C++14
0 / 100
 284 ms 34020 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define ld long double
#define fi first
#define se second
#define mp make_pair
const int N = 3e5 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;
int a[N],pre[N],n,k;

namespace sub1 {
    bool check_condition() {
        for (int i = 1; i <= n; i++)
            if (a[i] < 0) return false;
        return true;
    }
    void solve() {
        int ans = 0;
        for (int i = 1; i <= n; i++) ans += a[i];
        cout << ans << "\n";
    }
}

namespace sub2 {
    bool check_condition() {
        int cnt = 0;
        for (int i = 1; i <= n; i++)
            if (a[i] < 0) cnt++;
        return (cnt == 1);
    }
    void solve() {
        pre[0] = 0;
        int pos = 0;
        for (int i = 1; i <= n; i++) {
            pre[i] = pre[i - 1] + a[i];
            if (a[i] < 0) pos = i;
        }
        if (k == 1) cout << max(max(pre[pos - 1],pre[n] - pre[pos]),pre[n]) << "\n";
        else cout << pre[n] - a[pos] << "\n";
    }
}

namespace sub3 {
    void solve() {
        int ans = -inf,sum = 0;
        for (int i = 1; i <= n; i++) {
            sum = max(sum + a[i],a[i]);
            ans = max(ans,sum);
        }
        cout << ans << "\n";
    }
}

namespace sub5 {
    int dp[305][305];
    void solve() {
        pre[0] = 0;
        for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] + a[i];
        dp[0][0] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= k; j++) {
                dp[i][j] = dp[i - 1][j];
                for (int z = 1; z <= i; z++)
                    dp[i][j] = max(dp[i][j],dp[z - 1][j - 1] + pre[i] - pre[z - 1]);
            }
        cout << dp[n][k] << "\n";
    }
}

namespace sub7 {
    pair<ld,int>dp[N][3];
    bool check(ld val) {
        dp[0][0] = mp(0,0),dp[0][1] = mp(-inf,0);
        for (int i = 1; i <= n; i++) {
            dp[i][0] = max(dp[i - 1][0],dp[i - 1][1]);
            dp[i][1] = max(mp(dp[i - 1][0].fi + a[i] - val,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]).se >= k);
    }
    void alien_trick() {
        ld l = 0,r = inf;
        while (l + 1e-3 < r) {
            ld mid = (l + r) / 2.0;
            if (check(mid)) l = mid;
            else r = mid;
        }
        check(l);
        cout << k * l + max(dp[n][0],dp[n][1]).fi << "\n";
    }
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    //freopen("task.inp","r",stdin);
    //freopen("task.out","w",stdout);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    /*if (sub1::check_condition()) sub1::solve();
    else if (sub2::check_condition()) sub2::solve();
    else if (k == 1) sub3::solve();
    else if (n <= 300) sub5::solve();
    else */
    sub7::alien_trick();
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 18.0

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

Subtask #4
0 / 10.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 29.0

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