oj.uz

Submission #69734

# Submission time Handle Problem Language Result Execution time Memory
69734 2018-08-21T12:21:01 Z khohko Homecoming (BOI18_homecoming) C++17
100 / 100
 698 ms 173676 KB 
#include<bits/stdc++.h>
#include "homecoming.h"
using namespace std;
#define ll long long
#define fr first
#define sc second
#define pb push_back
#define ARRS ((ll)(6e6+100))
#define MAX ((ll)(1e16+100))


ll a[ARRS];
ll b[ARRS];
ll s[ARRS];
ll dp[ARRS][2];

ll sum(ll l,ll r){
	return s[r]-s[l-1];
}

long long solve(int n, int K, int *B, int *A){
	ll pas=0,p=0;
	for(int i=1; i<=n; i++){
		a[i]=A[i-1];
		a[i+n]=A[i-1];

		b[i]=B[i-1];
		b[i+n]=B[i-1];

		p-=a[i];
		p+=b[i];
	}
	for(int i=1; i<=2*n; i++)s[i]=s[i-1]+a[i];
	pas=max(pas,p);

	pair<ll,ll> mn={MAX,MAX};
	ll es=0,l=1;
	vector<pair<ll,ll> > g;
	for(int i=n+1; i<=2*n; i++){
		//ll sm=0;
		//for(int j=i; j<=2*n; j++){
		//	sm-=a[j]-b[j];
		if(i-l>=n)es+=a[l]-b[l++];
		if(es>=0)es=0,l=i;
		es-=a[i]-b[i];
		mn=min(mn,{es,i-1});
		g.pb({es,i-1});
	}
	sort(g.begin(),g.end());
	for(int i=0; i<10; i++){



	ll s=g[i].sc;
	s++;
	s%=n;
	dp[0][0]=0;
	dp[0][1]=-MAX;
	for(int i=1; i<=n; i++){
		dp[i][0]=dp[i-1][0];
		dp[i][1]=-MAX;
		if(i>=K){
			dp[i][1]=max(dp[i][1],dp[i-K][0]+b[i-K+1+s]-sum(i-K+1+s,i+s));
			dp[i][1]=max(dp[i][1],dp[i-1][1]+b[i-K+1+s]-a[i+s]);
		}
		dp[i][0]=max(dp[i][0],dp[i][1]);
		//cout<<dp[i][0]<<" "<<dp[i][1]<<endl;
	}
	pas=max(pas,dp[n][0]);

	}
	//cout<<endl;

	return pas;
}

Compilation message

homecoming.cpp: In function 'long long int solve(int, int, int*, int*)':
homecoming.cpp:43:25: warning: operation on 'l' may be undefined [-Wsequence-point]
   if(i-l>=n)es+=a[l]-b[l++];
                        ~^~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 612 KB Output is correct
3 Correct 3 ms 612 KB Output is correct
4 Correct 3 ms 736 KB Output is correct
5 Correct 3 ms 736 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 612 KB Output is correct
3 Correct 3 ms 612 KB Output is correct
4 Correct 3 ms 736 KB Output is correct
5 Correct 3 ms 736 KB Output is correct
6 Correct 4 ms 1208 KB Output is correct
7 Correct 4 ms 1208 KB Output is correct
8 Correct 4 ms 1208 KB Output is correct
9 Correct 4 ms 1208 KB Output is correct
10 Correct 4 ms 1208 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 43848 KB Output is correct
2 Correct 10 ms 43848 KB Output is correct
3 Correct 682 ms 173112 KB Output is correct
4 Correct 8 ms 173112 KB Output is correct
5 Correct 25 ms 173112 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 612 KB Output is correct
3 Correct 3 ms 612 KB Output is correct
4 Correct 3 ms 736 KB Output is correct
5 Correct 3 ms 736 KB Output is correct
6 Correct 4 ms 1208 KB Output is correct
7 Correct 4 ms 1208 KB Output is correct
8 Correct 4 ms 1208 KB Output is correct
9 Correct 4 ms 1208 KB Output is correct
10 Correct 4 ms 1208 KB Output is correct
11 Correct 164 ms 43848 KB Output is correct
12 Correct 10 ms 43848 KB Output is correct
13 Correct 682 ms 173112 KB Output is correct
14 Correct 8 ms 173112 KB Output is correct
15 Correct 25 ms 173112 KB Output is correct
16 Correct 698 ms 173540 KB Output is correct
17 Correct 234 ms 173540 KB Output is correct
18 Correct 439 ms 173540 KB Output is correct
19 Correct 517 ms 173540 KB Output is correct
20 Correct 481 ms 173676 KB Output is correct
21 Correct 428 ms 173676 KB Output is correct