# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
485986 |
2021-11-10T03:45:45 Z |
Killer2501 |
Feast (NOI19_feast) |
C++14 |
|
196 ms |
165236 KB |
#include<bits/stdc++.h>
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back
#define task "hopscotch"
#define pii pair<ll, pll>
using namespace std;
using ll = long long;
const int N = 3e5+5;
const ll mod = 1e9+7;
const ll base = 350;
const ll inf = 1e15;
ll m, n, t, k, a[N], ans, tong, b[N], d[N], h[N];
vector<pii> kq;
bool ok[N];
string s;
ll pw(ll k, ll n)
{
ll total = 1;
for(; n; n >>= 1)
{
if(n&1)total = total * k % mod;
k = k * k % mod;
}
return total;
}
struct node
{
ll mx, sum, l, r, pre, suf, nl, nr;
node(ll _mx = -inf, ll _sum = -inf, ll _l = 0, ll _r = 0, ll _pre = -inf, ll _suf = -inf, ll _nl = 0, ll _nr = 0)
{
mx = _mx;
sum = _sum;
l = _l;
r = _r;
pre = _pre;
suf = _suf;
nl = _nl;
nr = _nr;
}
};
node merga(node x, node y)
{
node res;
res.sum = x.sum + y.sum;
if(x.mx > y.mx)
{
res.mx = x.mx;
res.l = x.l;
res.r = x.r;
}
else
{
res.mx = y.mx;
res.l = y.l;
res.r = y.r;
}
if(res.mx < x.suf+y.pre)
{
res.mx = x.suf+y.pre;
res.l = x.nr;
res.r = y.nl;
}
res.pre = x.pre;
res.nl = x.nl;
if(res.pre < x.sum + y.pre)
{
res.pre = x.sum + y.pre;
res.nl = y.nl;
}
res.suf = y.suf;
res.nr = y.nr;
if(res.suf < x.suf + y.sum)
{
res.suf = x.suf + y.sum;
res.nr = x.nr;
}
return res;
}
struct IT
{
ll n;
vector<node> st, rv;
vector<ll> lazy;
IT(ll _n)
{
n = _n;
st.resize(n*4+4);
rv.resize(n*4+4);
lazy.resize(n*4+4, 0);
}
void build(ll id, ll l, ll r)
{
if(l == r)
{
st[id] = node(a[l], a[l], l, l, a[l], a[l], l, l);
rv[id] = node(-a[l], -a[l], l, l, -a[l], -a[l], l, l);
return;
}
ll mid = (l+r)/2;
build(id*2, l, mid);
build(id*2+1, mid+1, r);
st[id] = merga(st[id*2], st[id*2+1]);
rv[id] = merga(rv[id*2], rv[id*2+1]);
}
void build()
{
build(1, 1, n);
}
void down(ll id)
{
if(!lazy[id])return;
swap(st[id*2], rv[id*2]);
swap(st[id*2+1], rv[id*2+1]);
lazy[id*2] ^= 1;
lazy[id*2+1] ^= 1;
lazy[id] = 0;
}
void update(ll id, ll l, ll r, ll u, ll v)
{
if(u <= l && r <= v)
{
swap(st[id], rv[id]);
lazy[id] ^= 1;
return;
}
if(u > r || l > v)return;
ll mid = (l+r)/2;
down(id);
update(id*2, l, mid, u, v);
update(id*2+1, mid+1, r, u, v);
st[id] = merga(st[id*2], st[id*2+1]);
rv[id] = merga(rv[id*2], rv[id*2+1]);
}
void update(ll l, ll r)
{
update(1, 1, n, l, r);
}
};
void sol()
{
cin >> n >> k;
for(int i = 1; i <= n; i ++)cin >> a[i];
IT it(n);
it.build();
while(k -- > 0)
{
if(it.st[1].mx <= 0)break;
ans += it.st[1].mx;
it.update(it.st[1].l, it.st[1].r);
}
cout << ans;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen(task".in", "r"))
{
freopen(task".in", "r", stdin);
freopen(task".out", "w", stdout);
}
int ntest = 1;
//cin >> ntest;
while(ntest -- > 0)
sol();
}
/*
5 4
1 2 1
2 3 4
1 4 3
4 3 2
3
1 3 1
1 3 2
1 3 3
*/
Compilation message
feast.cpp: In function 'int main()':
feast.cpp:164:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
164 | freopen(task".in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
feast.cpp:165:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
165 | freopen(task".out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
103 ms |
157892 KB |
Output is correct |
2 |
Correct |
102 ms |
163112 KB |
Output is correct |
3 |
Correct |
115 ms |
164992 KB |
Output is correct |
4 |
Correct |
115 ms |
163852 KB |
Output is correct |
5 |
Correct |
99 ms |
163000 KB |
Output is correct |
6 |
Correct |
111 ms |
160236 KB |
Output is correct |
7 |
Correct |
103 ms |
160064 KB |
Output is correct |
8 |
Correct |
101 ms |
163372 KB |
Output is correct |
9 |
Correct |
108 ms |
160688 KB |
Output is correct |
10 |
Correct |
119 ms |
162256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
89 ms |
158540 KB |
Output is correct |
2 |
Correct |
92 ms |
163116 KB |
Output is correct |
3 |
Correct |
89 ms |
159172 KB |
Output is correct |
4 |
Correct |
94 ms |
160636 KB |
Output is correct |
5 |
Correct |
100 ms |
160280 KB |
Output is correct |
6 |
Correct |
93 ms |
159044 KB |
Output is correct |
7 |
Correct |
93 ms |
163424 KB |
Output is correct |
8 |
Correct |
109 ms |
164064 KB |
Output is correct |
9 |
Correct |
96 ms |
159812 KB |
Output is correct |
10 |
Correct |
91 ms |
162308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
100 ms |
161244 KB |
Output is correct |
2 |
Correct |
110 ms |
161348 KB |
Output is correct |
3 |
Correct |
134 ms |
162960 KB |
Output is correct |
4 |
Correct |
103 ms |
161380 KB |
Output is correct |
5 |
Correct |
101 ms |
162912 KB |
Output is correct |
6 |
Correct |
103 ms |
163908 KB |
Output is correct |
7 |
Correct |
107 ms |
164620 KB |
Output is correct |
8 |
Correct |
115 ms |
163012 KB |
Output is correct |
9 |
Correct |
120 ms |
165060 KB |
Output is correct |
10 |
Correct |
103 ms |
164548 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
12 |
Correct |
1 ms |
460 KB |
Output is correct |
13 |
Correct |
1 ms |
460 KB |
Output is correct |
14 |
Correct |
1 ms |
460 KB |
Output is correct |
15 |
Correct |
1 ms |
460 KB |
Output is correct |
16 |
Correct |
1 ms |
460 KB |
Output is correct |
17 |
Correct |
1 ms |
460 KB |
Output is correct |
18 |
Correct |
1 ms |
460 KB |
Output is correct |
19 |
Correct |
0 ms |
460 KB |
Output is correct |
20 |
Correct |
1 ms |
460 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
0 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
460 KB |
Output is correct |
12 |
Correct |
1 ms |
460 KB |
Output is correct |
13 |
Correct |
1 ms |
460 KB |
Output is correct |
14 |
Correct |
1 ms |
460 KB |
Output is correct |
15 |
Correct |
1 ms |
460 KB |
Output is correct |
16 |
Correct |
1 ms |
460 KB |
Output is correct |
17 |
Correct |
1 ms |
460 KB |
Output is correct |
18 |
Correct |
1 ms |
460 KB |
Output is correct |
19 |
Correct |
0 ms |
460 KB |
Output is correct |
20 |
Correct |
1 ms |
460 KB |
Output is correct |
21 |
Correct |
1 ms |
1356 KB |
Output is correct |
22 |
Correct |
2 ms |
1304 KB |
Output is correct |
23 |
Correct |
1 ms |
1356 KB |
Output is correct |
24 |
Correct |
1 ms |
1356 KB |
Output is correct |
25 |
Correct |
1 ms |
1356 KB |
Output is correct |
26 |
Correct |
1 ms |
1356 KB |
Output is correct |
27 |
Correct |
1 ms |
1372 KB |
Output is correct |
28 |
Correct |
1 ms |
1356 KB |
Output is correct |
29 |
Correct |
1 ms |
1356 KB |
Output is correct |
30 |
Correct |
1 ms |
1356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
103 ms |
157892 KB |
Output is correct |
2 |
Correct |
102 ms |
163112 KB |
Output is correct |
3 |
Correct |
115 ms |
164992 KB |
Output is correct |
4 |
Correct |
115 ms |
163852 KB |
Output is correct |
5 |
Correct |
99 ms |
163000 KB |
Output is correct |
6 |
Correct |
111 ms |
160236 KB |
Output is correct |
7 |
Correct |
103 ms |
160064 KB |
Output is correct |
8 |
Correct |
101 ms |
163372 KB |
Output is correct |
9 |
Correct |
108 ms |
160688 KB |
Output is correct |
10 |
Correct |
119 ms |
162256 KB |
Output is correct |
11 |
Correct |
89 ms |
158540 KB |
Output is correct |
12 |
Correct |
92 ms |
163116 KB |
Output is correct |
13 |
Correct |
89 ms |
159172 KB |
Output is correct |
14 |
Correct |
94 ms |
160636 KB |
Output is correct |
15 |
Correct |
100 ms |
160280 KB |
Output is correct |
16 |
Correct |
93 ms |
159044 KB |
Output is correct |
17 |
Correct |
93 ms |
163424 KB |
Output is correct |
18 |
Correct |
109 ms |
164064 KB |
Output is correct |
19 |
Correct |
96 ms |
159812 KB |
Output is correct |
20 |
Correct |
91 ms |
162308 KB |
Output is correct |
21 |
Correct |
100 ms |
161244 KB |
Output is correct |
22 |
Correct |
110 ms |
161348 KB |
Output is correct |
23 |
Correct |
134 ms |
162960 KB |
Output is correct |
24 |
Correct |
103 ms |
161380 KB |
Output is correct |
25 |
Correct |
101 ms |
162912 KB |
Output is correct |
26 |
Correct |
103 ms |
163908 KB |
Output is correct |
27 |
Correct |
107 ms |
164620 KB |
Output is correct |
28 |
Correct |
115 ms |
163012 KB |
Output is correct |
29 |
Correct |
120 ms |
165060 KB |
Output is correct |
30 |
Correct |
103 ms |
164548 KB |
Output is correct |
31 |
Correct |
1 ms |
332 KB |
Output is correct |
32 |
Correct |
1 ms |
332 KB |
Output is correct |
33 |
Correct |
0 ms |
332 KB |
Output is correct |
34 |
Correct |
1 ms |
332 KB |
Output is correct |
35 |
Correct |
0 ms |
332 KB |
Output is correct |
36 |
Correct |
0 ms |
332 KB |
Output is correct |
37 |
Correct |
1 ms |
332 KB |
Output is correct |
38 |
Correct |
0 ms |
332 KB |
Output is correct |
39 |
Correct |
0 ms |
332 KB |
Output is correct |
40 |
Correct |
0 ms |
332 KB |
Output is correct |
41 |
Correct |
1 ms |
460 KB |
Output is correct |
42 |
Correct |
1 ms |
460 KB |
Output is correct |
43 |
Correct |
1 ms |
460 KB |
Output is correct |
44 |
Correct |
1 ms |
460 KB |
Output is correct |
45 |
Correct |
1 ms |
460 KB |
Output is correct |
46 |
Correct |
1 ms |
460 KB |
Output is correct |
47 |
Correct |
1 ms |
460 KB |
Output is correct |
48 |
Correct |
1 ms |
460 KB |
Output is correct |
49 |
Correct |
0 ms |
460 KB |
Output is correct |
50 |
Correct |
1 ms |
460 KB |
Output is correct |
51 |
Correct |
1 ms |
1356 KB |
Output is correct |
52 |
Correct |
2 ms |
1304 KB |
Output is correct |
53 |
Correct |
1 ms |
1356 KB |
Output is correct |
54 |
Correct |
1 ms |
1356 KB |
Output is correct |
55 |
Correct |
1 ms |
1356 KB |
Output is correct |
56 |
Correct |
1 ms |
1356 KB |
Output is correct |
57 |
Correct |
1 ms |
1372 KB |
Output is correct |
58 |
Correct |
1 ms |
1356 KB |
Output is correct |
59 |
Correct |
1 ms |
1356 KB |
Output is correct |
60 |
Correct |
1 ms |
1356 KB |
Output is correct |
61 |
Correct |
172 ms |
161188 KB |
Output is correct |
62 |
Correct |
196 ms |
165236 KB |
Output is correct |
63 |
Correct |
112 ms |
160836 KB |
Output is correct |
64 |
Correct |
190 ms |
164060 KB |
Output is correct |
65 |
Correct |
145 ms |
163976 KB |
Output is correct |
66 |
Correct |
156 ms |
163396 KB |
Output is correct |
67 |
Correct |
142 ms |
161084 KB |
Output is correct |
68 |
Correct |
110 ms |
164092 KB |
Output is correct |
69 |
Correct |
112 ms |
160796 KB |
Output is correct |
70 |
Correct |
101 ms |
160104 KB |
Output is correct |