Submission #446990

#	Time	Username	Problem	Language	Result	Execution time	Memory
446990		maomao90	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	208 ms	300240 KiB

ho_t3

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

template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;

#ifdef DEBUG
#define debug(args...) _debug(args)
void _debug(const char* format, ...) {
	va_list args;
	va_start(args, format);
	vprintf(format, args);
	va_end(args);
}
#else
#define debug(args...)
#endif

#define INF 2000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 205

int n, l;
ll x[MAXN], t[MAXN];
ll dp[MAXN][MAXN][5][MAXN];
int ans;

int main() {
	scanf("%d%d", &n, &l);
	REP (i, 1, n + 1) {
		scanf("%lld", &x[i]);
	}
	REP (i, 1, n + 1) {
		scanf("%lld", &t[i]);
	}
	x[0] = 0;
	t[0] = -1;
	n++;
	REP (i, 0, n + 3) {
		REP (j, 0, n + 3) {
			REP (m, 0, 2) {
				REP (k, 0, n + 3) {
					dp[i][j][m][k] = LINF;
				}
			}
		}
	}
	dp[0][0][0][0] = dp[0][0][1][0] = 0;
	// dp[i][j][m][k] is with range from s to e and currently at s,
	// minimum time to take k stamps
	// i is the length, j is starting point, m is positive or negative
	REP (i, 1, n) {
		REP (j, 0, n) {
			REP (m, 0, 2) {
				int p = m ? 1 : -1;
				int s = j, e = (j + i * p + n) % n;
				REP (k, 0, n) {
					int pk = k;
					ll pc = min(abs(x[s] - x[(s + p + n) % n]), 
							min(abs(x[s] - x[(s + p + n) % n] - l), 
								abs(x[s] - x[(s + p + n) % n] + l)));
					debug(" %lld %lld\n", x[s] - x[(s + p + n) % n], pc);
					if (k != 0 && dp[i - 1][(j + p + n) % n][m][k - 1] + pc <= t[s]) {
					   pk--;
					}
					mnto(dp[i][j][m][k], dp[i - 1][(j + p + n) % n][m][pk] + pc);
					int ppk = k;
					ll ppc = min(abs(x[e] - x[s]), 
							min(abs(x[e] - x[s] - l), 
								abs(x[e] - x[s] + l)));
					debug(" %lld %lld\n", x[e] - x[s], ppc);
					if (k != 0 && dp[i - 1][e][!m][k - 1] + ppc <= t[s]) {
					   ppk--;
					}
					mnto(dp[i][j][m][k], dp[i - 1][e][!m][ppk] + ppc);
					debug("%d %d %d %d: %lld\n", s, e, p, k, dp[i][j][m][k]);
					if (dp[i][j][m][k] < LINF) {
						mxto(ans, k);
					}
				}
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  scanf("%d%d", &n, &l);
      |  ~~~~~^~~~~~~~~~~~~~~~
ho_t3.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |   scanf("%lld", &x[i]);
      |   ~~~~~^~~~~~~~~~~~~~~
ho_t3.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |   scanf("%lld", &t[i]);
      |   ~~~~~^~~~~~~~~~~~~~~

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