oj.uz

Submission #27858

# Submission time Handle Problem Language Result Execution time Memory
27858 2017-07-14T08:57:03 Z 상수조아(#1181) Sparklers (JOI17_sparklers) C++11
0 / 100
 0 ms 17060 KB 
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <set>
#include <bitset>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define pb(x) push_back(x)
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define Fi first
#define Se second

int N, K, T;
int X[1010];
pll D[1010][1010];

int Do(int S) {
	if((ll)S * T >= 2e9) return 1;
	for(int i=1;i<=N;i++) for(int j=i;j<=N;j++) D[i][j] = pll(1e18, -1e18);
	D[K][K] = pll(X[K],X[K]);
	for(int i=1;i<N;i++) for(int j=1;j+i<=N;j++) {
		int l = j, r = j + i;
		if(D[l][r-1].Fi <= D[l][r-1].Se) {
			ll rv = D[l][r-1].Se;
			ll lv = D[l][r-1].Fi;
			if(X[r] - rv <= (ll)(r-l+1) * S * T) {
				D[l][r].Fi = min(D[l][r].Fi, max(X[r] - (ll)(r-l) * S * T, lv - (ll)S * T));
				D[l][r].Se = max(D[l][r].Se, rv + (ll)S * T);
			}
		}
		if(D[l+1][r].Fi <= D[l+1][r].Se) {
			ll lv = D[l+1][r].Fi;
			ll rv = D[l+1][r].Se;
			if(lv - X[l] <= (ll)(r-l+1) * S * T) {
				D[l][r].Fi = min(D[l][r].Fi, lv - (ll)S * T);
				D[l][r].Se = max(D[l][r].Se, min(X[l] + (ll)(r-l) * S * T, rv + (ll)S * T));
			}
		}
	}
	return D[1][N].Fi <= D[1][N].Se;
}

int main(){
	scanf("%d%d%d", &N, &K, &T);
	if(N > 1000) return 0;
	for(int i=1;i<=N;i++) scanf("%d", X+i);
	int low = 1, high = 1e9, res = 0;
	while(low <= high) {
		int mid = (low + high) >> 1;
		if(Do(mid)) res = mid, high = mid - 1;
		else low = mid + 1;
	}
	printf("%d\n", res);
	return 0;
};

Compilation message

sparklers.cpp: In function 'int main()':
sparklers.cpp:49:29: 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:51:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=N;i++) scanf("%d", X+i);
                                        ^

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17060 KB Output is correct
2 Correct 0 ms 17060 KB Output is correct
3 Correct 0 ms 17060 KB Output is correct
4 Correct 0 ms 17060 KB Output is correct
5 Correct 0 ms 17060 KB Output is correct
6 Correct 0 ms 17060 KB Output is correct
7 Correct 0 ms 17060 KB Output is correct
8 Correct 0 ms 17060 KB Output is correct
9 Correct 0 ms 17060 KB Output is correct
10 Correct 0 ms 17060 KB Output is correct
11 Correct 0 ms 17060 KB Output is correct
12 Correct 0 ms 17060 KB Output is correct
13 Correct 0 ms 17060 KB Output is correct
14 Correct 0 ms 17060 KB Output is correct
15 Correct 0 ms 17060 KB Output is correct
16 Correct 0 ms 17060 KB Output is correct
17 Correct 0 ms 17060 KB Output is correct
18 Correct 0 ms 17060 KB Output is correct
19 Incorrect 0 ms 17060 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17060 KB Output is correct
2 Correct 0 ms 17060 KB Output is correct
3 Correct 0 ms 17060 KB Output is correct
4 Correct 0 ms 17060 KB Output is correct
5 Correct 0 ms 17060 KB Output is correct
6 Correct 0 ms 17060 KB Output is correct
7 Correct 0 ms 17060 KB Output is correct
8 Correct 0 ms 17060 KB Output is correct
9 Correct 0 ms 17060 KB Output is correct
10 Correct 0 ms 17060 KB Output is correct
11 Correct 0 ms 17060 KB Output is correct
12 Correct 0 ms 17060 KB Output is correct
13 Correct 0 ms 17060 KB Output is correct
14 Correct 0 ms 17060 KB Output is correct
15 Correct 0 ms 17060 KB Output is correct
16 Correct 0 ms 17060 KB Output is correct
17 Correct 0 ms 17060 KB Output is correct
18 Correct 0 ms 17060 KB Output is correct
19 Incorrect 0 ms 17060 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 17060 KB Output is correct
2 Correct 0 ms 17060 KB Output is correct
3 Correct 0 ms 17060 KB Output is correct
4 Correct 0 ms 17060 KB Output is correct
5 Correct 0 ms 17060 KB Output is correct
6 Correct 0 ms 17060 KB Output is correct
7 Correct 0 ms 17060 KB Output is correct
8 Correct 0 ms 17060 KB Output is correct
9 Correct 0 ms 17060 KB Output is correct
10 Correct 0 ms 17060 KB Output is correct
11 Correct 0 ms 17060 KB Output is correct
12 Correct 0 ms 17060 KB Output is correct
13 Correct 0 ms 17060 KB Output is correct
14 Correct 0 ms 17060 KB Output is correct
15 Correct 0 ms 17060 KB Output is correct
16 Correct 0 ms 17060 KB Output is correct
17 Correct 0 ms 17060 KB Output is correct
18 Correct 0 ms 17060 KB Output is correct
19 Incorrect 0 ms 17060 KB Output isn't correct
20 Halted 0 ms 0 KB -