oj.uz

Submission #27800

# Submission time Handle Problem Language Result Execution time Memory
27800 2017-07-14T06:31:56 Z 서규호(#1160) Sparklers (JOI17_sparklers) C++14
0 / 100
 0 ms 36136 KB 
#include <bits/stdc++.h>

#define lld long long
#define pii pair<int,int>
#define pll pair<lld,lld>
#define pb push_back
#define next nextt
#define left leftt
#define right rightt
#define Inf 1000000000
#define Linf 1000000000000000000LL
#define Mod 1000000007

using namespace std;

int N,M,ans; lld T;
lld a[100002];
lld s[1002][1002][2],e[1002][1002][2];
bool d[1002][1002][2];

bool can(lld X){
	X *= T; X %= Mod;
	for(int i=1; i<=M; i++) for(int j=M; j<=N; j++) for(int k=0; k<2; k++){
		d[i][j][k] = false;
		s[i][j][k] = Mod; e[i][j][k] = 0;
	}
	d[M][M][0] = true; s[M][M][0] = e[M][M][0] = a[M];
	for(int i=1; i<=N-1; i++){
		for(int j=max(1,M-i); j+i<=N; j++){
			for(int k=0; k<2; k++){
				int x,y;
				lld now,cnt = i;
				if(k == 0) now = a[j];
				else now = a[j+i];
				x = j+1; y = j+i;
				for(int t=0; t<2; t++){
					if(!d[x][y][t]) continue;
					if(max(s[x][y][t]-X,now-cnt*X) <= min(e[x][y][t]+X,now+cnt*X)){
						d[j][j+i][k] = true;
						s[j][j+i][k] = min(s[j][j+i][k],max(s[x][y][t]-X,now-cnt*X));
						e[j][j+i][k] = max(e[j][j+i][k],min(e[x][y][t]+X,now+cnt*X));
					}
				}
				x = j; y = j+i-1;
				for(int t=0; t<2; t++){
					if(!d[x][y][t]) continue;
					if(max(s[x][y][t]-X,now-cnt*X) <= min(e[x][y][t]+X,now+cnt*X)){
						d[j][j+i][k] = true;
						s[j][j+i][k] = min(s[j][j+i][k],max(s[x][y][t]-X,now-cnt*X));
						e[j][j+i][k] = max(e[j][j+i][k],min(e[x][y][t]+X,now+cnt*X));
					}
				}
			}
		}
	}

	return (d[1][N][0]|d[1][N][1]);
}

int main(){
	scanf("%d %d %lld",&N,&M,&T);
	for(int i=1; i<=N; i++){
		scanf("%lld",&a[i]);
	}
	int l,r;
	l = 0; r = a[N];
	while(l <= r){
		int m = (l+r)/2;
		if(can(m)){
			ans = m;
			r = m-1;
		}else l = m+1;
	}
	printf("%d\n",ans);

	return 0;
}

Compilation message

sparklers.cpp: In function 'int main()':
sparklers.cpp:61:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %lld",&N,&M,&T);
                              ^
sparklers.cpp:63:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]);
                      ^

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 36136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 36136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 36136 KB Output isn't correct
2 Halted 0 ms 0 KB -