oj.uz

Submission #73912

# Submission time Handle Problem Language Result Execution time Memory
73912 2018-08-29T09:13:48 Z zscoder Homecoming (BOI18_homecoming) C++17
62 / 100
 1000 ms 149700 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "homecoming.h"

using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;

ll prefa[4222222];
ll prefb[4222222];
ll dp[2][2222222];
ll suma(int l, int r)
{
	if(l==0) return prefa[r];
	else return prefa[r]-prefa[l-1];
}

ll sumb(int l, int r)
{
	if(l>r) return 0;
	if(l==0) return prefb[r];
	else return prefb[r]-prefb[l-1];
}

const ll INF=ll(1e18);
ll solve(int n, int k, int *a, int *b)
{
	ll ans = 0;
	for(int i=0;i<2*n;i++)
	{
		prefa[i]=a[i%n]; prefb[i]=b[i%n];
		if(i>0) 
		{
			prefa[i]+=prefa[i-1]; prefb[i]+=prefb[i-1];
		}
	}
	ans = max(0LL,prefa[n-1]-prefb[n-1]);
	if(k==n) return ans;
	for(int s=0;s<k;s++)
	{
		//s must be a starting point
		for(int j=0;j<2;j++)
		{
			for(int z=0;z<n;z++)
			{
				dp[j][z]=-INF;
			}
		}
		dp[1][s] = a[s] - sumb(s,s+k-1);
		ans=max(ans,dp[1][s]);
		if(s==k-1)
		{
			dp[0][s]=0;
		}
		for(int i=s+1;i<n;i++)
		{
			dp[0][i] = max(dp[0][i-1], dp[1][i-1]);
			dp[1][i] = max(dp[0][i-1] + a[i] - sumb(i, min(n+s-1, i+k-1)), dp[1][i-1] + a[i] - (i+k-1>=n+s?0:b[(i+k-1)%n]));
			//cerr<<0<<' '<<s<<' '<<i<<' '<<dp[0][s][i]<<'\n';
			//cerr<<1<<' '<<s<<' '<<i<<' '<<dp[1][s][i]<<'\n';
			ans=max(ans,dp[0][i]);
			ans=max(ans,dp[1][i]);
		}
	}
	return ans;
}	

/*
int aaaa[2111111];
int bbbb[2111111];
int main()
{
	int n,k;
	cin>>n>>k;
	for(int i=0;i<n;i++)
	{
		cin>>aaaa[i];
	}
	for(int i=0;i<n;i++)
	{
		cin>>bbbb[i];
	}
	cout<<solve(n,k,aaaa,bbbb)<<'\n';
}
*/

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 488 KB Output is correct
3 Correct 3 ms 572 KB Output is correct
4 Correct 3 ms 572 KB Output is correct
5 Correct 3 ms 572 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 4 ms 488 KB Output is correct
3 Correct 3 ms 572 KB Output is correct
4 Correct 3 ms 572 KB Output is correct
5 Correct 3 ms 572 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 116 ms 724 KB Output is correct
8 Correct 27 ms 764 KB Output is correct
9 Correct 8 ms 860 KB Output is correct
10 Correct 3 ms 860 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 27960 KB Output is correct
2 Correct 20 ms 27960 KB Output is correct
3 Correct 233 ms 110408 KB Output is correct
4 Correct 23 ms 110408 KB Output is correct
5 Correct 36 ms 110408 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 4 ms 488 KB Output is correct
3 Correct 3 ms 572 KB Output is correct
4 Correct 3 ms 572 KB Output is correct
5 Correct 3 ms 572 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 116 ms 724 KB Output is correct
8 Correct 27 ms 764 KB Output is correct
9 Correct 8 ms 860 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 73 ms 27960 KB Output is correct
12 Correct 20 ms 27960 KB Output is correct
13 Correct 233 ms 110408 KB Output is correct
14 Correct 23 ms 110408 KB Output is correct
15 Correct 36 ms 110408 KB Output is correct
16 Execution timed out 1069 ms 149700 KB Time limit exceeded
17 Halted 0 ms 0 KB -