oj.uz

답안 #69741

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
69741 2018-08-21T12:26:57 Z khohko Homecoming (BOI18_homecoming) C++17
100 / 100
 703 ms 176100 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<5; 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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 536 KB Output is correct
3 Correct 2 ms 536 KB Output is correct
4 Correct 2 ms 536 KB Output is correct
5 Correct 3 ms 648 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 536 KB Output is correct
3 Correct 2 ms 536 KB Output is correct
4 Correct 2 ms 536 KB Output is correct
5 Correct 3 ms 648 KB Output is correct
6 Correct 4 ms 1108 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct
8 Correct 3 ms 1108 KB Output is correct
9 Correct 3 ms 1124 KB Output is correct
10 Correct 3 ms 1124 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 154 ms 43836 KB Output is correct
2 Correct 7 ms 43836 KB Output is correct
3 Correct 617 ms 172996 KB Output is correct
4 Correct 8 ms 172996 KB Output is correct
5 Correct 22 ms 172996 KB Output is correct

Subtask #4
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 536 KB Output is correct
3 Correct 2 ms 536 KB Output is correct
4 Correct 2 ms 536 KB Output is correct
5 Correct 3 ms 648 KB Output is correct
6 Correct 4 ms 1108 KB Output is correct
7 Correct 3 ms 1108 KB Output is correct
8 Correct 3 ms 1108 KB Output is correct
9 Correct 3 ms 1124 KB Output is correct
10 Correct 3 ms 1124 KB Output is correct
11 Correct 154 ms 43836 KB Output is correct
12 Correct 7 ms 43836 KB Output is correct
13 Correct 617 ms 172996 KB Output is correct
14 Correct 8 ms 172996 KB Output is correct
15 Correct 22 ms 172996 KB Output is correct
16 Correct 703 ms 176068 KB Output is correct
17 Correct 229 ms 176068 KB Output is correct
18 Correct 441 ms 176068 KB Output is correct
19 Correct 446 ms 176068 KB Output is correct
20 Correct 432 ms 176100 KB Output is correct
21 Correct 386 ms 176100 KB Output is correct