oj.uz

Submission #584977

# Submission time Handle Problem Language Result Execution time Memory
584977 2022-06-28T08:01:50 Z 조영욱(#8382) 도장 모으기 (JOI14_stamps) C++14
0 / 100
 1 ms 980 KB 
#include <bits/stdc++.h>
using namespace std;

int n;
long long t;
long long dp[3005];
long long u[3005];
long long v[3005];
long long d[3005];
long long e[3005];
const long long INF=1e18;

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[3005];
long long g[3005];

Seg seg1;
Seg seg2;

int main(void) {
    seg1.init();
    seg2.init();
    scanf("%d %lld",&n,&t);
    assert(n>3000);
    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]);
    }
    printf("%lld",dp[n+1]);
}

Compilation message

stamps.cpp: In function 'int main()':
stamps.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 980 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 980 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 980 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -