답안 #1113189

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1113189	2024-11-16T03:15:49 Z	kzhi	Feast (NOI19_feast)	C++14	71 / 100	71 ms	63808 KB

feast

/*
    Author : kmv a.k.a kzhi
    K41 IT CHV
*/
#include <bits/stdc++.h>
using namespace std;


//#define int long long
#define ll long long
#define FOR(i,a,b) for (int i = a ; i <= b; ++ i)
#define FOD(i,a,b) for (int i = a; i >= b; -- i)


#define BIT(mask,i)       ((mask >> i) & 1)
#define MASK(i)                (1ll << (i))
#define OFFBIT(mask,i)  (mask &~(1ll<<(i)))
#define ONBIT(mask,i) (mask | (1ll << (i)))
#define lg2(x)    (63 - __builtin_clzll(x))
#define c_bit          __builtin_popcountll

#define vi vector < int >
#define all(a) a.begin(), a.end()
#define pb push_back

#define ii pair<int,int>
#define fi first
#define se second

#define openfile(TASK) if (fopen(TASK".inp","r"))\
        {freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
#define endl '\n'
#define Faster ios_base::sync_with_stdio(false); \
                        cin.tie(0);  cout.tie(0);

#define mid(l,r) ((l + r) >> 1)
#define left(id) (id << 1)
#define right(id) ((id << 1) | 1)
#define ci const int

template <class X, class Y> bool maximize(X &a, const Y &b){if(a < b) return a = b, true;return false;}
template <class X, class Y> bool minimize(X &a, const Y &b){if(a > b) return a = b, true;return false;}

const int N = 3e5 + 5;
const ll oo = 1e17 + 7;
const int LOG = lg2(N);

int n, k;
int a[N];
ll t[N];

ll sum(int l, int r){
    if (l > r)
        return 0;
    return t[r] - t[l - 1];
}

bool ok1 = 1;
int cnt2 = 0, pos2 = -1;

namespace SUB1{
    ll pt[N];

    void SOLVE(){
        pt[0] = oo;
        ll res = - oo;

        FOR (i, 1, n){
            pt[i] = min(t[i], pt[i - 1]);
            maximize(res, t[i] - pt[i - 1]);
            maximize(res, t[i]);
        }

        maximize(res, 0ll);
        cout << res;
    }
}

namespace SUB6{
    static const int maxN = 2e3 + 5;

    ll dp[maxN][maxN][2];

    ll sol(int i, int cnt, bool ok){
        if (i == n + 1 || cnt == k + 1)
            return 0;
        if (dp[i][cnt][ok] != - oo)
            return dp[i][cnt][ok];
        ll cur = - oo;

        if (!ok){
            maximize(cur, sol(i + 1, cnt, 1) + a[i]);

            maximize(cur, sol(i + 1, cnt, 0));
        }
        else{
            maximize(cur, sol(i + 1, cnt, 1) + a[i]);

            maximize(cur, sol(i + 1, cnt + 1, 0) + max(a[i], 0));
        }

        return dp[i][cnt][ok] = cur;
    }

    void SOLVE(){
        FOR (i, 0, maxN - 1)
            FOR (j, 0, maxN - 1)
                FOR (ok, 0, 1)
                    dp[i][j][ok] = - oo;


        cout << sol(1, 1, 0);
    }
}

namespace FULL {
    vector < ll > v;

    ll s[N];
    int par[N];

    void build(){
        FOR (i, 1, n){
            par[i] = -1;
            s[i] = a[i];
        }
    }

    int F(int x){
        if (par[x] < 0)
            return x;
        return par[x] = F(par[x]);
    }

    void Merge(int u, int v){
        u = F(u);
        v = F(v);
        if (u == v)
            return;

        if (par[u] > par[v])
            swap(u, v);

        par[u] += par[v];
        par[v] = u;
        s[u] += s[v];
    }

    void SOLVE(){
        build();

        FOR (i, 1, n - 1)
            if (a[i] >= 0 && a[i + 1] >= 0)
                Merge(i, i + 1);

        FOR (i, 1, n)
            if (F(i) == i && a[i] >= 0)
                v.pb(s[i]);

        sort(all(v));

        if (k >= v.size()){
            ll res = 0;

            for (ll i : v)
                res += i;

            cout << res;
        }
        else{
            ll res = 0;
            int sz = v.size();

            FOR (i, 1, k)
                res += v[sz - i];

            cout << res;
        }
    }
}

void SOLVE(){
    cin >> n >> k;

    FOR (i, 1, n){
        cin >> a[i];
        t[i] = t[i - 1] + a[i];
        if (a[i] < 0){
            ok1 = 0;
            cnt2 ++;
            pos2 = i;
        }
    }

    if (ok1){
        cout << t[n];
        return;
    }

    if (cnt2 == 1){
        if (k >= 2)
            cout << t[n] - a[pos2];
        else
            cout << max({t[n], sum(1, pos2 - 1), sum(pos2 + 1, n)});
        return;
    }

    if (k == 1){
        SUB1 :: SOLVE();
        return;
    }

    if (n <= 2000 && k <= 2000){
        SUB6 :: SOLVE();
        return;
    }

    FULL :: SOLVE();
}

signed main(){
    Faster
    openfile("feast")

    int q = 1;

//    cin >> q;

    while (q --){
        SOLVE();
    }

    return 0;
}

Compilation message

feast.cpp: In function 'void FULL::SOLVE()':
feast.cpp:162:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |         if (k >= v.size()){
      |             ~~^~~~~~~~~~~
feast.cpp: In function 'int main()':
feast.cpp:31:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         {freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
      |          ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
feast.cpp:223:5: note: in expansion of macro 'openfile'
  223 |     openfile("feast")
      |     ^~~~~~~~
feast.cpp:31:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         {freopen(TASK".inp","r",stdin);freopen(TASK".out","w",stdout);}
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:223:5: note: in expansion of macro 'openfile'
  223 |     openfile("feast")
      |     ^~~~~~~~

Subtask #1

4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	3664 KB	Output is correct
2	Correct	22 ms	3912 KB	Output is correct
3	Correct	23 ms	3920 KB	Output is correct
4	Correct	24 ms	3920 KB	Output is correct
5	Correct	23 ms	3920 KB	Output is correct
6	Correct	26 ms	5328 KB	Output is correct
7	Correct	23 ms	3888 KB	Output is correct
8	Correct	23 ms	3932 KB	Output is correct
9	Correct	23 ms	3664 KB	Output is correct
10	Correct	26 ms	6124 KB	Output is correct

Subtask #2

8.0 / 8.0

#	결과	실행 시간	메모리	Grader output
1	Correct	19 ms	3920 KB	Output is correct
2	Correct	15 ms	3932 KB	Output is correct
3	Correct	18 ms	3920 KB	Output is correct
4	Correct	16 ms	4944 KB	Output is correct
5	Correct	26 ms	6480 KB	Output is correct
6	Correct	17 ms	4944 KB	Output is correct
7	Correct	16 ms	4944 KB	Output is correct
8	Correct	26 ms	6716 KB	Output is correct
9	Correct	24 ms	6544 KB	Output is correct
10	Correct	23 ms	4944 KB	Output is correct

Subtask #3

18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	27 ms	6224 KB	Output is correct
2	Correct	32 ms	7496 KB	Output is correct
3	Correct	32 ms	6232 KB	Output is correct
4	Correct	30 ms	6072 KB	Output is correct
5	Correct	30 ms	6072 KB	Output is correct
6	Correct	31 ms	6216 KB	Output is correct
7	Correct	29 ms	6224 KB	Output is correct
8	Correct	31 ms	8716 KB	Output is correct
9	Correct	38 ms	6236 KB	Output is correct
10	Correct	37 ms	6320 KB	Output is correct

Subtask #4

10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	39 ms	63408 KB	Output is correct
3	Correct	36 ms	63304 KB	Output is correct
4	Correct	40 ms	63260 KB	Output is correct
5	Correct	39 ms	63320 KB	Output is correct
6	Correct	39 ms	63312 KB	Output is correct
7	Correct	42 ms	63304 KB	Output is correct
8	Correct	46 ms	63304 KB	Output is correct
9	Correct	1 ms	500 KB	Output is correct
10	Correct	42 ms	63352 KB	Output is correct

Subtask #5

11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	39 ms	63408 KB	Output is correct
3	Correct	36 ms	63304 KB	Output is correct
4	Correct	40 ms	63260 KB	Output is correct
5	Correct	39 ms	63320 KB	Output is correct
6	Correct	39 ms	63312 KB	Output is correct
7	Correct	42 ms	63304 KB	Output is correct
8	Correct	46 ms	63304 KB	Output is correct
9	Correct	1 ms	500 KB	Output is correct
10	Correct	42 ms	63352 KB	Output is correct
11	Correct	41 ms	63328 KB	Output is correct
12	Correct	50 ms	63304 KB	Output is correct
13	Correct	44 ms	63304 KB	Output is correct
14	Correct	52 ms	63336 KB	Output is correct
15	Correct	45 ms	63304 KB	Output is correct
16	Correct	47 ms	63300 KB	Output is correct
17	Correct	47 ms	63200 KB	Output is correct
18	Correct	44 ms	63304 KB	Output is correct
19	Correct	44 ms	63300 KB	Output is correct
20	Correct	45 ms	63304 KB	Output is correct

Subtask #6

20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	39 ms	63408 KB	Output is correct
3	Correct	36 ms	63304 KB	Output is correct
4	Correct	40 ms	63260 KB	Output is correct
5	Correct	39 ms	63320 KB	Output is correct
6	Correct	39 ms	63312 KB	Output is correct
7	Correct	42 ms	63304 KB	Output is correct
8	Correct	46 ms	63304 KB	Output is correct
9	Correct	1 ms	500 KB	Output is correct
10	Correct	42 ms	63352 KB	Output is correct
11	Correct	41 ms	63328 KB	Output is correct
12	Correct	50 ms	63304 KB	Output is correct
13	Correct	44 ms	63304 KB	Output is correct
14	Correct	52 ms	63336 KB	Output is correct
15	Correct	45 ms	63304 KB	Output is correct
16	Correct	47 ms	63300 KB	Output is correct
17	Correct	47 ms	63200 KB	Output is correct
18	Correct	44 ms	63304 KB	Output is correct
19	Correct	44 ms	63300 KB	Output is correct
20	Correct	45 ms	63304 KB	Output is correct
21	Correct	61 ms	63508 KB	Output is correct
22	Correct	71 ms	63364 KB	Output is correct
23	Correct	62 ms	63808 KB	Output is correct
24	Correct	48 ms	63568 KB	Output is correct
25	Correct	51 ms	63560 KB	Output is correct
26	Correct	51 ms	63516 KB	Output is correct
27	Correct	50 ms	63560 KB	Output is correct
28	Correct	42 ms	63560 KB	Output is correct
29	Correct	41 ms	63424 KB	Output is correct
30	Correct	40 ms	63352 KB	Output is correct

Subtask #7

0 / 29.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	3664 KB	Output is correct
2	Correct	22 ms	3912 KB	Output is correct
3	Correct	23 ms	3920 KB	Output is correct
4	Correct	24 ms	3920 KB	Output is correct
5	Correct	23 ms	3920 KB	Output is correct
6	Correct	26 ms	5328 KB	Output is correct
7	Correct	23 ms	3888 KB	Output is correct
8	Correct	23 ms	3932 KB	Output is correct
9	Correct	23 ms	3664 KB	Output is correct
10	Correct	26 ms	6124 KB	Output is correct
11	Correct	19 ms	3920 KB	Output is correct
12	Correct	15 ms	3932 KB	Output is correct
13	Correct	18 ms	3920 KB	Output is correct
14	Correct	16 ms	4944 KB	Output is correct
15	Correct	26 ms	6480 KB	Output is correct
16	Correct	17 ms	4944 KB	Output is correct
17	Correct	16 ms	4944 KB	Output is correct
18	Correct	26 ms	6716 KB	Output is correct
19	Correct	24 ms	6544 KB	Output is correct
20	Correct	23 ms	4944 KB	Output is correct
21	Correct	27 ms	6224 KB	Output is correct
22	Correct	32 ms	7496 KB	Output is correct
23	Correct	32 ms	6232 KB	Output is correct
24	Correct	30 ms	6072 KB	Output is correct
25	Correct	30 ms	6072 KB	Output is correct
26	Correct	31 ms	6216 KB	Output is correct
27	Correct	29 ms	6224 KB	Output is correct
28	Correct	31 ms	8716 KB	Output is correct
29	Correct	38 ms	6236 KB	Output is correct
30	Correct	37 ms	6320 KB	Output is correct
31	Correct	1 ms	336 KB	Output is correct
32	Correct	39 ms	63408 KB	Output is correct
33	Correct	36 ms	63304 KB	Output is correct
34	Correct	40 ms	63260 KB	Output is correct
35	Correct	39 ms	63320 KB	Output is correct
36	Correct	39 ms	63312 KB	Output is correct
37	Correct	42 ms	63304 KB	Output is correct
38	Correct	46 ms	63304 KB	Output is correct
39	Correct	1 ms	500 KB	Output is correct
40	Correct	42 ms	63352 KB	Output is correct
41	Correct	41 ms	63328 KB	Output is correct
42	Correct	50 ms	63304 KB	Output is correct
43	Correct	44 ms	63304 KB	Output is correct
44	Correct	52 ms	63336 KB	Output is correct
45	Correct	45 ms	63304 KB	Output is correct
46	Correct	47 ms	63300 KB	Output is correct
47	Correct	47 ms	63200 KB	Output is correct
48	Correct	44 ms	63304 KB	Output is correct
49	Correct	44 ms	63300 KB	Output is correct
50	Correct	45 ms	63304 KB	Output is correct
51	Correct	61 ms	63508 KB	Output is correct
52	Correct	71 ms	63364 KB	Output is correct
53	Correct	62 ms	63808 KB	Output is correct
54	Correct	48 ms	63568 KB	Output is correct
55	Correct	51 ms	63560 KB	Output is correct
56	Correct	51 ms	63516 KB	Output is correct
57	Correct	50 ms	63560 KB	Output is correct
58	Correct	42 ms	63560 KB	Output is correct
59	Correct	41 ms	63424 KB	Output is correct
60	Correct	40 ms	63352 KB	Output is correct
61	Incorrect	36 ms	11468 KB	Output isn't correct
62	Halted	0 ms	0 KB	-