oj.uz

Submission #442074

# Submission time Handle Problem Language Result Execution time Memory
442074 2021-07-07T05:32:42 Z Evirir Feast (NOI19_feast) C++17
30 / 100
 244 ms 19764 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<(x)<<'\n'
#define mset(d,val) memset(d,val,sizeof(d))
#define setp(x) cout<<fixed<<setprecision(x)
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define pqueue priority_queue
#define fbo find_by_order
#define ook order_of_key
typedef long long ll;
typedef pair<ll,ll> ii;
typedef pair<ii,ll> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef long double ld;
template<typename T>
using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void amin(ll &a, ll b){ a=min(a,b); }
void amax(ll &a, ll b){ a=max(a,b); }
void YES(){cout<<"YES\n";} void NO(){cout<<"NO\n";}
void SD(int t=0){ cout<<"PASSED "<<t<<endl; }
const ll INF = ll(1e18);
const int MOD = 998244353;

const bool DEBUG = 0;
const int MAXN = 300005;

int n,K;
ll a[MAXN];
ll p[MAXN];
ll dp[MAXN], cnt[MAXN];
iii pre[MAXN]; //best dp[j-1]+sum(j..i) for j<=i

ll sum(int l, int r){ return p[r]-(l?p[l-1]:0LL); }

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	
	cin>>n>>K;
	fore(i,1,n)
	{
		cin>>a[i];
		p[i]=p[i-1]+a[i];
	}
	dp[0]=cnt[0]=0;
	pre[0]={{0,0},0};
	
	ll ans=0;
	for(ll L=0,R=1e16;L<=R;)
	{
		ll mid=(L+R)>>1;
		
		fore(i,1,n)
		{
			iii tmp=pre[i-1];
			tmp.F.F+=a[i];
			pre[i]=max({{dp[i-1]+a[i],-cnt[i-1]-1}, i}, tmp);
			if(pre[i].F.F-mid>dp[i-1]) // strict; use as few as possible
			{
				dp[i]=pre[i].F.F-mid;
				cnt[i]=cnt[pre[i].S]+1;
			}
			else
			{
				dp[i]=dp[i-1];
				cnt[i]=cnt[i-1];
			}
		}
		if(cnt[n]<=K)
		{
			ans=dp[n]+cnt[n]*mid;
			R=mid-1;
		}
		else L=mid+1;
		
		if(DEBUG && ans>0)
		{
			cout<<"mid="<<mid<<'\n';
			cout<<"a: "; fore(i,1,n) cout<<a[i]<<" "; cout<<'\n';
			cout<<"dp: "; fore(i,1,n) cout<<dp[i]<<" "; cout<<'\n';
			cout<<"cnt: "; fore(i,1,n) cout<<cnt[i]<<" "; cout<<'\n';
			cout<<"pre: "; fore(i,1,n) cout<<"("<<pre[i].F.F<<","<<pre[i].F.S<<") "; cout<<'\n';
			cout<<"ans: "<<dp[n]+cnt[n]*mid<<"\n\n";
		}
	}
	
	cout<<ans<<'\n';
	
	return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 18976 KB Output is correct
2 Correct 233 ms 19384 KB Output is correct
3 Correct 239 ms 19616 KB Output is correct
4 Correct 241 ms 19464 KB Output is correct
5 Correct 240 ms 19268 KB Output is correct
6 Correct 232 ms 19056 KB Output is correct
7 Correct 242 ms 18980 KB Output is correct
8 Correct 239 ms 19452 KB Output is correct
9 Correct 236 ms 19140 KB Output is correct
10 Correct 239 ms 19292 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 17460 KB Output is correct
2 Correct 231 ms 17844 KB Output is correct
3 Correct 217 ms 17424 KB Output is correct
4 Correct 221 ms 17560 KB Output is correct
5 Correct 232 ms 19060 KB Output is correct
6 Correct 218 ms 17420 KB Output is correct
7 Correct 227 ms 17876 KB Output is correct
8 Correct 239 ms 19512 KB Output is correct
9 Correct 242 ms 18900 KB Output is correct
10 Correct 225 ms 17760 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 19524 KB Output is correct
2 Correct 236 ms 19336 KB Output is correct
3 Correct 232 ms 19524 KB Output is correct
4 Correct 237 ms 19268 KB Output is correct
5 Correct 237 ms 19532 KB Output is correct
6 Correct 238 ms 19744 KB Output is correct
7 Correct 241 ms 19652 KB Output is correct
8 Correct 233 ms 19420 KB Output is correct
9 Correct 244 ms 19764 KB Output is correct
10 Correct 240 ms 19724 KB Output is correct

Subtask #4
0 / 10.0

# 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 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 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 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 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 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 234 ms 18976 KB Output is correct
2 Correct 233 ms 19384 KB Output is correct
3 Correct 239 ms 19616 KB Output is correct
4 Correct 241 ms 19464 KB Output is correct
5 Correct 240 ms 19268 KB Output is correct
6 Correct 232 ms 19056 KB Output is correct
7 Correct 242 ms 18980 KB Output is correct
8 Correct 239 ms 19452 KB Output is correct
9 Correct 236 ms 19140 KB Output is correct
10 Correct 239 ms 19292 KB Output is correct
11 Correct 218 ms 17460 KB Output is correct
12 Correct 231 ms 17844 KB Output is correct
13 Correct 217 ms 17424 KB Output is correct
14 Correct 221 ms 17560 KB Output is correct
15 Correct 232 ms 19060 KB Output is correct
16 Correct 218 ms 17420 KB Output is correct
17 Correct 227 ms 17876 KB Output is correct
18 Correct 239 ms 19512 KB Output is correct
19 Correct 242 ms 18900 KB Output is correct
20 Correct 225 ms 17760 KB Output is correct
21 Correct 238 ms 19524 KB Output is correct
22 Correct 236 ms 19336 KB Output is correct
23 Correct 232 ms 19524 KB Output is correct
24 Correct 237 ms 19268 KB Output is correct
25 Correct 237 ms 19532 KB Output is correct
26 Correct 238 ms 19744 KB Output is correct
27 Correct 241 ms 19652 KB Output is correct
28 Correct 233 ms 19420 KB Output is correct
29 Correct 244 ms 19764 KB Output is correct
30 Correct 240 ms 19724 KB Output is correct
31 Correct 1 ms 332 KB Output is correct
32 Correct 1 ms 332 KB Output is correct
33 Correct 1 ms 332 KB Output is correct
34 Correct 1 ms 332 KB Output is correct
35 Incorrect 1 ms 332 KB Output isn't correct
36 Halted 0 ms 0 KB -