oj.uz

Submission #584882

# Submission time Handle Problem Language Result Execution time Memory
584882 2022-06-28T06:11:17 Z 박상훈(#8379) 도장 모으기 (JOI14_stamps) C++14
10 / 100
 1000 ms 183180 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
const ll INF = 4e18;
struct Seg{
    ll tree[6060];
    int sz;
    void init(int n){
        sz = n;
        fill(tree, tree+sz*2, INF);
    }
    void update(int p, ll x){
        p += sz;
        for (tree[p]=min(tree[p], x);p>1;p>>=1) tree[p>>1] = min(tree[p], tree[p^1]);
    }
    ll query(int l, int r){
        r++;
        ll ret = INF;
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1) ret = min(ret, tree[l++]);
            if (r&1) ret = min(ret, tree[--r]);
        }
        return ret;
    }
}M1, M3[3030];
struct Seg2{
    ll tree[6060];
    int sz;
    void init(int n){
        sz = n;
        fill(tree, tree+sz*2, INF);
    }
    ll query(int p){
        p += sz;
        ll ret = tree[p];
        for (p>>=1;p;p>>=1) ret = min(ret, tree[p]);
        return ret;
    }
    void update(int l, int r, ll x){
        r++;
        for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
            if (l&1){
                tree[l] = min(tree[l], x);
                l++;
            }
            if (r&1){
                --r;
                tree[r] = min(tree[r], x);
            }
        }
    }
}M2;
ll dp[3030][3030], cstS[3030], dcstS[3030], UD[3030], DU[3030], T;

ll cst(int l, int r){
    if (r<l) return 0;
    return cstS[r] - cstS[l-1];
}

ll dcst(int l, int r){
    if (r<l) return 0;
    return cstS[r] - cstS[l-1] - (dcstS[r] - dcstS[l-1]);
}

ll Tij(int r, int l){
    return T*(r-l)*2 + UD[r] + DU[l];
}

int main(){
    int n;
    scanf("%d %lld", &n, &T);
    for (int i=1;i<=n;i++){
        int u, v, d, e;
        scanf("%d %d %d %d", &u, &v, &d, &e);
        UD[i] = u + e;
        DU[i] = d + v;
        int uu = u+v, dd = d+e;
        cstS[i] = cstS[i-1] + uu;
        dcstS[i] = dcstS[i-1] + max(uu-dd, 0);

        M3[i].init(n+1);
    }

    M1.init(n+1);
    M2.init(n+1);

    ll ans = T*(n+1) + cst(1, n);

    for (int i=1;i<=n;i++){
        for (int j=1;j<i;j++){
            dp[i][j] = T*i + cst(1, j-1) + dcst(j+1, i-1) + Tij(i, j);

            ///case 1. k<=j
            dp[i][j] = min(dp[i][j], M1.query(1, j) + T*i - cst(j, n) + dcst(j+1, i-1) + Tij(i, j));

            ///case 2. k>j, l<j
            dp[i][j] = min(dp[i][j], M2.query(j) + T*i - dcst(i, n) + Tij(i, j) - dcst(j, j));

            ///case 3. k>j, l=j
            dp[i][j] = min(dp[i][j], M3[j].query(j+1, i-1) + T*i - dcst(i, n) + Tij(i, j));

            ///update
            M1.update(i, dp[i][j] - T*i + cst(i+1, n));
            M2.update(j+1, i-1, dp[i][j] - T*i + dcst(i+1, n));
            M3[j].update(i, dp[i][j] - T*i + dcst(i+1, n));

            ans = min(ans, dp[i][j] + T*(n+1-i) + cst(i+1, n));

            /*
            for (int k=1;k<=j;k++){
                for (int l=1;l<k;l++){
                    ///case 1. k<=j
                    dp[i][j] = min(dp[i][j], dp[k][l] + T*(i-k) + cst(k+1, j-1) + dcst(j+1, i-1) + Tij(i, j));
                }
            }

            for (int k=j+1;k<=i;k++){
                for (int l=1;l<j;l++){
                    ///case 2. k>j, l<j
                    dp[i][j] = min(dp[i][j], dp[k][l] + T*(i-k) + dcst(k+1, i-1) + Tij(i, j) - dcst(j, j));
                }

                if (k==i) break;
                ///case 3.k>j, l=j
                int l = j;
                dp[i][j] = min(dp[i][j], dp[k][l] + T*(i-k) + dcst(k+1, i-1) + Tij(i, j));
            }*/


        }
    }

    //printf("%lld\n", dp[2][1]);
    printf("%lld\n", ans);
    return 0;
}

Compilation message

stamps.cpp: In function 'int main()':
stamps.cpp:72:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |     scanf("%d %lld", &n, &T);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
stamps.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         scanf("%d %d %d %d", &u, &v, &d, &e);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 2 ms 1364 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 852 KB Output is correct
7 Correct 2 ms 1108 KB Output is correct
8 Correct 1 ms 1236 KB Output is correct
9 Correct 1 ms 1236 KB Output is correct
10 Correct 2 ms 1236 KB Output is correct
11 Correct 2 ms 1236 KB Output is correct
12 Correct 2 ms 1236 KB Output is correct
13 Correct 1 ms 1364 KB Output is correct
14 Correct 2 ms 1236 KB Output is correct
15 Correct 1 ms 1236 KB Output is correct
16 Incorrect 1 ms 1364 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1097 ms 183180 KB Time limit exceeded
2 Halted 0 ms 0 KB -