oj.uz

Submission #853385

# Submission time Handle Problem Language Result Execution time Memory
853385 2023-09-24T09:08:28 Z taitruong270 Feast (NOI19_feast) C++17
63 / 100
 1000 ms 34152 KB 
/*==============================================================================================================
         __                    __                                             _____     ______    _______
        |  |                  |  |                                           /  __ \   / _____|  / ______|     
      __|  |__              __|  |__                                         |_|  | |  | |       | |  
     |__|   __|            |__|   __|                                             | |  | |____   | |_____ 
        |  |    _____   _     |  |    ____  __  __  ____    _____    _____       / /   \ ___  \  |  ___  \
        |  |   /  _  \ | |    |  |   /  _/ | | | | /  _  \ /  __ \  /  _  \     / /         | |  | |   | |
        |  |_  | |_| | | |    |  |_  | |   | |_| | | |_| | | |  | | | |_| |    / /___   ____| |  | |___| |
        \____\ \____/| |_|    \____\ |_|   \_____/ \_____/ |_|  |_| \____ |   |______| |______/  \_______/
                                                                        | |
                                                                      __/ |
                                                                     |___/  
                                        Pratice, practice, and practice
                                       Where is the bug, delete it there
                                     Try, try, try again until you succeed
I hated every minute of training, but I said, 'Don't quit. Suffer now and live the rest of your life as a champion.' - Mohamed Ali 
                              You may not be the best, but must be the most effort
     Even the things and people you like, you don't have the courage to take, you are destined to be a failure.
                                           Difficult means more time
                                          Done is better than perfect
                                         Pain + Reflection = Progress 
==============================================================================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define endl '\n'
const ll mod = 1e9+7;

ll n, k, a[300005];
pair<ld, ll> dp[300005][3];  //sum doan, cnt doan
ld l, r, lambda;

bool check(ld m)
{
    dp[0][0]={0, 0};
    dp[0][1]={-1e18, 0};
    for (ll i=1; i<=n; i++)
    {
        dp[i][0]=max(dp[i-1][0], dp[i-1][1]);
        dp[i][1]=max(   make_pair(dp[i-1][1].first+a[i], dp[i-1][1].second),   //them a[i] vao doan truoc do
                        make_pair(dp[i-1][0].first+a[i]-m, dp[i-1][0].second+1));  // bat dau doan moi tai vi tri a[i]
    }
    return max(dp[n][0], dp[n][1]).second>=k;
}

void solve()
{
    cin>>n>>k;
    for (ll i=1; i<=n; i++) cin>>a[i];
    l=0, r=1e18;
    ld eps=1e-6;
    while (r-l>eps)
    {
        ld mid=(l+r)/2;
        if (check(mid)==true) l=mid;
        else r=mid;
    }
    lambda=l;
    check(lambda);
    cout<<llround(max(dp[n][0], dp[n][1]).first+lambda*k);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    clock_t start = clock();
    //#ifndef ONLINE_JUDGE
    //freopen("_input.txt", "r", stdin);
    //freopen("_output.txt", "w", stdout);
    //#endif
    solve();
    clock_t end = clock();
    cerr<<"Time: "<<fixed<<setprecision(10)<<double(end-start)/double(CLOCKS_PER_SEC)<<"\n";
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 30900 KB Output is correct
2 Correct 256 ms 33792 KB Output is correct
3 Correct 260 ms 33852 KB Output is correct
4 Correct 255 ms 33816 KB Output is correct
5 Correct 255 ms 33620 KB Output is correct
6 Correct 262 ms 33708 KB Output is correct
7 Correct 249 ms 33616 KB Output is correct
8 Correct 260 ms 33808 KB Output is correct
9 Correct 253 ms 33716 KB Output is correct
10 Correct 259 ms 33764 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 30908 KB Output is correct
2 Correct 253 ms 32080 KB Output is correct
3 Correct 263 ms 32024 KB Output is correct
4 Correct 252 ms 32080 KB Output is correct
5 Execution timed out 1024 ms 33616 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 306 ms 30808 KB Output is correct
2 Correct 307 ms 33904 KB Output is correct
3 Correct 311 ms 33956 KB Output is correct
4 Correct 302 ms 33872 KB Output is correct
5 Correct 308 ms 34128 KB Output is correct
6 Correct 309 ms 33988 KB Output is correct
7 Correct 316 ms 34004 KB Output is correct
8 Correct 305 ms 33872 KB Output is correct
9 Correct 312 ms 34152 KB Output is correct
10 Correct 310 ms 33872 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2592 KB Output is correct
2 Correct 1 ms 2516 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct

Subtask #5
11.0 / 11.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2592 KB Output is correct
2 Correct 1 ms 2516 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct
13 Correct 2 ms 2392 KB Output is correct
14 Correct 1 ms 2392 KB Output is correct
15 Correct 1 ms 2392 KB Output is correct
16 Correct 1 ms 2396 KB Output is correct
17 Correct 1 ms 2392 KB Output is correct
18 Correct 1 ms 2392 KB Output is correct
19 Correct 1 ms 2392 KB Output is correct
20 Correct 1 ms 2396 KB Output is correct
21 Correct 2 ms 2648 KB Output is correct
22 Correct 2 ms 2648 KB Output is correct
23 Correct 3 ms 4696 KB Output is correct
24 Correct 2 ms 2652 KB Output is correct
25 Correct 3 ms 4896 KB Output is correct
26 Correct 3 ms 4696 KB Output is correct
27 Correct 3 ms 4696 KB Output is correct
28 Correct 3 ms 4696 KB Output is correct
29 Correct 3 ms 4696 KB Output is correct
30 Correct 2 ms 2648 KB Output is correct

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 30900 KB Output is correct
2 Correct 256 ms 33792 KB Output is correct
3 Correct 260 ms 33852 KB Output is correct
4 Correct 255 ms 33816 KB Output is correct
5 Correct 255 ms 33620 KB Output is correct
6 Correct 262 ms 33708 KB Output is correct
7 Correct 249 ms 33616 KB Output is correct
8 Correct 260 ms 33808 KB Output is correct
9 Correct 253 ms 33716 KB Output is correct
10 Correct 259 ms 33764 KB Output is correct
11 Correct 255 ms 30908 KB Output is correct
12 Correct 253 ms 32080 KB Output is correct
13 Correct 263 ms 32024 KB Output is correct
14 Correct 252 ms 32080 KB Output is correct
15 Execution timed out 1024 ms 33616 KB Time limit exceeded
16 Halted 0 ms 0 KB -