Submission #201343

#TimeUsernameProblemLanguageResultExecution timeMemory
201343AtalasionCollecting Stamps 3 (JOI20_ho_t3)C++14
15 / 100
63 ms72956 KiB
//khodaya khodet komak kon #include <bits/stdc++.h> #define F first #define S second #define pb push_back #define all(x) x.begin(), x.end() #pragma GCC optimise ("ofast") #pragma GCC optimise("unroll-loops") using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef vector<int> vi; const int N = 200 + 10; const ll MOD = 1000000000 + 7; const ll INF = 1000000000000000000; const ll LOG = 25; int dp[N][N][N][2]; int n, x[N], L, T[N]; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> L; for (int i = 1; i <= n; i++) cin >> x[i]; for (int i = 1; i <= n; i++) cin >> T[i]; x[n + 1] = L; memset(dp, 31, sizeof dp); dp[0][0][0][0] = dp[0][0][0][1] = 0; for (int i = 0; i <= n; i++){ for (int j = 0; j <= n - i - 1; j++){ for (int k = 0; k <= (i + j); k++){ //cout << i << ' ' << j << ' ' << k << ' ' << dp[i][j][k][0] << ' ' << dp[i][j][k][1] << '\n'; int ti = dp[i][j][k][0]; if (ti + x[i + 1] - x[i] <= T[i + 1]) dp[i + 1][j][k + 1][0] = min(dp[i + 1][j][k + 1][0], ti + x[i + 1] - x[i]); else dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], ti + x[i + 1] - x[i]); //cout << ti + x[i] + L - x[n - j] << '\n'; if (ti + x[i] + L - x[n - j] <= T[n - j]) dp[i][j + 1][k + 1][1] = min(dp[i][j + 1][k + 1][1], ti + x[i] + L - x[n - j]); else dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1], ti + x[i] + L - x[n - j]); ti = dp[i][j][k][1]; if (ti + x[n - j + 1] - x[n - j] <= T[n - j]) dp[i][j + 1][k + 1][1] = min(dp[i][j + 1][k + 1][1], ti + x[n - j + 1] - x[n - j]); else dp[i][j + 1][k][1] = min(dp[i][j + 1][k][1], ti + x[n - j + 1] - x[n - j]); if (L - x[n - j + 1] + ti + x[i + 1] <= T[i + 1]) dp[i + 1][j][k + 1][0] = min(dp[i + 1][j][k + 1][0], L - x[n - j + 1] + ti + x[i + 1]); else dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], L - x[n - j + 1] + ti + x[i + 1]); } } } int ans = 0; for (int i = 1; i <= n; i++){ for (int j = 0; j <= n; j++){ if (min(dp[j][n - j][i][0], dp[j][n - j][i][1]) <= (100000000ll)) ans = i; } } cout << ans; return 0; }

Compilation message (stderr)

ho_t3.cpp:8:0: warning: ignoring #pragma GCC optimise [-Wunknown-pragmas]
 #pragma GCC optimise ("ofast")
 
ho_t3.cpp:9:0: warning: ignoring #pragma GCC optimise [-Wunknown-pragmas]
 #pragma GCC optimise("unroll-loops")
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...