oj.uz

Submission #1007981

# Submission time Handle Problem Language Result Execution time Memory
1007981 2024-06-26T04:41:34 Z Luvidi Feast (NOI19_feast) C++17
12 / 100
 46 ms 19500 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll, ll>
#define pii pair<int, int>
#define fs first
#define sc second
#define pb push_back

void solve() {
    int n,k;
    cin>>n>>k;
    ll a[n];
    for(int i=0;i<n;i++)cin>>a[i];
    vector<pair<pll,pll>> v;
    ll sum=0,s=a[0]>=0,l=0,cnt=0,ans=0;
    for(int i=0;i<n;i++){
        if(s^(a[i]>=0)){
            v.pb({{abs(sum),s},{l,i-1}});
            if(s){
                cnt++;
                ans+=sum;
            }
            s=!s;
            sum=0;
            l=i;
        }
        sum+=a[i];
    }
    v.pb({{abs(sum),s},{l,n-1}});
    if(s){
        cnt++;
        ans+=sum;
    }
    bool b[n];
    for(int i=0;i<n;i++)b[i]=a[i]>=0;
    
    sort(v.begin(),v.end());
    printf("\n");
    int idx=0;
    while(cnt>k){
        auto[x,y]=v[idx].fs;
        auto[l,r]=v[idx].sc;
        idx++;
        if(y){
            if(l>0&&b[l-1]||r<n-1&&b[r+1])continue;
            for(int i=l;i<=r;i++)b[i]=0;
            ans-=x;
        }else{
            if(!l||!b[l-1]||r==n-1||!b[r+1])continue;
            for(int i=l;i<=r;i++)b[i]=1;
            ans-=x;
        }
        cnt--;        
    }
    cout<<ans;
}

int main() {   
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    solve();
}

Compilation message

feast.cpp: In function 'void solve()':
feast.cpp:47:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   47 |             if(l>0&&b[l-1]||r<n-1&&b[r+1])continue;
      |                ~~~^~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 5712 KB Output is correct
2 Correct 21 ms 5724 KB Output is correct
3 Correct 21 ms 5716 KB Output is correct
4 Correct 22 ms 5716 KB Output is correct
5 Correct 21 ms 5712 KB Output is correct
6 Correct 20 ms 5768 KB Output is correct
7 Correct 20 ms 5552 KB Output is correct
8 Correct 21 ms 5716 KB Output is correct
9 Correct 21 ms 5784 KB Output is correct
10 Correct 21 ms 5968 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 4128 KB Output is correct
2 Correct 17 ms 4168 KB Output is correct
3 Correct 13 ms 3932 KB Output is correct
4 Correct 13 ms 3932 KB Output is correct
5 Correct 20 ms 5664 KB Output is correct
6 Correct 16 ms 3932 KB Output is correct
7 Correct 14 ms 4188 KB Output is correct
8 Correct 21 ms 5908 KB Output is correct
9 Correct 22 ms 5720 KB Output is correct
10 Correct 14 ms 4188 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 19500 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 5712 KB Output is correct
2 Correct 21 ms 5724 KB Output is correct
3 Correct 21 ms 5716 KB Output is correct
4 Correct 22 ms 5716 KB Output is correct
5 Correct 21 ms 5712 KB Output is correct
6 Correct 20 ms 5768 KB Output is correct
7 Correct 20 ms 5552 KB Output is correct
8 Correct 21 ms 5716 KB Output is correct
9 Correct 21 ms 5784 KB Output is correct
10 Correct 21 ms 5968 KB Output is correct
11 Correct 22 ms 4128 KB Output is correct
12 Correct 17 ms 4168 KB Output is correct
13 Correct 13 ms 3932 KB Output is correct
14 Correct 13 ms 3932 KB Output is correct
15 Correct 20 ms 5664 KB Output is correct
16 Correct 16 ms 3932 KB Output is correct
17 Correct 14 ms 4188 KB Output is correct
18 Correct 21 ms 5908 KB Output is correct
19 Correct 22 ms 5720 KB Output is correct
20 Correct 14 ms 4188 KB Output is correct
21 Runtime error 46 ms 19500 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -