Submission #170416

#	Time	Username	Problem	Language	Result	Execution time	Memory
170416		Retro3014	Homecoming (BOI18_homecoming)	C++17	100 / 100	210 ms	118216 KiB

homecoming

#include <bits/stdc++.h>
#include "homecoming.h"

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 1
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e18;
const int MAX_N = 2000000;

ll dp[2][2], A[MAX_N+1], B[MAX_N+1], SA[MAX_N+1], SB[MAX_N+1];
ll ndp[2][2];

int N, K;
ll sumA(int x, int y){
	if(x==0){
		return SA[y];
	}
	if(x<=y){
		return SA[y]-SA[x-1];
	}else{
		return SA[N-1]-SA[x-1]+SA[y];
	}
}
ll sumB(int x, int y){
	if(x==0)	return SB[y];
	if(x<=y){
		return SB[y]-SB[x-1];
	}else{
		return SB[N-1]-SB[x-1]+SB[y];
	}	
}

long long int solve(int n, int k, int *C, int *D){
	N = n; K = k;
	for(int i=0; i<N; i++){
		A[i] = (ll)C[i];
		B[i] = (ll)D[i];
		if(i!=0){
			SA[i] = SA[i-1] + A[i];
			SB[i] = SB[i-1] + B[i];
		}else{
			SA[i] = A[i]; SB[i] = B[i];
		}
	}
	dp[0][0] = 0;
	dp[0][1] = 0;
	dp[1][0] = A[0] - sumB(0, K-1);
	dp[1][1] = A[0] - B[K-1];
	for(int i=1; i<N; i++){
		for(int j=0; j<2; j++){
			ndp[0][j] = max(dp[0][j], dp[1][j]);
			ndp[1][j] = max(dp[1][j] + A[i] - B[(i+K-1)%N], dp[0][j] + A[i] - sumB(i, (i+K-1)%N));
			dp[0][j] = ndp[0][j]; dp[1][j] = ndp[1][j];
		}
	}
	return max(dp[0][0], dp[1][1]);
}

• Subtask 1: 13 / 13
• Subtask 2: 18 / 18
• Subtask 3: 31 / 31
• Subtask 4: 38 / 38