oj.uz

Submission #62811

# Submission time Handle Problem Language Result Execution time Memory
62811 2018-07-30T07:09:37 Z gusfring Sparklers (JOI17_sparklers) C++14
30 / 100
 4 ms 928 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;

const int MAXN = 205;
 
int n, k;
ll t;
ll x[MAXN];
bool dp[MAXN][MAXN];
 
bool check(ll s){
	memset(dp, 0, sizeof dp);
	dp[k][k] = 1;
	for(int len=2; len<=n; ++len){
		for(int l=0; l<n; ++l){
			int r = l + len - 1;
			if (r >= n) break;
			dp[l][r] = ((dp[l + 1][r] || dp[l][r - 1]) && (x[r] - x[l]) <= 2 * s * (r - l) * t);
		}
	}
	return dp[0][n - 1];
}
 
int main(){
	scanf("%d %d %d", &n, &k, &t);
	k--;
	for(int i=0; i<n; ++i) scanf("%d", &x[i]);
	ll lo = -1, hi = (x[n - 1] + t) / t;
	while (hi - lo > 1) {
		ll mid = (lo + hi) / 2;
		if(check(mid)) hi = mid;
		else lo = mid;
	}
	printf("%lld\n", hi);
	return 0;
}

Compilation message

sparklers.cpp: In function 'int main()':
sparklers.cpp:28:30: warning: format '%d' expects argument of type 'int*', but argument 4 has type 'll* {aka long long int*}' [-Wformat=]
  scanf("%d %d %d", &n, &k, &t);
                            ~~^
sparklers.cpp:30:42: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll* {aka long long int*}' [-Wformat=]
  for(int i=0; i<n; ++i) scanf("%d", &x[i]);
                                     ~~~~~^
sparklers.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &k, &t);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:30:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=0; i<n; ++i) scanf("%d", &x[i]);
                         ~~~~~^~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 568 KB Output is correct
3 Correct 3 ms 568 KB Output is correct
4 Correct 3 ms 644 KB Output is correct
5 Correct 3 ms 644 KB Output is correct
6 Correct 3 ms 676 KB Output is correct
7 Correct 3 ms 740 KB Output is correct
8 Correct 3 ms 744 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 3 ms 752 KB Output is correct
11 Correct 3 ms 756 KB Output is correct
12 Correct 3 ms 760 KB Output is correct
13 Correct 3 ms 764 KB Output is correct
14 Correct 3 ms 768 KB Output is correct
15 Correct 2 ms 868 KB Output is correct
16 Correct 3 ms 868 KB Output is correct
17 Correct 4 ms 868 KB Output is correct
18 Correct 3 ms 868 KB Output is correct
19 Correct 3 ms 868 KB Output is correct
20 Correct 3 ms 868 KB Output is correct
21 Correct 4 ms 868 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 568 KB Output is correct
3 Correct 3 ms 568 KB Output is correct
4 Correct 3 ms 644 KB Output is correct
5 Correct 3 ms 644 KB Output is correct
6 Correct 3 ms 676 KB Output is correct
7 Correct 3 ms 740 KB Output is correct
8 Correct 3 ms 744 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 3 ms 752 KB Output is correct
11 Correct 3 ms 756 KB Output is correct
12 Correct 3 ms 760 KB Output is correct
13 Correct 3 ms 764 KB Output is correct
14 Correct 3 ms 768 KB Output is correct
15 Correct 2 ms 868 KB Output is correct
16 Correct 3 ms 868 KB Output is correct
17 Correct 4 ms 868 KB Output is correct
18 Correct 3 ms 868 KB Output is correct
19 Correct 3 ms 868 KB Output is correct
20 Correct 3 ms 868 KB Output is correct
21 Correct 4 ms 868 KB Output is correct
22 Runtime error 4 ms 928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 568 KB Output is correct
3 Correct 3 ms 568 KB Output is correct
4 Correct 3 ms 644 KB Output is correct
5 Correct 3 ms 644 KB Output is correct
6 Correct 3 ms 676 KB Output is correct
7 Correct 3 ms 740 KB Output is correct
8 Correct 3 ms 744 KB Output is correct
9 Correct 3 ms 748 KB Output is correct
10 Correct 3 ms 752 KB Output is correct
11 Correct 3 ms 756 KB Output is correct
12 Correct 3 ms 760 KB Output is correct
13 Correct 3 ms 764 KB Output is correct
14 Correct 3 ms 768 KB Output is correct
15 Correct 2 ms 868 KB Output is correct
16 Correct 3 ms 868 KB Output is correct
17 Correct 4 ms 868 KB Output is correct
18 Correct 3 ms 868 KB Output is correct
19 Correct 3 ms 868 KB Output is correct
20 Correct 3 ms 868 KB Output is correct
21 Correct 4 ms 868 KB Output is correct
22 Runtime error 4 ms 928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Halted 0 ms 0 KB -