oj.uz

답안 #584970

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
584970 2022-06-28T07:54:44 Z 조영욱(#8382) 도장 모으기 (JOI14_stamps) C++14
85 / 100
 887 ms 684 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=4096;

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);
    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]=1e18;
        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:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%lld %lld %lld %lld",&u[i],&v[i],&d[i],&e[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 468 KB Output is correct
13 Correct 1 ms 340 KB Output is correct

Subtask #2
75.0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 408 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 360 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 887 ms 568 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 841 ms 580 KB Output is correct
4 Correct 655 ms 684 KB Output is correct
5 Correct 521 ms 680 KB Output is correct
6 Incorrect 202 ms 516 KB Output isn't correct
7 Halted 0 ms 0 KB -