oj.uz

답안 #492578

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
492578 2021-12-08T02:31:51 Z Deepesson Feast (NOI19_feast) C++17
59 / 100
 91 ms 5700 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;
    std::cout<<(res.first+(res.second*l)+bonus)<<"\n";
}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 47 ms 5388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 3704 KB Output is correct
2 Correct 45 ms 3780 KB Output is correct
3 Correct 41 ms 3656 KB Output is correct
4 Incorrect 45 ms 3708 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 5628 KB Output is correct
2 Correct 76 ms 5584 KB Output is correct
3 Correct 77 ms 5640 KB Output is correct
4 Correct 78 ms 5580 KB Output is correct
5 Correct 80 ms 5520 KB Output is correct
6 Correct 91 ms 5660 KB Output is correct
7 Correct 86 ms 5572 KB Output is correct
8 Correct 76 ms 5580 KB Output is correct
9 Correct 80 ms 5700 KB Output is correct
10 Correct 88 ms 5680 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct

Subtask #5
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 0 ms 332 KB Output is correct

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 0 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 2 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 460 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 352 KB Output is correct
30 Correct 1 ms 332 KB Output is correct

Subtask #7
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 47 ms 5388 KB Output isn't correct
2 Halted 0 ms 0 KB -