Submission #251985

#	Time	Username	Problem	Language	Result	Execution time	Memory
251985		ivandasfs	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	121 ms	135296 KiB

ho_t3

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

typedef long long ll;

#define pb push_back
#define mp make_pair
#define x first
#define y second

const ll MOD = 1e9+7;
const ll INF = 1e18+5;

// dp[pos][0/1 = l/r][l+r][skupljeno] = mintime;

pair <ll, ll> a[205];
ll dp[205][2][205][205];

int main() {
	for (int i=0 ; i<205 ; i++) {
		for (int j=0 ; j<205 ; j++) {
			for (int k=0 ; k<205 ; k++) {
				dp[i][0][j][k] = INF;
				dp[i][1][j][k] = INF;
			}
		}
	}
	int n;
	ll l;
	scanf("%d%lld", &n, &l);
	for (int i=0 ; i<n ; i++) {
		scanf("%lld", &a[i].x);
	}
	for (int i=0 ; i<n ; i++) {
		scanf("%lld", &a[i].y);
	}
	sort(a, a+n);
	int maxx = 0;
	if (a[0].x <= a[0].y or l - a[n-1].x <= a[n-1].y) maxx = 1;
	dp[0][0][1][a[0].x <= a[0].y] = a[0].x;
	dp[n-1][1][1][l - a[n-1].x <= a[n-1].y] = l - a[n-1].x;
	for (int i=2 ; i<=n ; i++) {
		for (int pos=0 ; pos<n ; pos++) {
			for (int sk = 0 ; sk<=n ; sk++) {
				if (dp[pos][0][i-1][sk] != INF) {
					ll tim = dp[pos][0][i-1][sk];
					ll nxt = a[pos+1].x - a[pos].x;
					if (tim + nxt <= a[pos+1].y) {
						dp[pos+1][0][i][sk+1] = min(dp[pos+1][0][i][sk+1], tim + nxt);
						maxx = max(maxx, sk+1);
					} else {
						dp[pos+1][0][i][sk] = min(dp[pos+1][0][i][sk], tim + nxt);
					}
					int indp = n+pos-i+1;
					ll prev = a[pos].x + l - a[indp].x;
					if (tim + prev <= a[indp].y) {
						dp[indp][1][i][sk+1] = min(dp[indp][1][i][sk+1], tim + prev);
						maxx = max(maxx, sk+1);
					} else {
						dp[indp][1][i][sk] = min(dp[indp][1][i][sk], tim + prev);
					}
				}
				if (dp[pos][1][i-1][sk] != INF) {
					ll tim = dp[pos][1][i-1][sk];
					ll prev = a[pos].x - a[pos-1].x;
					if (tim + prev <= a[pos-1].y) {
						dp[pos-1][1][i][sk+1] = min(dp[pos-1][1][i][sk+1], tim + prev);
						maxx = max(maxx, sk+1);
					} else {
						dp[pos-1][1][i][sk] = min(dp[pos-1][1][i][sk], tim + prev);
					}
					int indn = (pos + i - 1) % n;
					ll nxt = l - a[pos].x + a[indn].x;
					if (tim + nxt <= a[indn].y) {
						dp[indn][0][i][sk+1] = min(dp[indn][0][i][sk+1], tim + nxt);
						maxx = max(maxx, sk+1);
					} else {
						dp[indn][0][i][sk] = min(dp[indn][0][i][sk], tim + nxt);
					}
				}
			}
		}
	}
	printf("%d\n", maxx);
	return 0;
}

Compilation message (stderr)

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

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