oj.uz

Submission #889150

# Submission time Handle Problem Language Result Execution time Memory
889150 2023-12-19T03:44:35 Z dimashhh Feast (NOI19_feast) C++17
4 / 100
 114 ms 38920 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);
        if(ok[i]) return;
        ok[i] = 1;
        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});
        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:38:8: warning: unused variable 'lst' [-Wunused-variable]
   38 |     ll lst = 0;
      |        ^~~
feast.cpp: At global scope:
feast.cpp:90:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   90 | main()
      | ^~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 8796 KB Output is correct
2 Correct 25 ms 8916 KB Output is correct
3 Correct 25 ms 9008 KB Output is correct
4 Correct 24 ms 9024 KB Output is correct
5 Correct 25 ms 8884 KB Output is correct
6 Correct 24 ms 8796 KB Output is correct
7 Correct 23 ms 8912 KB Output is correct
8 Correct 23 ms 9048 KB Output is correct
9 Correct 23 ms 8860 KB Output is correct
10 Correct 25 ms 8796 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 114 ms 38920 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 10 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 10 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 10 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 23 ms 8796 KB Output is correct
2 Correct 25 ms 8916 KB Output is correct
3 Correct 25 ms 9008 KB Output is correct
4 Correct 24 ms 9024 KB Output is correct
5 Correct 25 ms 8884 KB Output is correct
6 Correct 24 ms 8796 KB Output is correct
7 Correct 23 ms 8912 KB Output is correct
8 Correct 23 ms 9048 KB Output is correct
9 Correct 23 ms 8860 KB Output is correct
10 Correct 25 ms 8796 KB Output is correct
11 Runtime error 22 ms 17872 KB Execution killed with signal 11
12 Halted 0 ms 0 KB -