oj.uz

Submission #923762

# Submission time Handle Problem Language Result Execution time Memory
923762 2024-02-07T17:56:52 Z Karoot Feast (NOI19_feast) C++17
63 / 100
 775 ms 81504 KB 
#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>
#include <chrono>

#define all(x)  (x).begin(), (x).end()
#define rall(x)  (x).rbegin(), (x).rend()

using namespace std;

typedef long long ll;

ll linf = 1e15+1;

inline void scoobydoobydoo(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}

const int MAXN = 3e5+3;
ll arr[MAXN];
pair<long double, ll> mem[MAXN][2];
ll n, k; 
bool isVisited[MAXN][2];

long double lambda;

pair<long double, ll> dp(ll index, int inInterval){
    if (index == n) return {0, 0};
    if (isVisited[index][inInterval])return mem[index][inInterval];
    isVisited[index][inInterval] = true;
    if (inInterval){
        //fortsätt -> ingen penalty
        pair<long double, ll> cont = {dp(index+1, 1).first+arr[index], dp(index+1, 1).second};

        pair<long double, ll> stop = {dp(index+1, 0).first, dp(index+1, 0).second};

        //stanna -> penalty
        return mem[index][inInterval] = max(cont, stop);
    } else {
        //köp inget
        pair<long double, ll> cont = {dp(index+1, 0).first, dp(index+1, 0).second};

        //starta
        pair<long double, ll> start = {dp(index+1, 1).first + arr[index] - lambda, dp(index+1, 1).second+1};
        return mem[index][inInterval] = max(cont, start);
    }
}

bool check(long double la){
    lambda = la;
    for (int i = 0; i < n; i++){
        isVisited[i][0] = false;
        isVisited[i][1] = false;
    }
    //cout << la << " " << dp(0, 0).first << " " << dp(0, 0).second << endl;
    return dp(0,0).second >= k; 
}

int main(){
    scoobydoobydoo();
    cin >> n >> k;
    for (int i = 0; i < n; i++)cin >> arr[i];

    long double a = 0, b = 1e15;

    chrono::time_point<chrono::system_clock> start, end;

    start = chrono::system_clock::now();

    while (a+(1e-3) < b){
        long double mid = (a+b)/2.0;
        if (check(mid)){
            a = mid;
        } else {
            b = mid;
        }
        end = chrono::system_clock::now();
        chrono::duration<double> elapsed_seconds = end - start;
        if (elapsed_seconds.count() > 0.69)break;
    }

    check(a);
    //cout << fixed << setprecision(5);
    //cout << a << endl;

    //cout << check(6.99) << endl;
    //cout << check(7.99) << endl;

    ll ans = round(a*k + mem[0][0].first);
    
    cout << ans << endl;


    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 775 ms 76680 KB Output is correct
2 Correct 737 ms 80624 KB Output is correct
3 Correct 724 ms 81488 KB Output is correct
4 Correct 737 ms 80892 KB Output is correct
5 Correct 728 ms 80568 KB Output is correct
6 Correct 740 ms 79532 KB Output is correct
7 Correct 752 ms 79292 KB Output is correct
8 Correct 742 ms 80724 KB Output is correct
9 Correct 747 ms 79412 KB Output is correct
10 Correct 757 ms 80288 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 770 ms 77844 KB Output is correct
2 Correct 741 ms 80092 KB Output is correct
3 Correct 744 ms 80724 KB Output is correct
4 Correct 743 ms 80144 KB Output is correct
5 Correct 762 ms 80520 KB Output is correct
6 Correct 761 ms 80980 KB Output is correct
7 Correct 750 ms 81280 KB Output is correct
8 Correct 747 ms 80724 KB Output is correct
9 Correct 753 ms 81504 KB Output is correct
10 Correct 754 ms 81492 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 2 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 2 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 2 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 2 ms 4444 KB Output is correct
20 Correct 2 ms 4444 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4440 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 1 ms 4440 KB Output is correct
10 Correct 1 ms 4444 KB Output is correct
11 Correct 2 ms 4444 KB Output is correct
12 Correct 2 ms 4444 KB Output is correct
13 Correct 1 ms 4444 KB Output is correct
14 Correct 2 ms 4444 KB Output is correct
15 Correct 1 ms 4444 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 2 ms 4444 KB Output is correct
18 Correct 1 ms 4444 KB Output is correct
19 Correct 2 ms 4444 KB Output is correct
20 Correct 2 ms 4444 KB Output is correct
21 Correct 6 ms 4700 KB Output is correct
22 Correct 6 ms 4932 KB Output is correct
23 Correct 7 ms 4700 KB Output is correct
24 Correct 6 ms 4700 KB Output is correct
25 Correct 7 ms 4700 KB Output is correct
26 Correct 6 ms 4700 KB Output is correct
27 Correct 7 ms 4700 KB Output is correct
28 Correct 6 ms 4700 KB Output is correct
29 Correct 6 ms 4700 KB Output is correct
30 Correct 6 ms 4700 KB Output is correct

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 775 ms 76680 KB Output is correct
2 Correct 737 ms 80624 KB Output is correct
3 Correct 724 ms 81488 KB Output is correct
4 Correct 737 ms 80892 KB Output is correct
5 Correct 728 ms 80568 KB Output is correct
6 Correct 740 ms 79532 KB Output is correct
7 Correct 752 ms 79292 KB Output is correct
8 Correct 742 ms 80724 KB Output is correct
9 Correct 747 ms 79412 KB Output is correct
10 Correct 757 ms 80288 KB Output is correct
11 Correct 740 ms 77084 KB Output is correct
12 Incorrect 728 ms 79532 KB Output isn't correct
13 Halted 0 ms 0 KB -