oj.uz

Submission #585047

# Submission time Handle Problem Language Result Execution time Memory
585047 2022-06-28T09:25:06 Z 조영욱(#8382) 도장 모으기 (JOI14_stamps) C++14
85 / 100
 1000 ms 840 KB 
#include <bits/stdc++.h>
using namespace std;

int n;
long long t;
long long dp[100005];
long long u[100005];
long long v[100005];
long long d[100005];
long long e[100005];
const long long INF=2e9;

const int sz=8192;

struct Seg {
    long long seg[sz*2];
    void init() {
        for(int i=1;i<sz*2;i++) {
            seg[i]=INF;
        }
    }
    long long sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
        if (r<nodel||l>noder) {
            return INF;
        }
        if (l<=nodel&&noder<=r) {
            return seg[node];
        }
        int mid=(nodel+noder)/2;
        return min(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,mid+1,noder));
    }
    void update(int i,long long val) {
        i+=sz;
        seg[i]=val;
        while (i>1) {
            i/=2;
            seg[i]=min(seg[i*2],seg[i*2+1]);
        }
    }
};

long long f[100005];
long long g[100005];

Seg seg1;
Seg seg2;

int main(void) {
    scanf("%d %lld",&n,&t);
    assert(n<=3000);
    seg1.init();
    seg2.init();
    for(int i=1;i<=n;i++) {
        scanf("%lld %lld %lld %lld",&u[i],&v[i],&d[i],&e[i]);
    }
    for(int i=1;i<=n;i++) {
        f[i]=f[i-1]+u[i]+v[i];
        g[i]=g[i-1]+min(u[i]+v[i],d[i]+e[i]);
    }
    for(int i=1;i<=n;i++) {
        seg1.update(i,v[i]+d[i]-2*t*i);
        seg2.update(i,f[i-1]+v[i]+d[i]-g[i]-2*t*i);
    }
    for(int i=1;i<=n+1;i++) {
        dp[i]=INF;
        for(int j=0;j<i;j++) {
            if (i==n+1) continue;
            dp[i]=min(dp[i],dp[j]-f[j]+g[i-1]+u[i]+e[i]+(i-j)*t+2*i*t+seg2.sum(j+1,i-1));
            dp[i]=min(dp[i],dp[j]+g[i-1]-g[j]+u[i]+e[i]+(i-j)*t+2*i*t+seg1.sum(1,j));
            //printf("%d %d %lld\n",i,j,dp[j]+f(j+1,i==n+1?n:i)+(i-j)*t);
            //printf(".%d %lld\n",i,dp[i]);
        }
        dp[i]=min(dp[i],dp[i-1]+u[i]+v[i]+t);
        //printf("%lld\n",dp[i]);
    }
    long long ret=dp[n+1];
    reverse(u+1,u+n+1);
    reverse(v+1,v+n+1);
    reverse(d+1,d+n+1);
    reverse(e+1,e+n+1);
    for(int i=1;i<=n;i++) {
        swap(u[i],v[i]);
        swap(d[i],e[i]);
        f[i]=f[i-1]+u[i]+v[i];
        g[i]=g[i-1]+min(u[i]+v[i],d[i]+e[i]);
    }
    for(int i=1;i<=n;i++) {
        seg1.update(i,v[i]+d[i]-2*t*i);
        seg2.update(i,f[i-1]+v[i]+d[i]-g[i]-2*t*i);
    }
    for(int i=1;i<=n+1;i++) {
        dp[i]=INF;
        for(int j=0;j<i;j++) {
            if (i==n+1) continue;
            dp[i]=min(dp[i],dp[j]-f[j]+g[i-1]+u[i]+e[i]+(i-j)*t+2*i*t+seg2.sum(j+1,i-1));
            dp[i]=min(dp[i],dp[j]+g[i-1]-g[j]+u[i]+e[i]+(i-j)*t+2*i*t+seg1.sum(1,j));
            //printf("%d %d %lld\n",i,j,dp[j]+f(j+1,i==n+1?n:i)+(i-j)*t);
            //printf(".%d %lld\n",i,dp[i]);
        }
        dp[i]=min(dp[i],dp[i-1]+u[i]+v[i]+t);
        //printf("%lld\n",dp[i]);
    }
    ret=min(ret,dp[n+1]);
    printf("%lld",ret);
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 520 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 468 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 596 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 468 KB Output is correct

Subtask #2
75.0 / 75.0

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

Subtask #3
0 / 15.0

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