제출 #378256

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
378256		peijar	Collecting Stamps 3 (JOI20_ho_t3)	C++17	0 / 100	42 ms	63852 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;

const int INF = 2e9;
const int MAXN = 201;

int minTime[MAXN][MAXN][MAXN][2];

signed main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	for (int nbPref = 0; nbPref < MAXN; ++nbPref) 
		for (int nbSuff = 0; nbSuff < MAXN; ++nbSuff) 
			for (int nbPris = 0; nbPris < MAXN; ++nbPris) 
				for (int pos = 0; pos < 2; ++pos) 
					minTime[nbPref][nbSuff][nbPris][pos] = INF;

	int nbStamps, longueur;
	cin >> nbStamps >> longueur;
	vector<int> positions(nbStamps);
	vector<int> tempsMax(nbStamps);
	for (auto &v : positions)
		cin >> v;
	for (auto &v : tempsMax)
		cin >> v;
	positions.insert(positions.begin(), 0);
	tempsMax.insert(tempsMax.begin(), INF);
	minTime[0][0][0][0] = 0;
	int sol = 0;
	for (int nbPref = 0; nbPref <= nbStamps; ++nbPref) 
		for (int nbSuff = 0; nbSuff <= nbStamps; ++nbSuff) 
			for (int nbPris = 0; nbPris <= nbStamps; ++nbPris) 
				for (int iPos(0); iPos < 2; ++iPos)
					if (minTime[nbPref][nbSuff][nbPris][iPos] < INF)
					{
						sol = max(sol, nbPris);
						int temps = minTime[nbPref][nbSuff][nbPris][iPos];
						//cout << nbPref << ' ' << nbSuff << ' ' << nbPris << ' ' << iPos << ' ' << temps << endl;
						if (nbPref + 1 + nbSuff > nbStamps) continue;
						if (!iPos)
						{
								int nxtTemps = temps + positions[nbPref+1] - positions[nbPref];
								int nxtPris = nbPris + (nxtTemps <= tempsMax[nbPref+1]);
								minTime[nbPref+1][nbSuff][nxtPris][0] =
									min(minTime[nbPref+1][nbSuff][nxtPris][0], nxtTemps);
								nxtTemps = temps + positions[nbPref] + (longueur - positions[nbStamps - nbSuff]);
								nxtPris = nbPris + (nxtTemps <= tempsMax[nbStamps-nbSuff]);
								minTime[nbPref][nbSuff+1][nxtPris][1] = 
									min(minTime[nbPref][nbSuff+1][nxtPris][1], nxtTemps);
						}
						else if (nbSuff)
						{
							int nxtTemps = temps + positions[nbStamps-nbSuff+1]
								- positions[nbStamps-nbSuff];
							int nxtPris = nbPris + (nxtTemps <= tempsMax[nbStamps-nbSuff]);
							minTime[nbPref][nbSuff+1][nxtPris][1] = 
								min(minTime[nbPref][nbSuff+1][nxtPris][1], nxtTemps);
							nxtTemps = temps + (longueur - positions[nbStamps-nbSuff+1]);
							nxtPris = nbPris + (nxtTemps <= tempsMax[nbPref+1]);
							minTime[nbPref+1][nbSuff][nxtPris][0] = 
								min(minTime[nbPref+1][nbSuff][nxtPris][0], nxtTemps);
						}
					}
	cout << sol << endl;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75