oj.uz

Submission #126480

# Submission time Handle Problem Language Result Execution time Memory
126480 2019-07-07T21:00:55 Z hugo_pm Homecoming (BOI18_homecoming) C++17
0 / 100
 63 ms 33272 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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 33272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -