oj.uz

Submission #731502

# Submission time Handle Problem Language Result Execution time Memory
731502 2023-04-27T13:35:53 Z mohav48173 Feast (NOI19_feast) C++14
59 / 100
 223 ms 5048 KB 
#include<bits/stdc++.h>
using namespace std;
int n,k;
long long a[400000];
long long m[400000];
long long mincnt=0;
double score=0;
double get(int ind) {
    if(ind<0)return 0;
    else return m[ind];
}
void calc(double lam) {
    double bestscore=0;
    long long bestcnt=0;
    double bestnxt=-lam;
    long long nxtcnt=0;
    for(int i=0;i<n;i++) {
        if(bestscore-lam-get(i-1)>bestnxt ||
           (bestscore-lam-get(i-1)==bestnxt && nxtcnt>bestcnt)) {
            bestnxt=bestscore-get(i-1)-lam;
            nxtcnt=bestcnt;
        }
        if(bestnxt+get(i)>bestscore || (bestnxt+get(i)==bestscore && nxtcnt+1<bestcnt)) {
            bestscore=bestnxt+get(i);
            bestcnt=nxtcnt+1;
        }
    }
    mincnt=bestcnt;
    score=bestscore;
}
int main() {
    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>a[i];
    m[0]=a[0];for(int i=1;i<n;i++)m[i]=m[i-1]+a[i];
    double l=0,r=1e17;
    while((r-l)>(double)(1e-5)) {
        double mid=(l+r)/2.0;
        calc(mid);
        if(mincnt<k)r=mid;
        else l=mid;
    }
    calc(r);
    cout<<(long long)(round(score+k*r))<<endl;
    return 0;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 4884 KB Output is correct
2 Correct 97 ms 4980 KB Output is correct
3 Correct 100 ms 4984 KB Output is correct
4 Incorrect 101 ms 5032 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 207 ms 4812 KB Output is correct
2 Correct 198 ms 4908 KB Output is correct
3 Correct 213 ms 4820 KB Output is correct
4 Correct 210 ms 4980 KB Output is correct
5 Correct 208 ms 4952 KB Output is correct
6 Correct 210 ms 4948 KB Output is correct
7 Correct 204 ms 4964 KB Output is correct
8 Correct 192 ms 4916 KB Output is correct
9 Correct 209 ms 4980 KB Output is correct
10 Correct 223 ms 5048 KB Output is correct

Subtask #4
10.0 / 10.0

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

Subtask #5
11.0 / 11.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
0 / 29.0

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