Submission #18106

#TimeUsernameProblemLanguageResultExecution timeMemory
18106tncks0121도장 모으기 (JOI14_stamps)C++14
0 / 100
30 ms73948 KiB
#include <stdio.h> #include <stdlib.h> #include <string.h> #include <memory.h> #include <math.h> #include <assert.h> #include <stack> #include <queue> #include <map> #include <set> #include <algorithm> #include <string> #include <functional> #include <vector> #include <deque> #include <utility> #include <bitset> #include <limits.h> #include <time.h> #include <functional> #include <numeric> using namespace std; typedef long long ll; typedef unsigned long long llu; typedef double lf; typedef unsigned int uint; typedef long double llf; typedef pair<int, int> pii; const int N_ = 3050; int N; ll T; int U[N_], V[N_], D[N_], E[N_]; ll sum1[N_]; // U+V ll sum2[N_]; // min(U+V, D+E) ll C1[N_], C2[N_], C3[N_], C4[N_]; ll tb[N_][N_]; void upd (ll &t, ll v) { if(t > v) t = v; } int main() { scanf("%d%lld", &N, &T); for(int i = 1; i <= N; i++) scanf("%d%d%d%d", U+i, V+i, D+i, E+i); for(int i = 1; i <= N; i++) { C1[i] = U[i] + V[i]; C2[i] = D[i] + E[i]; C3[i] = U[i] + E[i]; C4[i] = D[i] + V[i]; for(int j = i-1; j > 0; j--) { upd(C4[i], T * (i - j) * 2 + min(C1[i], C2[i]) + D[j] + V[j]); } sum1[i] = sum1[i-1] + U[i] + V[i]; sum2[i] = sum2[i-1] + min(U[i] + V[i], D[i] + E[i]); } for(int i = 1; i <= N; i++) { for(int j = 1; j <= i; j++) tb[i][j] = (ll)1e18; } tb[1][1] = T + C1[1]; for(int i = 1; i <= N; i++) { for(int j = 1; j < i; j++) { upd(tb[i+1][j], tb[i][j] - C3[i] + min(C1[i], C2[i]) + C3[i+1] + 2 * T); upd(tb[i+1][i+1], tb[i][j] + C1[i+1] + T * (i-j+1)); } { // T[i][i] upd(tb[i+1][i+1], tb[i][i] + C1[i+1] + T); upd(tb[i+1][i], tb[i][i] - C1[i] + C3[i+1] + C4[i] + 2*T); } } ll ans = (ll)1e18; for(int i = 1; i <= N; i++) { for(int j = 1; j <= i; j++) { ll val = tb[i][j] + sum1[N] - sum1[i] + T * (N+1 - j); ans = min(ans, val); } } printf("%lld\n", ans); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...