Submission #31956

#	Time	Username	Problem	Language	Result	Execution time	Memory
31956		minhtung0404	도장 모으기 (JOI14_stamps)	C++14	100 / 100	73 ms	72748 KiB

stamps

#include<bits/stdc++.h>
const long long N = 3005;
const long long inf = 1e18;
using namespace std;

long long n, t, u[N][2], d[N][2];
long long l[N][2], r[N][2], dp[N][N];

int main(){
    scanf("%ld %ld", &n, &t);
    for (long long i = 1; i <= n; i++) scanf("%ld %ld %ld %ld", &u[i][0], &u[i][1], &d[i][0], &d[i][1]);
    for (long long i = 1; i <= n; i++){
        r[i][0] = u[i][1]; l[i][0] = u[i][0];
        r[i][1] = d[i][1]; l[i][1] = d[i][0];
        for (long long j = 1; j < i; j++){
            r[i][0] = min(r[i][0], d[i][1]+2*t*(i-j)+d[j][0]+u[j][1]);
            l[i][1] = min(l[i][1], 2*t*(i-j)+d[j][0]+u[j][1]+u[i][0]);
        }
        for (long long j = i+1; j <= n; j++){
            r[i][1] = min(r[i][1], u[i][1]+2*t*(j-i)+u[j][0]+d[j][1]);
            l[i][0] = min(l[i][0], 2*t*(j-i)+u[j][0]+d[j][1]+d[i][0]);
        }
        r[i][0] -= t*i; l[i][0] += t*i;
        r[i][1] += t*i; l[i][1] -= t*i;
    }
    for (long long i = 0; i <= n; i++) for (long long j = 0; j <= n; j++) dp[i][j] = inf;
    dp[0][1] = 0;
    for (long long i = 0; i < n; i++){
        for (long long j = 1; j <= n; j++){
            if (dp[i][j] == inf) continue;
            if (j > 1)  dp[i+1][j]   = min(dp[i+1][j]  , dp[i][j]+l[i+1][1]+r[i+1][1]);
            if (j > 0)  dp[i+1][j]   = min(dp[i+1][j]  , dp[i][j]+l[i+1][0]+r[i+1][0]);
            if (j > 1)  dp[i+1][j-1] = min(dp[i+1][j-1], dp[i][j]+l[i+1][0]+r[i+1][1]);
            if (j < n)  dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+l[i+1][1]+r[i+1][0]);
        }
    }
    printf("%ld", dp[n][1]+(n+1)*t);
}

Compilation message (stderr)

stamps.cpp: In function 'int main()':
stamps.cpp:10:28: warning: format '%ld' expects argument of type 'long int*', but argument 2 has type 'long long int*' [-Wformat=]
     scanf("%ld %ld", &n, &t);
                            ^
stamps.cpp:10:28: warning: format '%ld' expects argument of type 'long int*', but argument 3 has type 'long long int*' [-Wformat=]
stamps.cpp:11:103: warning: format '%ld' expects argument of type 'long int*', but argument 2 has type 'long long int*' [-Wformat=]
     for (long long i = 1; i <= n; i++) scanf("%ld %ld %ld %ld", &u[i][0], &u[i][1], &d[i][0], &d[i][1]);
                                                                                                       ^
stamps.cpp:11:103: warning: format '%ld' expects argument of type 'long int*', but argument 3 has type 'long long int*' [-Wformat=]
stamps.cpp:11:103: warning: format '%ld' expects argument of type 'long int*', but argument 4 has type 'long long int*' [-Wformat=]
stamps.cpp:11:103: warning: format '%ld' expects argument of type 'long int*', but argument 5 has type 'long long int*' [-Wformat=]
stamps.cpp:37:35: warning: format '%ld' expects argument of type 'long int', but argument 2 has type 'long long int' [-Wformat=]
     printf("%ld", dp[n][1]+(n+1)*t);
                                   ^
stamps.cpp:10:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%ld %ld", &n, &t);
                             ^
stamps.cpp:11:104: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (long long i = 1; i <= n; i++) scanf("%ld %ld %ld %ld", &u[i][0], &u[i][1], &d[i][0], &d[i][1]);
                                                                                                        ^

• Subtask 1: 10 / 10
• Subtask 2: 75 / 75
• Subtask 3: 15 / 15