oj.uz

Submission #996628

# Submission time Handle Problem Language Result Execution time Memory
996628 2024-06-11T01:18:31 Z cpptowin Feast (NOI19_feast) C++17
0 / 100
 1000 ms 45372 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 ans = 0;
int cnt = 0;
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];
    int pos = 0;
    fo(i,1,n)
    {
        int now = i;
        int sum = a[i];
        while(a[i] * a[now + 1] >= 0) sum += a[++now];
        if(sum >= 0) v.pb(sum),cnt++;
        arr[++pos] = sum;
        s.insert({abs(sum),i});
        save.insert(pos);
    }
    if(v.size() <= k)
    {
        int tot = 0;
        for(int it : v) tot += it;
        return cout << tot,0;
    }
    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[id]),id});
        s.erase({abs(arr[*nxt]),*nxt});
        arr[id] += arr[*pre] + arr[*nxt];
        s.insert({abs(arr[id]),id});
        save.erase(*pre);
        save.erase(*nxt);
    }
    int ans = 0;
    for(int it : save) if(arr[it] >= 0) ans += arr[it];
    cout << ans;
}

Compilation message

feast.cpp:47:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   47 | main()
      | ^~~~
feast.cpp: In function 'int main()':
feast.cpp:70:17: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   70 |     if(v.size() <= k)
      |        ~~~~~~~~~^~~~
feast.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
feast.cpp:53:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1040 ms 7616 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

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

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 454 ms 45372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 20.0

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

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1040 ms 7616 KB Time limit exceeded
2 Halted 0 ms 0 KB -