oj.uz

Submission #117610

# Submission time Handle Problem Language Result Execution time Memory
117610 2019-06-16T18:57:22 Z evpipis Pinball (JOI14_pinball) C++17
51 / 100
 1000 ms 2156 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int len = 1e5+5;
const ll inf = 1e18;
int lef[len], rig[len], pos[len], cost[len];
ll dp[len][3];

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d %d %d %d", &lef[i], &rig[i], &pos[i], &cost[i]);

    ll ans = inf;
    for (int i = 1; i <= n; i++){
        ll d0 = inf, d1 = inf, d2 = inf;
        if (lef[i] == 1 && rig[i] == m)
            d0 = d1 = d2 = cost[i];
        else if (lef[i] == 1)
            d0 = cost[i];
        else if (rig[i] == m)
            d1 = cost[i];

        for (int j = 1; j < i; j++){
            if (pos[j] < lef[i] || rig[i] < pos[j])
                continue;
            d0 = min(d0, cost[i]+dp[j][0]);
            d1 = min(d1, cost[i]+dp[j][1]);
        }
        d2 = min(d2, d0+d1-cost[i]);

        dp[i][0] = d0;
        dp[i][1] = d1;
        dp[i][2] = d2;

        ans = min(ans, d2);

        //printf("i = %d, d0 = %lld, d1 = %lld, d2 = %lld\n", i, d0, d1, d2);
    }

    if (ans == inf)
        printf("-1\n");
    else
        printf("%lld", ans);
    return 0;
}

Compilation message

pinball.cpp: In function 'int main()':
pinball.cpp:12:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
pinball.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d %d", &lef[i], &rig[i], &pos[i], &cost[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 3 ms 384 KB Output is correct
22 Correct 4 ms 384 KB Output is correct
23 Correct 3 ms 384 KB Output is correct
24 Correct 4 ms 384 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 3 ms 384 KB Output is correct
22 Correct 4 ms 384 KB Output is correct
23 Correct 3 ms 384 KB Output is correct
24 Correct 4 ms 384 KB Output is correct
25 Correct 215 ms 1300 KB Output is correct
26 Execution timed out 1077 ms 2156 KB Time limit exceeded
27 Halted 0 ms 0 KB -