1
#include <bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define endl '\n'
5
const int N = 3e5+5;
6
#define pii pair<int,int>
7
int n, k, a[N], vis[N], ans;
8
int st[N], e[N];
9
priority_queue<int,vector<int>,greater<int> > q;
10
set<int> s;
11
signed main(){
12
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
13
  // freopen("interview.in", "r", stdin);
14
    // freopen("interview.out", "w", stdout);
15
    cin >> n >> k;
16
    for(int i = 1; i <= n; i++) cin >> a[i];
17
  for(int i = 1; i <= k; i++) {
18
        e[i] = a[i];
19
        q.push(e[i]);
20
    }
21
  for(int i = k + 1; i <= n; i++){
22
    int fro = q.top();
23
        q.pop();
24
        st[i] = fro, fro += a[i], e[i] = fro;
25
        q.push(fro);
26
  }
27
    cout << q.top() << endl;
28
    s.insert(q.top());
29
    for(int i = n; i >= 1; i--){
30
        if(s.find(e[i]) != s.end()){
31
            s.insert(st[i]);
32
            if(i <= k) vis[i] = 1;
33
        }
34
    }
35
  for(int i = 1; i <= k; i++) cout << vis[i];
36
    return 0;
37
}

1
#include <bits/stdc++.h>
2
using namespace std;
3
#define int long long
4
#define endl '\n'
5
const int N = 3e5+5;
6
int t, n, m, k;
7
int a[5];
8
int e[N], o[N], w[N];
9
signed main(){
10
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
11
    cin >> t;
12
    while(t--){
13
        cin >> n >> m >> k;
14
        memset(o, 0x3f, sizeof(o)), memset(e, 0x3f, sizeof(e));
15
        for(int i = 1; i <= m; i++){
16
            for(int j = 1; j <= k; j++){
17
                cin >> a[j];
18
                if(a[j] & 1)
19
                    o[i] = min(o[i], a[j]), e[i] = min(e[i], -a[j]);
20
                else
21
                    o[i] = min(o[i], -a[j]), e[i] = min(e[i], a[j]);
22
            }
23
            w[i] = max(e[i], o[i]);
24
        }
25
        w[m + 1] = 0;
26
        for(int i = m; i >= 1; i--)
27
            w[i] = min(w[i] + w[i + 1], 0ll);
28
        if(n + w[1] <= 0){
29
            cout << -1 << endl;
30
            continue;
31
        }
32
        for(int i = 1; i <= m; i++){
33
            n += max(e[i], o[i]);
34
            if(e[i] >= o[i]) cout << "Even "; // L34: n += e[i]
35
            else if(n - o[i] + e[i] + w[i + 1] > 0) //L34: n += o[i] 先亏后赚
36
                cout << "Even ", n = n - o[i] + e[i];
37
            else cout << "Odd ";
38
            assert(n > 0);
39
        }
40
        cout << endl;
41
    }
42
    return 0;
43
}