Submission #1063147

#TimeUsernameProblemLanguageResultExecution timeMemory
1063147WhisperCollecting Stamps 3 (JOI20_ho_t3)C++17
100 / 100
108 ms129724 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int long long #define FOR(i, a, b) for (int i = (a); i <= (b); i++) #define FORD(i, a, b) for (int i = (b); i >= (a); i --) #define REP(i, a) for (int i = 0; i < (a); ++i) #define REPD(i, a) for (int i = (a) - 1; i >= 0; --i) #define MASK(i) (1LL << (i)) #define BIT(x, i) (((x) >> (i)) & 1) constexpr ll LINF = (1ll << 60); constexpr int INF = (1ll << 30); constexpr int Mod = 1e9 + 7; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); /* Phu Trong from Nguyen Tat Thanh High School for gifted student */ template <class X, class Y> bool minimize(X &x, const Y &y){ X eps = 1e-9; if (x > y + eps) {x = y; return 1;} return 0; } template <class X, class Y> bool maximize(X &x, const Y &y){ X eps = 1e-9; if (x + eps < y) {x = y; return 1;} return 0; } int nArr, L; #define MAX 202 int A[MAX], T[MAX]; //min DP[l][r][picked][where] = time //where = 0: clock wise //where = 1: counter clock wise int dp[MAX][MAX][MAX][2]; void process(void){ cin >> nArr >> L; for (int i = 1; i <= nArr; ++i) cin >> A[i]; for (int i = 1; i <= nArr; ++i) cin >> T[i]; A[nArr + 1] = L; memset(dp, 0x3f, sizeof dp); REP(i, 2) dp[0][0][0][i] = 0; REP(l, nArr) REP(r, nArr) REP(picked, nArr){ if(l + r + 1 > nArr) continue; int cur = dp[l][r][picked][1]; bool can_pick = 0; can_pick = (cur + (A[r + 1] - A[r]) <= T[r + 1]); minimize(dp[l][r + 1][picked + can_pick][1], cur + (A[r + 1] - A[r])); can_pick = (cur + (A[r] + L - A[nArr - l]) <= T[nArr - l]); minimize(dp[l + 1][r][picked + can_pick][0], cur + (A[r] + L - A[nArr - l])); cur = dp[l][r][picked][0]; can_pick = (cur + (A[nArr - l + 1] - A[nArr - l]) <= T[nArr - l]); minimize(dp[l + 1][r][picked + can_pick][0], cur + (A[nArr - l + 1] - A[nArr - l])); can_pick = (cur + (L - A[nArr - l + 1] + A[r + 1]) <= T[r + 1]); minimize(dp[l][r + 1][picked + can_pick][1], cur + (L - A[nArr - l + 1] + A[r + 1])); } FORD(picked, 0, nArr) FOR(l, 0, nArr) FOR(r, 0, nArr) REP(where, 2){ if(dp[l][r][picked][where] < INF){ return void(cout << picked); } } } signed main(){ #define name "Whisper" cin.tie(nullptr) -> sync_with_stdio(false); //freopen(name".inp", "r", stdin); //freopen(name".out", "w", stdout); process(); return (0 ^ 0); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...