oj.uz

Submission #126482

# Submission time Handle Problem Language Result Execution time Memory
126482 2019-07-07T21:05:34 Z hugo_pm Homecoming (BOI18_homecoming) C++17
100 / 100
 249 ms 133752 KB 
#include <bits/stdc++.h>
#include "homecoming.h"
using namespace std;

#define int long long
#define form2(i, a, b) for (int i = (a); i < (b); ++i)
#define ford2(i, a, b) for (int i = (a-1); i >= (b); --i)
#define form(i, n) form2(i, 0, n)
#define ford(i, n) ford2(i, n, 0)

#define chmax(x, v) x = max(x, (v))
#define chmin(x, v) x = min(x, (v))
#define fi first
#define se second

const long long BIG = 1000000000000000000LL;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int PRIS=0, NON=1;

const int borne = 2*1000*1000 + 5;
int nbLivres, lenCyc;
int rcp[borne];
int prix[borne];
int somPrix[borne];
int dp[borne][2];

int getSom(int a, int b)
{
	if (a > b) return getSom(a, nbLivres - 1) + getSom(0, b);
	int rep = somPrix[b];
	if (a) rep -= somPrix[a-1];
	return rep;
}

long long solve(signed N, signed K, signed *A, signed *B)
{
	nbLivres = N; lenCyc = K;
	form(i, nbLivres) {
		rcp[i] = A[i];
		prix[i] = B[i];
		somPrix[i] = prix[i];
		if (i) somPrix[i] += somPrix[i-1];
	}

	// Cas 1 : on prend le premier livre

	dp[0][NON] = -BIG;
	dp[0][PRIS] = rcp[0] - getSom(0, lenCyc-1);

	form2(iElem, 1, nbLivres) {
		int newAdd = (iElem + lenCyc - 1); // TODO PAS MOD

		// PRIS, et prev pris
		if (true) {
			int rep = dp[iElem-1][PRIS];
			if (newAdd < nbLivres) rep -= prix[newAdd];
			rep += rcp[iElem];
			dp[iElem][PRIS] = rep;
		}
		// PRIS, et prev pas pris
		if (true) {
			int rep = dp[iElem-1][NON];
			rep += rcp[iElem];
			rep -= getSom(iElem, min(newAdd, nbLivres-1));
			chmax(dp[iElem][PRIS], rep);
		}

		// NON
		dp[iElem][NON] = max(dp[iElem-1][PRIS], dp[iElem-1][NON]);
	}

	int repCas1 = max(dp[nbLivres-1][PRIS], dp[nbLivres-1][NON]);
	
	// Cas 2 : on ne prend pas le premier livre

	dp[0][PRIS] = -BIG;
	dp[0][NON] = 0;

	form2(iElem, 1, nbLivres) {
		int newAdd = (iElem + lenCyc - 1) % nbLivres;
		
		// PRIS, et prev pris
		if (true) {
			int rep = dp[iElem-1][PRIS];
			rep += rcp[iElem];
			rep -= prix[newAdd];
			dp[iElem][PRIS] = rep;
		}
		// PRIS, et prev pas pris
		if (true) {
			int rep = dp[iElem-1][NON];
			rep += rcp[iElem];
			rep -= getSom(iElem, newAdd);
			chmax(dp[iElem][PRIS], rep);
		}

		// NON
		dp[iElem][NON] = max(dp[iElem-1][PRIS], dp[iElem-1][NON]);
	}

	int repCas2 = max(dp[nbLivres-1][PRIS], dp[nbLivres-1][NON]);

	int wo = max(repCas1, repCas2);
	assert(wo >= 0);
	return wo;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 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 2 ms 376 KB Output is correct
2 Correct 2 ms 376 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 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 3 ms 504 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 23800 KB Output is correct
2 Correct 5 ms 1020 KB Output is correct
3 Correct 248 ms 133752 KB Output is correct
4 Correct 4 ms 1532 KB Output is correct
5 Correct 13 ms 3536 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 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 632 KB Output is correct
7 Correct 2 ms 632 KB Output is correct
8 Correct 3 ms 504 KB Output is correct
9 Correct 3 ms 760 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 62 ms 23800 KB Output is correct
12 Correct 5 ms 1020 KB Output is correct
13 Correct 248 ms 133752 KB Output is correct
14 Correct 4 ms 1532 KB Output is correct
15 Correct 13 ms 3536 KB Output is correct
16 Correct 249 ms 133600 KB Output is correct
17 Correct 112 ms 29856 KB Output is correct
18 Correct 186 ms 42636 KB Output is correct
19 Correct 183 ms 74580 KB Output is correct
20 Correct 201 ms 116728 KB Output is correct
21 Correct 178 ms 72008 KB Output is correct