Submission #681671

#TimeUsernameProblemLanguageResultExecution timeMemory
681671Cross_Ratio도장 모으기 (JOI14_stamps)C++14
85 / 100
137 ms262144 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll INF = 1e18; ll U[3005]; ll V[3005]; ll D[3005]; ll E[3005]; ll C[3005][3005]; ll DP[3005][3005]; ll D2[3005][3005]; ll L[3005][3005]; ll R[3005][3005]; ll cL(int c) { return U[c] + V[c]; } ll cR(int c) { return D[c] + E[c]; } ll cost(int c) { return min(cL(c), cR(c)); } ll LR(int c) { return U[c] + E[c]; } ll RL(int c) { return D[c] + V[c]; } ll val1[3005]; ll val2[3005]; ll val3[3005]; signed main() { cin.sync_with_stdio(false); cin.tie(0); cout.tie(0); ll N; cin >> N; ll T; cin >> T; ll i, j; for(i=1;i<=N;i++) cin >> U[i] >> V[i] >> D[i] >> E[i]; for(i=1;i<=N;i++) { for(j=i;j<=N;j++) { C[i][j] = C[i][j-1] + cost(j); L[i][j] = L[i][j-1] + cL(j); R[i][j] = R[i][j-1] + cR(j); } } for(i=0;i<=N+1;i++) { for(j=0;j<=N+1;j++) DP[i][j] = D2[i][j] = INF; } for(i=0;i<=N+1;i++) val1[i] = val2[i] = val3[i] = INF; DP[0][0] = D2[0][0] = 0; DP[1][0] = D2[1][0] = T + cL(1); for(i=1;i<=N;i++) { ll mi = INF; for(j=1;j<=i-1;j++) { //for(int i2 = i-1; i2 >= 1; i2--) { //if(i2 <= j) { DP[i][j] = min(DP[i][j], val1[j] + T*i+2*T*(i-j)+L[1][j-1]+RL(j)+LR(i)+C[j+1][i-1]); if(j==1) { DP[i][j] = min(DP[i][j],DP[1][0]+T*(i-1)+2*T*(i-j)+L[2][j-1]+RL(j)+LR(i)+C[j+1][i-1]-cL(1)); } /* DP[i][j] = min(DP[i][j], DP[i2][i2-1] + T * (i - i2) + 2 * T * (i - j) + L[i2+1][j-1] + RL(j) + LR(i) + C[j+1][i-1] +(i2==1&&j==1?-cL(1):0));*/ //} //else { if(j!=i-1) DP[i][j] = min(DP[i][j], val2[j]+T*i+2*T*(i-j)+RL(j)+LR(i)+C[1][i-1]-cost(j)); DP[i][j] = min(DP[i][j], val3[j]+T*i+2*T*(i-j)+RL(j)+LR(i)+C[1][i-1]); /* DP[i][j] = min(DP[i][j], DP[i2][j] + T * (i - i2) + 2 * T * (i - j) + RL(j) + LR(i) + C[i2+1][i-1]);*/ //} //} if(j != 1) DP[i][j] = min(DP[i][j], mi + 2*T*(i-j)+LR(i)+RL(j)-cost(j)); mi = min(mi, DP[i][j]); } for(j=1;j<=i-1;j++) D2[i][j] = DP[i][j]; for(j=1;j+1<=i-1;j++) { D2[i][j+1] = min(D2[i][j+1], D2[i][j]); } val1[i] = min(val1[i-1], D2[i][i-1]-T*i-L[1][i]); for(j=1;j<=i-1;j++) { val2[j] = min(val2[j], D2[i][j-1]-T*i-C[1][i]); } for(j=1;j<=i-1;j++) { val3[j] = min(val3[j], DP[i][j]-T*i-C[1][i]); } } ll ans = T*(N+1) + L[1][N]; for(i=1;i<=N;i++) { for(j=1;j<=i-1;j++) { //cout << i << " " << j << " : " << DP[i][j] << '\n'; ans = min(ans, DP[i][j] + T*(N+1-i) + L[i+1][N]); } } cout << ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...