Submission #230071

#	Time	Username	Problem	Language	Result	Execution time	Memory
230071		grt	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	138 ms	134008 KiB

ho_t3

#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 200+10;
const ll INF = 1e18;
int n,l;
int dist[nax], tim[nax];
ll dp[nax][nax][nax][2];

int get_dist(int i, int j) {
	return (i <= j ? dist[j] - dist[i] : l - dist[i] + dist[j]);
}

int main() {_
	cin >> n >> l;
	for(int i = 1; i <= n; ++i) {
		cin >> dist[i];
	}
	for(int i = 1; i <= n; ++i) {
		cin >> tim[i];
	}
	for(int i = 0; i <= n; ++i) {
		for(int j = 0; j <= n; ++j) {
			for(int k = 0; k <= n; ++k) {
				dp[i][j][k][0] = dp[i][j][k][1] = INF;
			}
		}
	}
	dp[0][0][0][0] = 0;
	dp[0][0][0][1] = 0;
	int cur = 0; int cnt = 0;
	int ans = 0;
	for(int i = 1; i <= n; ++i) {
		if(dist[i] <= tim[i]) {
			cnt++;
		}
		dp[0][i][cnt][1] = dist[i];
		dp[0][i][cnt][0] = 2 * dist[i];
		ans = max(ans,cnt);
	}
	cnt = 0;
	dist[n+1] = l;
	for(int i = 1; i <= n; ++i) {
		cur += dist[n-i+2] - dist[n-i+1];
		if(cur <= tim[n - i + 1]) {
			cnt++;
		}
		dp[i][0][cnt][0] = cur;
		dp[i][0][cnt][1] = 2 * cur;
		//cout << i << " " << cur << " " << cnt << "\n";
		ans = max(ans,cnt);
	}
	for(int k = 0; k <= n; ++k) {
	for(int i = 1; i <= n; ++i) {
		for(int j = 1; j <= n; ++j) {
				if(i + j > n || i + j < k) continue;
				dp[i][j][k][0] = min({dp[i][j][k][0],dp[i-1][j][k][0] + get_dist(n - i + 1, n - i +2), dp[i-1][j][k][1] + get_dist(n - i + 1, j)});
				dp[i][j][k][1] = min({dp[i][j][k][1],dp[i][j-1][k][1] + get_dist(j-1, j), dp[i][j-1][k][0] + get_dist(n-i+1, j)});
				if(k > 0) {
					if(tim[n - i + 1] >= min(dp[i-1][j][k][1] + get_dist(n - i + 1, j),dp[i-1][j][k][0] + get_dist(n - i + 1, n - i +2))) {
						dp[i][j][k+1][0] = min(dp[i][j][k+1][0], min(dp[i-1][j][k][1] + get_dist(n - i + 1, j),dp[i-1][j][k][0] + get_dist(n - i + 1, n - i +2)));
					}
					if(tim[j] >= min(dp[i][j-1][k][1] + get_dist(j-1, j), dp[i][j-1][k][0] + get_dist(n-i+1, j))) {
						dp[i][j][k+1][1] = min(dp[i][j][k+1][1], min(dp[i][j-1][k][1] + get_dist(j-1, j), dp[i][j-1][k][0] + get_dist(n-i+1, j)));
					}
					if(dp[i][j][k][0] < INF || dp[i][j][k][1] < INF) {
						ans = max(ans,k);
					}
				}
			}
		}
	}
	//~ for(int i = 0; i <= n; ++i) {
		//~ for(int j = 0; j <= n; ++j) {
			//~ for(int k = 0; k <= n; ++k) {
				//~ if(i + j > n || i + j < k) continue;
				//~ for(int o : {0,1}) {
					//~ cout << "[" << i << " " << j << " " << k << " " << o << "] : " << (dp[i][j][k][o] != INF ? dp[i][j][k][o] : -1) << "\n";
				//~ }
			//~ }
		//~ }
	//~ }
	cout << ans;
					
			
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:21:17: warning: assuming signed overflow does not occur when assuming that (X - c) <= X is always true [-Wstrict-overflow]
  return (i <= j ? dist[j] - dist[i] : l - dist[i] + dist[j]);
         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ho_t3.cpp:21:17: warning: assuming signed overflow does not occur when assuming that (X - c) <= X is always true [-Wstrict-overflow]
  return (i <= j ? dist[j] - dist[i] : l - dist[i] + dist[j]);
         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ho_t3.cpp:21:17: warning: assuming signed overflow does not occur when assuming that (X - c) <= X is always true [-Wstrict-overflow]
  return (i <= j ? dist[j] - dist[i] : l - dist[i] + dist[j]);
         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ho_t3.cpp:21:17: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
  return (i <= j ? dist[j] - dist[i] : l - dist[i] + dist[j]);
         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ho_t3.cpp:21:17: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
  return (i <= j ? dist[j] - dist[i] : l - dist[i] + dist[j]);
         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ho_t3.cpp:21:17: warning: assuming signed overflow does not occur when assuming that (X + c) >= X is always true [-Wstrict-overflow]
  return (i <= j ? dist[j] - dist[i] : l - dist[i] + dist[j]);
         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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