Submission #996633

#	Time	Username	Problem	Language	Result	Execution time	Memory
996633		cpptowin	Feast (NOI19_feast)	C++17	18 / 100	223 ms	26660 KiB

feast

#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];
set<pii> s;
set<int> save;
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;
    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 (stderr)

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

• Subtask 1: 0 / 4
• Subtask 2: 0 / 8
• Subtask 3: 18 / 18
• Subtask 4: 0 / 10
• Subtask 5: 0 / 11
• Subtask 6: 0 / 20
• Subtask 7: 0 / 29