oj.uz

Submission #373152

# Submission time Handle Problem Language Result Execution time Memory
373152 2021-03-03T14:25:31 Z LucaDantas Collecting Stamps 3 (JOI20_ho_t3) C++17
0 / 100
 43 ms 72812 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 72812 KB Output is correct
2 Correct 39 ms 72812 KB Output is correct
3 Incorrect 39 ms 72812 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 72812 KB Output is correct
2 Correct 39 ms 72812 KB Output is correct
3 Incorrect 39 ms 72812 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 72812 KB Output is correct
2 Correct 39 ms 72812 KB Output is correct
3 Incorrect 39 ms 72812 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 72812 KB Output is correct
2 Correct 39 ms 72812 KB Output is correct
3 Incorrect 39 ms 72812 KB Output isn't correct
4 Halted 0 ms 0 KB -