This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |