Submission #373152

#	Time	Username	Problem	Language	Result	Execution time	Memory
373152		LucaDantas	Collecting Stamps 3 (JOI20_ho_t3)	C++17	0 / 100	43 ms	72812 KiB

ho_t3

#include<bits/stdc++.h>

#define ff first
#define ss second

constexpr int maxn = 200+10;

std::pair<int,int> a[maxn];

int dp[maxn][maxn][maxn][2];

void min_self(int& a, int b) { a = std::min(a, b); }

int main() {
	int n, T; scanf("%d %d", &n, &T);
	for(int i = 1; i <= n; i++)
		scanf("%d", &a[i].ff);
	for(int i = 1; i <= n; i++)
		scanf("%d", &a[i].ss);
	a[0] = {0, -1}; // a origem
	++n;
	auto prev = [&](int x) {
		return (x+n-1)%n;
	};
	auto next = [&](int x) {
		return (x+1)%n;
	};
	auto dist = [&](int x, int y) {
		if(x > y) return y + T - x;
		return y - x;
	};
	memset(dp, 0x3f, sizeof dp);
	dp[0][0][0][0] = 0;
	for(int sz = 0; sz < n; sz++) {
		for(int l = 0; l < n; l++) {
			int r = (l+sz)%n;
			for(int k = 0; k <= sz; k++) {
				if(std::min(dp[l][r][k][0], dp[l][r][k][1]) == 0x3f3f3f3f || l == r+1) continue;
				// printf("%d %d %d (%d %d)\n\n", l, r, k, dp[l][r][k][0], dp[l][r][k][1]);
				
				// eu ligando com o anterior com o ptr na esq do itv
				int t = dp[l][r][k][0] + dist(a[prev(l)].first, a[l].first);
				min_self(dp[prev(l)][r][k+(t<=a[prev(l)].second)][0], t);
				// printf("%d %d\n", t, prev(l));

				// eu ligando com o anterior com o ptr na dir do itv
				t = dp[l][r][k][1] + dist(a[prev(l)].first, a[r].first);
				min_self(dp[prev(l)][r][k+(t<=a[prev(l)].second)][0], t);

				// eu ligando com o proximo com o ptr na esq do itv
				t = dp[l][r][k][0] + dist(a[l].first, a[next(r)].first);
				min_self(dp[l][next(r)][k+(t<=a[next(r)].second)][1], t);
				// eu ligando com o proximo com o ptr na dir do itv
				t = dp[l][r][k][1] + dist(a[r].first, a[next(r)].first);
				min_self(dp[l][next(r)][k+(t<=a[next(r)].second)][1], t);
			}
		}
	}

	int ans = 0;
	for(int k = 0; k <= n; k++)
		for(int l = 0; l <= n; l++)
			for(int r = 0; r <= n; r++)
				for(int b : {0, 1})
					if(dp[l][r][k][b] < 0x3f3f3f3f)
						ans = k;
	printf("%d\n", ans);
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:15:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   15 |  int n, T; scanf("%d %d", &n, &T);
      |            ~~~~~^~~~~~~~~~~~~~~~~
ho_t3.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   17 |   scanf("%d", &a[i].ff);
      |   ~~~~~^~~~~~~~~~~~~~~~
ho_t3.cpp:19:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   19 |   scanf("%d", &a[i].ss);
      |   ~~~~~^~~~~~~~~~~~~~~~

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