oj.uz

답안 #428443

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
428443 2021-06-15T11:53:02 Z errorgorn Sparklers (JOI17_sparklers) C++17
0 / 100
 73 ms 16120 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second
#define endl '\n'

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
#define lb lower_bound
#define ub upper_bound

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,k,t;
ll arr[100005];

ii memo[1005][1005];

bool can(ll i){
	rep(x,0,1005) rep(y,0,1005) memo[x][y]=ii(1e10,-1e10);
	
	memo[k][k]=ii(arr[k]-i,arr[k]+i);
	
	rep(x,0,n-1){
		rep(y,1,n-x+1){
			int l=y,r=y+x;
			
			ii temp=memo[l][r];
			temp.fi=max(temp.fi,arr[l-1]-(x+1)*i);
			temp.se=min(temp.se,arr[l-1]+(x+1)*i);
			if (temp.fi<=temp.se){
				memo[l-1][r].fi=min(memo[l-1][r].fi,temp.fi-i);
				memo[l-1][r].se=max(memo[l-1][r].se,temp.se+i);
			}
			
			temp=memo[l][r];
			temp.fi=max(temp.fi,arr[r+1]-(x+1)*i);
			temp.se=min(temp.se,arr[r+1]+(x+1)*i);
			if (temp.fi<=temp.se){
				memo[l][r+1].fi=min(memo[l][r+1].fi,temp.fi-i);
				memo[l][r+1].se=max(memo[l][r+1].se,temp.se+i);
			}
		}
	}
	
	return memo[1][n].fi<=memo[1][n].se;
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin.sync_with_stdio(false);
	
	cin>>n>>k>>t;
	
	rep(x,1,n+1) cin>>arr[x];
	
	ll lo=0,hi=1e9,mi;
	while (hi-lo>1){
		mi=hi+lo>>1;
		
		if (can(mi)) hi=mi;
		else lo=mi;
	}
	
	cout<<(hi+t-1)/t<<endl;
}

Compilation message

sparklers.cpp: In function 'int main()':
sparklers.cpp:69:8: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |   mi=hi+lo>>1;
      |      ~~^~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 16076 KB Output is correct
2 Correct 70 ms 16052 KB Output is correct
3 Correct 71 ms 16116 KB Output is correct
4 Correct 68 ms 16116 KB Output is correct
5 Correct 66 ms 16076 KB Output is correct
6 Correct 65 ms 16076 KB Output is correct
7 Correct 66 ms 16076 KB Output is correct
8 Correct 73 ms 16116 KB Output is correct
9 Correct 70 ms 16116 KB Output is correct
10 Correct 69 ms 16116 KB Output is correct
11 Correct 69 ms 16116 KB Output is correct
12 Correct 69 ms 16120 KB Output is correct
13 Correct 68 ms 16076 KB Output is correct
14 Correct 67 ms 16076 KB Output is correct
15 Correct 68 ms 16120 KB Output is correct
16 Correct 70 ms 16084 KB Output is correct
17 Correct 68 ms 16116 KB Output is correct
18 Correct 64 ms 16116 KB Output is correct
19 Incorrect 67 ms 16112 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 16076 KB Output is correct
2 Correct 70 ms 16052 KB Output is correct
3 Correct 71 ms 16116 KB Output is correct
4 Correct 68 ms 16116 KB Output is correct
5 Correct 66 ms 16076 KB Output is correct
6 Correct 65 ms 16076 KB Output is correct
7 Correct 66 ms 16076 KB Output is correct
8 Correct 73 ms 16116 KB Output is correct
9 Correct 70 ms 16116 KB Output is correct
10 Correct 69 ms 16116 KB Output is correct
11 Correct 69 ms 16116 KB Output is correct
12 Correct 69 ms 16120 KB Output is correct
13 Correct 68 ms 16076 KB Output is correct
14 Correct 67 ms 16076 KB Output is correct
15 Correct 68 ms 16120 KB Output is correct
16 Correct 70 ms 16084 KB Output is correct
17 Correct 68 ms 16116 KB Output is correct
18 Correct 64 ms 16116 KB Output is correct
19 Incorrect 67 ms 16112 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Correct 72 ms 16076 KB Output is correct
2 Correct 70 ms 16052 KB Output is correct
3 Correct 71 ms 16116 KB Output is correct
4 Correct 68 ms 16116 KB Output is correct
5 Correct 66 ms 16076 KB Output is correct
6 Correct 65 ms 16076 KB Output is correct
7 Correct 66 ms 16076 KB Output is correct
8 Correct 73 ms 16116 KB Output is correct
9 Correct 70 ms 16116 KB Output is correct
10 Correct 69 ms 16116 KB Output is correct
11 Correct 69 ms 16116 KB Output is correct
12 Correct 69 ms 16120 KB Output is correct
13 Correct 68 ms 16076 KB Output is correct
14 Correct 67 ms 16076 KB Output is correct
15 Correct 68 ms 16120 KB Output is correct
16 Correct 70 ms 16084 KB Output is correct
17 Correct 68 ms 16116 KB Output is correct
18 Correct 64 ms 16116 KB Output is correct
19 Incorrect 67 ms 16112 KB Output isn't correct
20 Halted 0 ms 0 KB -