oj.uz

Submission #492579

# Submission time Handle Problem Language Result Execution time Memory
492579 2021-12-08T02:36:44 Z Deepesson Feast (NOI19_feast) C++17
59 / 100
 73 ms 2720 KB 
#include <bits/stdc++.h>
#define MAX 505000
int N,K;
long long array[MAX];
typedef std::pair<long long,long long> pll;
pll func(long long C){
    long long a=1,b=0;
    long long max=0,maxval=0;
    long long pega=-C,npega=0;
    for(int i=0;i!=N;++i){
        pega+=array[i];
        if(pega>npega){
            npega=pega;
            b=a;
        }
        if(npega-C>=pega){
            pega=npega-C;
            a=b;
            ++a;
        }
        if(pega>max){
            max=pega;
            maxval=a;
        }
    }
    return {max,maxval};
}
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    std::cin>>N>>K;
    for(int i=0;i!=N;++i)std::cin>>array[i];
    long long l=0,r=1LL<<50LL;
    while(l<r){
        long long m = (l+r)/2;
        long long res = func(m).second;
        if(res<=K){
            r=m;
        }else l=m+1;
    }
    auto res = func(l);
    if(!l){
        std::cout<<res.first<<"\n";
        return 0;
    }
    auto res2=func(l-1);
    long long dif = res2.second-res.second;
    long long bonus = std::min(K-res.second,dif)*l;
    if(std::min(K-res.second,dif)+res.second<K){
        assert(0);
    }
    std::cout<<(res.first+(res.second*l)+bonus)<<"\n";
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 2512 KB Output is correct
2 Correct 37 ms 2636 KB Output is correct
3 Correct 36 ms 2588 KB Output is correct
4 Incorrect 35 ms 2508 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 2500 KB Output is correct
2 Correct 71 ms 2552 KB Output is correct
3 Correct 70 ms 2616 KB Output is correct
4 Correct 70 ms 2596 KB Output is correct
5 Correct 69 ms 2616 KB Output is correct
6 Correct 69 ms 2636 KB Output is correct
7 Correct 73 ms 2720 KB Output is correct
8 Correct 72 ms 2576 KB Output is correct
9 Correct 68 ms 2636 KB Output is correct
10 Correct 72 ms 2596 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
11.0 / 11.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
0 / 29.0

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