oj.uz

Submission #103048

# Submission time Handle Problem Language Result Execution time Memory
103048 2019-03-28T22:26:38 Z luciocf Pinball (JOI14_pinball) C++14
51 / 100
 8 ms 640 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e3+10;
const long long inf = 2e18+10;

typedef long long ll;

int l[maxn], r[maxn], p[maxn], d[maxn];

ll dp[2][maxn];

int main(void)
{
	int n, m;
	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++)
	{
		scanf("%d %d %d %d", &l[i], &r[i], &p[i], &d[i]);

		dp[0][i] = dp[1][i] = inf;
	}

	for (int i = 1; i <= n; i++)
	{
		if (l[i] == 1) dp[0][i] = d[i];

		for (int j = i-1; j >= 1; j--)
			if (p[j] >= l[i] && p[j] <= r[i])
				dp[0][i] = min(dp[0][i], 1ll*d[i]+dp[0][j]);
	}

	for (int i = 1; i <= n; i++)
	{
		if (r[i] == m) dp[1][i] = d[i];

		for (int j = i-1; j >= 1; j--)
			if (p[j] >= l[i] && p[j] <= r[i])
				dp[1][i] = min(dp[1][i], 1ll*d[i]+dp[1][j]);
	}

	ll ans = inf;
	for (int i = 1; i <= n; i++)
		if (dp[0][i] != inf && dp[1][i] != inf)
			ans = min(ans, dp[0][i]+dp[1][i]-1ll*d[i]);

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

Compilation message

pinball.cpp: In function 'int main()':
pinball.cpp:17:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~
pinball.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d", &l[i], &r[i], &p[i], &d[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 3 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 3 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 3 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 3 ms 380 KB Output is correct
10 Correct 3 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 3 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 3 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 3 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 3 ms 380 KB Output is correct
10 Correct 3 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 3 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 3 ms 384 KB Output is correct
17 Correct 7 ms 384 KB Output is correct
18 Correct 7 ms 384 KB Output is correct
19 Correct 8 ms 384 KB Output is correct
20 Correct 7 ms 384 KB Output is correct
21 Correct 3 ms 384 KB Output is correct
22 Correct 6 ms 384 KB Output is correct
23 Correct 4 ms 384 KB Output is correct
24 Correct 7 ms 512 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 3 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 3 ms 380 KB Output is correct
10 Correct 3 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 3 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 3 ms 384 KB Output is correct
17 Correct 7 ms 384 KB Output is correct
18 Correct 7 ms 384 KB Output is correct
19 Correct 8 ms 384 KB Output is correct
20 Correct 7 ms 384 KB Output is correct
21 Correct 3 ms 384 KB Output is correct
22 Correct 6 ms 384 KB Output is correct
23 Correct 4 ms 384 KB Output is correct
24 Correct 7 ms 512 KB Output is correct
25 Execution timed out 5 ms 640 KB Time limit exceeded (wall clock)
26 Halted 0 ms 0 KB -