Submission #207757

#TimeUsernameProblemLanguageResultExecution timeMemory
207757super_j6Collecting Stamps 3 (JOI20_ho_t3)C++14
0 / 100
5 ms504 KiB
#include <iostream> #include <cstdio> #include <algorithm> #include <string.h> using namespace std; #define endl '\n' #define pi pair<int, int> #define f first #define s second const long long inf = 1000000000000000007; const int maxn = 202; int n, m; pi a[maxn]; long long dp[maxn][maxn][maxn][2]; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cin >> n >> m; for(int i = 1; i <= n; i++) cin >> a[i].f; for(int i = 1; i <= n; i++) cin >> a[i].s; a[n + 1].f = m; sort(a + 1, a + n + 1); for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) for(int k = n + 1; k > j; k--) dp[i][j][k][0] = dp[i][j][k][1] = inf; int ret = 0; dp[0][0][n + 1][0] = dp[0][0][n + 1][1] = 0; for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++) for(int k = n + 1; k > j; k--){ long long x; bool t0 = 0, t1 = 0; if(dp[i][j][k][0] != inf){ ret = i; x = dp[i][j][k][0] + a[j + 1].f - a[j].f; if(x <= dp[i][j + 1][k][0]){ dp[i][j + 1][k][0] = x; t0 = 1; } x = dp[i][j][k][0] + a[j].f + m - a[k - 1].f; if(x <= dp[i][j][k - 1][1]){ dp[i][j][k - 1][1] = x; t1 = 1; } } if(dp[i][j][k][1] != inf){ ret = i; x = dp[i][j][k][1] + a[k].f - a[k - 1].f; if(x <= dp[i][j][k - 1][1]){ dp[i][j][k - 1][1] = x; t1 = 1; } x = dp[i][j][k][1] + a[j + 1].f + m - a[k].f; if(x <= dp[i][j + 1][k][0]){ dp[i][j + 1][k][0] = x; t0 = 1; } } if(t0 && dp[i][j + 1][k][0] <= a[j + 1].s) dp[i + 1][j + 1][k][0] = dp[i][j + 1][k][0]; if(t1 && dp[i][j][k - 1][1] <= a[k - 1].s) dp[i + 1][j][k - 1][1] = dp[i][j][k - 1][1]; } cout << ret << endl; return 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...