oj.uz

Submission #641696

# Submission time Handle Problem Language Result Execution time Memory
641696 2022-09-17T13:06:26 Z Cross_Ratio 도장 모으기 (JOI14_stamps) C++14
85 / 100
 122 ms 262144 KB 
#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;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 724 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 580 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 712 KB Output is correct
11 Correct 1 ms 724 KB Output is correct
12 Correct 1 ms 724 KB Output is correct
13 Correct 1 ms 724 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2388 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 2628 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 1 ms 1620 KB Output is correct
7 Correct 1 ms 2388 KB Output is correct
8 Correct 2 ms 2516 KB Output is correct
9 Correct 2 ms 2644 KB Output is correct
10 Correct 1 ms 2644 KB Output is correct
11 Correct 2 ms 2644 KB Output is correct
12 Correct 2 ms 2644 KB Output is correct
13 Correct 2 ms 2628 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 2 ms 2644 KB Output is correct
16 Correct 2 ms 2644 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 122 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -