oj.uz

Submission #584890

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

int n;
long long t;
long long dp[3002];
long long u[3002];
long long v[3002];
long long d[3002];
long long e[3002];
long long dist[3003][3003];
const long long INF=1e15;

long long f(int l,int r) {
    if (l>r) {
        return 0;
    }
    long long ret=0;
    for(int i=l;i<=r;i++) {
        //printf("%d\n",i);
        ret+=min(u[i]+v[i],dist[3*i][3*i+1]+dist[3*i+1][3*i+2]+dist[3*i+2][3*i]);
    }
    return ret;
}

long long g(int l,int r) {
    if (l>r) {
        return 0;
    }
    long long ret=0;
    for(int i=l;i<=r;i++) {
        //printf("%d\n",i);
        ret+=min({u[i]+v[i],dist[3*i][3*i+1]+dist[3*i+1][3*i+2]+dist[3*i+2][3*i],d[i]+e[i],dist[3*i+2][3*i+1]+dist[3*i+1][3*i]+dist[3*i][3*i+2]});
    }
    return ret;
}

int main(void) {
    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=0;i<=3*n+5;i++) {
        for(int j=0;j<=3*n+5;j++){
            dist[i][j]=INF;
            if (i==j){
                dist[i][j]=0;
                continue;
            }
        }
    }
    for(int i=0;i<=n+1;i++) {
        if (i<=n) {
            dist[3*i][3*i+3]=t;
        }
        if (i>0) {
            dist[3*i+2][3*i-1]=t;
        }
        if (i==0||i==n+1) {
            continue;
        }
        dist[3*i][3*i+1]=u[i];
        dist[3*i+1][3*i]=v[i];
        dist[3*i+1][3*i+2]=e[i];
        dist[3*i+2][3*i+1]=d[i];
    }
    for(int k=0;k<3*n+6;k++) {
        for(int i=0;i<3*n+6;i++) {
            for(int j=0;j<3*n+6;j++) {
                dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }
    //printf("%lld\n",f(4,4));
    for(int i=1;i<=n+1;i++) {
        dp[i]=1e18;
        for(int j=0;j<i;j++) {
            for(int k=j+1;k<i;k++) {
                dp[i]=min(dp[i],dp[j]+f(j+1,k-1)+v[k]+d[k]+g(max(j+1,k+1),i-1)+u[i]+e[i]+(i-j)*t+2*(i-k)*t);
                //printf("%d %d %d %lld\n",i,j,k,dp[j]+f(j+1,k-1)+v[k]+d[k]+g(max(j+1,k+1),i-1)+u[i]+e[i]+(i-j)*t+2*(i-k)*t);
                //printf(".%d %lld\n",i,dp[i]);
            }
            dp[i]=min(dp[i],dp[j]+f(j+1,i==n+1?n:i)+(i-j)*t);
            //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]);
        }
        //printf("%lld\n",dp[i]);
    }
    printf("%lld",dp[n+1]);
}

Compilation message

stamps.cpp: In function 'int main()':
stamps.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |     scanf("%d %lld",&n,&t);
      |     ~~~~~^~~~~~~~~~~~~~~~~
stamps.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         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 Incorrect 0 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 2068 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 52 ms 2284 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Incorrect 2 ms 724 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 108 ms 143820 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -