| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 581885 |
2022-06-23T07:42:01 Z |
반딧불(#8365) |
Sparklers (JOI17_sparklers) |
C++17 |
|
1 ms |
340 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;
ll t;
ll arr[100002];
ll val[100002];
ll revVal[100002];
void makeVector(vector<pair<ll, ll> > &ret, vector<ll> vec){
ll sum = 0, minSum = 0;
for(auto x: vec){
if(sum>0 && x<0){
ret.push_back(make_pair(-minSum, sum));
sum = minSum = 0;
}
sum += x;
minSum = min(minSum, sum);
}
if(sum || minSum) ret.push_back(make_pair(-minSum, sum));
ret.push_back(make_pair(5e18, -5e18));
}
bool able(ll speed){
speed*=t*2;
if(speed==6){
#ifdef TEST
puts("");
#endif // TEST
}
for(int i=1; i<n; i++) val[i] = revVal[n-i] = speed - (arr[i+1] - arr[i]);
/// ����, ������ �ٵ��
vector<pair<ll, ll> > Avec, Bvec;
makeVector(Avec, vector<ll>(revVal+(n+1-k), revVal+n));
makeVector(Bvec, vector<ll>(val+k, val+n));
ll val = 0;
int a = 0, b = 0;
int al = (int)Avec.size()-1, bl = (int)Bvec.size()-1;
for(int i=0; i<al-2; i++) assert(Avec[i].second >= 0);
for(int i=0; i<bl-2; i++) assert(Bvec[i].second >= 0);
while((a<al && Avec[a].second>=0) || (b<bl && Bvec[b].second>=0)){
if((a<al && Avec[a].second>=0) && (b<bl && Bvec[b].second>=0)
&& Avec[a].first <= val && Bvec[b].first <= val){ /// �� �� ���� �� ����
if(Avec[a].second >= Bvec[b].second) val += Avec[a++].second;
else val += Bvec[b++].second;
}
else if((a<al && Avec[a].second>=0) && Avec[a].first <= val){
val += Avec[a++].second;
}
else if((b<bl && Bvec[b].second>=0) && Bvec[b].first <= val){
val += Bvec[b++].second;
}
else return false;
if(val<0) exit(1);
}
if(a>=al && b>=bl) return true;
else if(a>=al){
while(b<bl){
if(Bvec[b].first > val) return false;
val += Bvec[b++].second;
if(val<0) return false;
}
return true;
}
else if(b>=bl){
while(a<al){
if(Avec[a].first > val) return false;
val += Avec[a++].second;
if(val<0) return false;
}
return true;
}
assert(a==al-1 && b==bl-1);
/// �ϳ��� ���� ����
vector<pair<ll, ll> > vec = {Avec[a], Bvec[b]};
if(val >= vec[0].first && val+vec[0].second >= vec[1].first && val+vec[0].second+vec[1].second >= 0) return true;
if(val >= vec[1].first && val+vec[1].second >= vec[0].first && val+vec[1].second+vec[0].second >= 0) return true;
return false;
}
pair<ll, ll> DP[1002][1002];
ll able2(ll speed){
speed*=t;
for(int i=1; i<=n; i++) for(int j=i; j<=n; j++) DP[i][j].first=1e18, DP[i][j].second=-1e18;
DP[k][k] = make_pair(arr[k], arr[k]);
for(int d=1; d<n; d++){
for(int i=1; i+d<=n; i++){
int j = i+d;
if((arr[j]-speed*d) <= (DP[i][j-1].second+speed)){
DP[i][j].first = min(DP[i][j].first, max(arr[j]-speed*d, DP[i][j-1].first-speed));
DP[i][j].second = max(DP[i][j].second, DP[i][j-1].second+speed);
}
if((arr[i]+speed*d) >= (DP[i+1][j].first-speed)){
DP[i][j].first = min(DP[i][j].first, DP[i+1][j].first-speed);
DP[i][j].second = max(DP[i][j].second, min(arr[i]+speed*d, DP[i+1][j].second+speed));
}
}
}
return DP[1][n].first <= DP[1][n].second;
}
int main(){
scanf("%d %d %lld", &n, &k, &t);
for(int i=1; i<=n; i++){
scanf("%lld", &arr[i]);
// arr[i] = arr[i-1] + rand()%10;
// printf("%lld ", arr[i]);
}
ll L = 0, R = 1e9, ANS = 1e9;
while(L<=R){
ll MID = (L+R)/2;
if(able(MID) != able2(MID)){
printf("MID %lld: error\n", MID);
return 1;
}
if(able(MID)) ANS = MID, R = MID-1;
else L = MID+1;
}
printf("%lld", ANS);
}
Compilation message
sparklers.cpp: In function 'int main()':
sparklers.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
111 | scanf("%d %d %lld", &n, &k, &t);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:113:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
113 | scanf("%lld", &arr[i]);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Runtime error |
0 ms |
340 KB |
Execution failed because the return code was nonzero |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Runtime error |
0 ms |
340 KB |
Execution failed because the return code was nonzero |
| 13 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
0 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
1 ms |
340 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
1 ms |
340 KB |
Output is correct |
| 9 |
Correct |
1 ms |
340 KB |
Output is correct |
| 10 |
Correct |
1 ms |
340 KB |
Output is correct |
| 11 |
Correct |
1 ms |
340 KB |
Output is correct |
| 12 |
Runtime error |
0 ms |
340 KB |
Execution failed because the return code was nonzero |
| 13 |
Halted |
0 ms |
0 KB |
- |
