oj.uz

Submission #130342

# Submission time Handle Problem Language Result Execution time Memory
130342 2019-07-14T21:26:14 Z qkxwsm Homecoming (BOI18_homecoming) C++14
100 / 100
 354 ms 196224 KB 
#include <bits/stdc++.h>
#include "homecoming.h"

using namespace std;

template<class T, class U>
void ckmin(T &a, U b)
{
	if (a > b) a = b;
}
template<class T, class U>
void ckmax(T &a, U b)
{
	if (a < b) a = b;
}

#define MP make_pair
#define PB push_back
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define FOR(i, a, b) for (auto i = (a); i < (b); i++)
#define FORD(i, a, b) for (auto i = (a) - 1; i >= (b); i--)
#define SZ(x) ((int) ((x).size()))
#define ALL(x) (x).begin(), (x).end()
#define INF 1000000007
#define LLINF 2696969696969696969ll
#define MAXN 4000013

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

int N, K;
ll A[MAXN], B[MAXN];
ll pref[MAXN];
ll dp[MAXN][2][2];
ll ans;

ll range(int l, int r)
{
	return pref[r + 1] - pref[l];
}
ll solve(int n, int k, int *a, int *b)
{
	N = n; K = k;
	FOR(i, 0, N)
	{
		A[i] = a[i];
		B[i] = b[i];
		B[i + N] = b[i];
	}
	FOR(i, 0, 2 * N)
	{
		pref[i + 1] = pref[i] + B[i];
	}
	FOR(i, 0, N)
	{
		FOR(j, 0, 2)
		{
			FOR(k, 0, 2)
			{
				dp[i][j][k] = -LLINF;
			}
		}
	}
	dp[0][0][0] = 0;
	dp[0][1][1] = A[0] - range(0, K - 1);
	FOR(i, 1, N)
	{
		ckmax(dp[i][1][1], dp[i - 1][1][1] + A[i] - (i + K - 1 >= N ? 0 : B[i + K - 1]));
		ckmax(dp[i][1][1], dp[i - 1][0][1] + A[i] - range(i, min(N - 1, i + K - 1)));
		ckmax(dp[i][1][0], dp[i - 1][1][0] + A[i] - B[i + K - 1]);
		ckmax(dp[i][1][0], dp[i - 1][0][0] + A[i] - range(i, i + K - 1));
		ckmax(dp[i][0][1], dp[i - 1][1][1]);
		ckmax(dp[i][0][1], dp[i - 1][0][1]);
		ckmax(dp[i][0][0], dp[i - 1][1][0]);
		ckmax(dp[i][0][0], dp[i - 1][0][0]);
	}
	ans = 0;
	FOR(i, 0, 2)
	{
		FOR(j, 0, 2)
		{
			ckmax(ans, dp[N - 1][i][j]);
		}
	}
	return ans;
}

Subtask #1
13.0 / 13.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 888 KB Output is correct
7 Correct 3 ms 888 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 888 KB Output is correct
10 Correct 2 ms 504 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 49016 KB Output is correct
2 Correct 4 ms 888 KB Output is correct
3 Correct 354 ms 195772 KB Output is correct
4 Correct 4 ms 2168 KB Output is correct
5 Correct 12 ms 4236 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 888 KB Output is correct
7 Correct 3 ms 888 KB Output is correct
8 Correct 2 ms 632 KB Output is correct
9 Correct 2 ms 888 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 69 ms 49016 KB Output is correct
12 Correct 4 ms 888 KB Output is correct
13 Correct 354 ms 195772 KB Output is correct
14 Correct 4 ms 2168 KB Output is correct
15 Correct 12 ms 4236 KB Output is correct
16 Correct 265 ms 196224 KB Output is correct
17 Correct 97 ms 37752 KB Output is correct
18 Correct 158 ms 45996 KB Output is correct
19 Correct 180 ms 105940 KB Output is correct
20 Correct 270 ms 179164 KB Output is correct
21 Correct 176 ms 103376 KB Output is correct