oj.uz

Submission #996634

# Submission time Handle Problem Language Result Execution time Memory
996634 2024-06-11T01:36:48 Z cpptowin Feast (NOI19_feast) C++17
18 / 100
 219 ms 23624 KB 
#include<bits/stdc++.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout<<"\n";
#define int long long
#define inf (int)1e18
#define pii pair<int,int>
#define vii vector<pii>
#define lb(x) x&-x
#define bit(i,j) ((i>>j)&1LL)
#define offbit(i,j) (i^(1LL<<j))
#define onbit(i,j) (i|(1LL<<j))
#define vi vector<int>
#define mp make_pair
template <typename T1, typename T2> bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
int n,k;
int a[maxn];
vi v;
int arr[maxn];
main()
{
#define name "TASK"
    if(fopen(name".inp","r"))
    {
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> k;
    fo(i,1,n) cin >> a[i];
    a[0] = a[n + 1] = -inf;
    int pos = 0;
    set<pii> s;
    set<int> save;
    fo(i,0,n + 1)
    {
        int now = i;
        int sum = a[i];
        while(now + 1 <= n and a[i] * a[now + 1] >= 0) sum += a[++now];
        if(sum >= 0) v.pb(sum);
        arr[++pos] = sum;
        s.insert({abs(sum),pos});
        save.insert(pos);
        i = now;
    }
    fod(i,v.size(),k + 1)
    {
        int id = s.begin() -> se;
        auto lb = save.lower_bound(id);
        auto pre = prev(lb),nxt = next(lb);
        s.erase({abs(arr[*pre]),*pre});
        s.erase({abs(arr[*nxt]),*nxt});
        s.erase({abs(arr[id]),id});
        arr[id] += arr[*pre];
        arr[id] += arr[*nxt];
        save.erase(*pre);
        save.erase(*nxt);
        s.insert({abs(arr[id]),id});
    }
    int ans = 0;
    for(int it : save) if(arr[it] >= 0) ans += arr[it];
    cout << ans;
}

Compilation message

feast.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main()
      | ^~~~
feast.cpp: In function 'int main()':
feast.cpp:48:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
feast.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4444 KB Output is correct
2 Correct 20 ms 4444 KB Output is correct
3 Incorrect 20 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 4440 KB Output is correct
2 Incorrect 12 ms 4568 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 23496 KB Output is correct
2 Correct 201 ms 23240 KB Output is correct
3 Correct 211 ms 23492 KB Output is correct
4 Correct 204 ms 23236 KB Output is correct
5 Correct 211 ms 23420 KB Output is correct
6 Correct 207 ms 23368 KB Output is correct
7 Correct 205 ms 23492 KB Output is correct
8 Correct 219 ms 23236 KB Output is correct
9 Correct 204 ms 23624 KB Output is correct
10 Correct 209 ms 23496 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 1 ms 2392 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4444 KB Output is correct
2 Correct 20 ms 4444 KB Output is correct
3 Incorrect 20 ms 4444 KB Output isn't correct
4 Halted 0 ms 0 KB -