oj.uz

Submission #889149

# Submission time Handle Problem Language Result Execution time Memory
889149 2023-12-19T03:40:38 Z dimashhh Feast (NOI19_feast) C++17
12 / 100
 130 ms 40816 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 1, MOD = 998244353;
typedef long long ll;
#define int long long
int n, k, a[N],p[N];
bool ok[N];
vector<ll> b, sum(N);
int get(int v){
    if(p[v] == v) return v;
    return p[v] = get(p[v]);
}
void merge(int v,int u){
    v = get(v);
    u = get(u);
    if(v == u) return;
    p[v] = u;
    sum[u] += sum[v];
}
set<pair<ll,ll>> st;
ll res = 0,col = 0;
void del(int i){
    if(i >= 0 && i < n){
        i = get(i);
        st.erase({abs(sum[i]),i});
        if(sum[i] >= 0){
            res -= sum[i];
            col--;
        }
    }
}
void test()
{
    cin >> n >> k;
    ll lst = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        ok[i] = (a[i] >= 0);
    }
    ll cur = 0;
    ok[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        if (ok[i] == ok[i - 1])
        {
            cur += a[i];
        }
        else
        {
            if(b.empty() && cur < 0){
            }
            else b.push_back(cur);
            cur = a[i];
        }
    }
    if(cur >= 0) b.push_back(cur);
    n = (int)b.size();
    for(int i = 0;i < n;i++){
        p[i] = i;
        sum[i] = b[i];
        if(b[i] >= 0){
            col++;
            res += b[i];
        }
        st.insert({abs(b[i]),i});
    }
    int it = 0;
    while(col > k){
        auto[x,y] = (*st.begin());
        st.erase({x,y});
        // cout << res << ' ' << x << ' ' << y << '\n';
        it++;
        del(y);
        del(y - 1);
        del(y + 1);
        ll nv = sum[y] + (y + 1 < n ? sum[get(y + 1)] : 0) + (y ? sum[get(y - 1)] : 0);
        if(y + 1 < n) merge(y,y + 1);
        if(y) merge(y,y - 1);
        if(nv >= 0){
            col++;
            res += nv;
        }
        // cout << res << '\n';
    }
    cout << res << '\n';
}
main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1; // cin >> T;
    while (T--)
        test();
}

Compilation message

feast.cpp: In function 'void test()':
feast.cpp:35:8: warning: unused variable 'lst' [-Wunused-variable]
   35 |     ll lst = 0;
      |        ^~~
feast.cpp: At global scope:
feast.cpp:88:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   88 | main()
      | ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 10580 KB Output is correct
2 Correct 26 ms 10576 KB Output is correct
3 Correct 26 ms 10836 KB Output is correct
4 Correct 25 ms 10580 KB Output is correct
5 Correct 26 ms 10844 KB Output is correct
6 Correct 26 ms 10392 KB Output is correct
7 Correct 26 ms 10392 KB Output is correct
8 Correct 27 ms 10592 KB Output is correct
9 Correct 27 ms 10328 KB Output is correct
10 Correct 25 ms 10704 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 9560 KB Output is correct
2 Correct 18 ms 9812 KB Output is correct
3 Correct 19 ms 9564 KB Output is correct
4 Correct 18 ms 9560 KB Output is correct
5 Correct 25 ms 10320 KB Output is correct
6 Correct 17 ms 9564 KB Output is correct
7 Correct 18 ms 9820 KB Output is correct
8 Correct 29 ms 10632 KB Output is correct
9 Correct 25 ms 10460 KB Output is correct
10 Correct 20 ms 9824 KB Output is correct

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 130 ms 40816 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 8 ms 16732 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 8 ms 16732 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 8 ms 16732 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 29 ms 10580 KB Output is correct
2 Correct 26 ms 10576 KB Output is correct
3 Correct 26 ms 10836 KB Output is correct
4 Correct 25 ms 10580 KB Output is correct
5 Correct 26 ms 10844 KB Output is correct
6 Correct 26 ms 10392 KB Output is correct
7 Correct 26 ms 10392 KB Output is correct
8 Correct 27 ms 10592 KB Output is correct
9 Correct 27 ms 10328 KB Output is correct
10 Correct 25 ms 10704 KB Output is correct
11 Correct 18 ms 9560 KB Output is correct
12 Correct 18 ms 9812 KB Output is correct
13 Correct 19 ms 9564 KB Output is correct
14 Correct 18 ms 9560 KB Output is correct
15 Correct 25 ms 10320 KB Output is correct
16 Correct 17 ms 9564 KB Output is correct
17 Correct 18 ms 9820 KB Output is correct
18 Correct 29 ms 10632 KB Output is correct
19 Correct 25 ms 10460 KB Output is correct
20 Correct 20 ms 9824 KB Output is correct
21 Runtime error 130 ms 40816 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -