oj.uz

Submission #31956

# Submission time Handle Problem Language Result Execution time Memory
31956 2017-09-18T15:44:20 Z minhtung0404 도장 모으기 (JOI14_stamps) C++14
100 / 100
 73 ms 72748 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 72748 KB Output is correct
2 Correct 0 ms 72748 KB Output is correct
3 Correct 0 ms 72748 KB Output is correct
4 Correct 0 ms 72748 KB Output is correct
5 Correct 0 ms 72748 KB Output is correct
6 Correct 0 ms 72748 KB Output is correct
7 Correct 0 ms 72748 KB Output is correct
8 Correct 0 ms 72748 KB Output is correct
9 Correct 0 ms 72748 KB Output is correct
10 Correct 0 ms 72748 KB Output is correct
11 Correct 0 ms 72748 KB Output is correct
12 Correct 0 ms 72748 KB Output is correct
13 Correct 0 ms 72748 KB Output is correct

Subtask #2
75.0 / 75.0

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

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 72748 KB Output is correct
2 Correct 0 ms 72748 KB Output is correct
3 Correct 63 ms 72748 KB Output is correct
4 Correct 46 ms 72748 KB Output is correct
5 Correct 53 ms 72748 KB Output is correct
6 Correct 16 ms 72748 KB Output is correct
7 Correct 9 ms 72748 KB Output is correct
8 Correct 63 ms 72748 KB Output is correct
9 Correct 56 ms 72748 KB Output is correct
10 Correct 59 ms 72748 KB Output is correct
11 Correct 66 ms 72748 KB Output is correct
12 Correct 59 ms 72748 KB Output is correct
13 Correct 63 ms 72748 KB Output is correct
14 Correct 73 ms 72748 KB Output is correct
15 Correct 59 ms 72748 KB Output is correct
16 Correct 66 ms 72748 KB Output is correct
17 Correct 66 ms 72748 KB Output is correct