| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 131510 |
2019-07-17T08:30:54 Z |
구재현(#3186) |
Sparklers (JOI17_sparklers) |
C++14 |
|
14 ms |
4476 KB |
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
using lint = long long;
using pi = pair<int, int>;
int n, k, a[MAXN], dp[MAXN][MAXN];
int t;
bool solve(vector<lint> x, vector<lint> y){
if(x[0] < y[0]) return 0;
vector<int> sx = {0}, sy = {0};
for(int i=1; i<x.size(); i++){
if(x[sx.back()] <= x[i]) sx.push_back(i);
}
for(int i=1; i<y.size(); i++){
if(y[sy.back()] >= y[i]) sy.push_back(i);
}
vector<lint> prec;
for(int i=0; i+1<sy.size(); i++){
prec.push_back(*max_element(y.begin() + sy[i] + 1, y.begin() + sy[i + 1] + 1));
}
int cs = 0, ce = 0;
for(int i=0; i<sx.size(); i++){
while(ce + 1 < sy.size()){
lint nxtmax = prec[ce];
//lint nxtmax = *max_element(y.begin() + sy[ce] + 1, y.begin() + sy[ce + 1] + 1);
if(nxtmax <= x[sx[i]]) ce++;
else break;
}
if(i + 1 < sx.size()){
lint nxtmin = *min_element(x.begin() + sx[i] + 1, x.begin() + sx[i + 1] + 1);
while(cs <= ce && y[sy[cs]] > nxtmin) cs++;
if(cs > ce) return 0;
}
}
return ce + 1 == sy.size();
}
bool trial(int s){
memset(dp, -1, sizeof(dp));
lint L = min(2ll * t * s, 2ll * a[n]);
vector<lint> vu, vd;
for(int i=1; i<=n; i++){
if(i <= k) vu.push_back(a[i] - L * i);
if(i >= k) vd.push_back(a[i] - L * i);
}
reverse(vu.begin(), vu.end());
int mx1 = max_element(vu.begin(), vu.end()) - vu.begin();
int mx2 = min_element(vd.begin(), vd.end()) - vd.begin();
vector<lint> u1, u2, d1, d2;
for(int i=0; i<=mx1; i++) u1.push_back(vu[i]);
for(int i=0; i<=mx2; i++) d1.push_back(vd[i]);
for(int i=mx1; i<vu.size(); i++) u2.push_back(vu[i]);
for(int i=mx2; i<vd.size(); i++) d2.push_back(vd[i]);
reverse(u2.begin(), u2.end());
reverse(d2.begin(), d2.end());
return solve(u1, d1) && solve(u2, d2);
}
int main(){
scanf("%d %d %d",&n,&k,&t);
for(int i=1; i<=n; i++) scanf("%d",&a[i]);
int s = 0, e = 1e9;
while(s != e){
int m = (s+e)/2;
if(trial(m)) e = m;
else s = m + 1;
}
cout << s << endl;
}
Compilation message
sparklers.cpp: In function 'bool solve(std::vector<long long int>, std::vector<long long int>)':
sparklers.cpp:13:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1; i<x.size(); i++){
~^~~~~~~~~
sparklers.cpp:16:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1; i<y.size(); i++){
~^~~~~~~~~
sparklers.cpp:20:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i+1<sy.size(); i++){
~~~^~~~~~~~~~
sparklers.cpp:24:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<sx.size(); i++){
~^~~~~~~~~~
sparklers.cpp:25:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ce + 1 < sy.size()){
~~~~~~~^~~~~~~~~~~
sparklers.cpp:31:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(i + 1 < sx.size()){
~~~~~~^~~~~~~~~~~
sparklers.cpp:37:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
return ce + 1 == sy.size();
~~~~~~~^~~~~~~~~~~~
sparklers.cpp: In function 'bool trial(int)':
sparklers.cpp:54:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=mx1; i<vu.size(); i++) u2.push_back(vu[i]);
~^~~~~~~~~~
sparklers.cpp:55:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=mx2; i<vd.size(); i++) d2.push_back(vd[i]);
~^~~~~~~~~~
sparklers.cpp: In function 'int main()':
sparklers.cpp:62: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:63:31: 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",&a[i]);
~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 2 |
Correct |
11 ms |
4344 KB |
Output is correct |
| 3 |
Correct |
11 ms |
4344 KB |
Output is correct |
| 4 |
Correct |
11 ms |
4344 KB |
Output is correct |
| 5 |
Correct |
14 ms |
4344 KB |
Output is correct |
| 6 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 7 |
Correct |
10 ms |
4216 KB |
Output is correct |
| 8 |
Correct |
12 ms |
4216 KB |
Output is correct |
| 9 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 10 |
Correct |
13 ms |
4216 KB |
Output is correct |
| 11 |
Correct |
11 ms |
4216 KB |
Output is correct |
| 12 |
Correct |
11 ms |
4216 KB |
Output is correct |
| 13 |
Correct |
13 ms |
4216 KB |
Output is correct |
| 14 |
Correct |
11 ms |
4216 KB |
Output is correct |
| 15 |
Correct |
11 ms |
4344 KB |
Output is correct |
| 16 |
Correct |
12 ms |
4364 KB |
Output is correct |
| 17 |
Correct |
11 ms |
4216 KB |
Output is correct |
| 18 |
Correct |
11 ms |
4216 KB |
Output is correct |
| 19 |
Correct |
11 ms |
4344 KB |
Output is correct |
| 20 |
Correct |
11 ms |
4344 KB |
Output is correct |
| 21 |
Correct |
11 ms |
4348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 2 |
Correct |
11 ms |
4344 KB |
Output is correct |
| 3 |
Correct |
11 ms |
4344 KB |
Output is correct |
| 4 |
Correct |
11 ms |
4344 KB |
Output is correct |
| 5 |
Correct |
14 ms |
4344 KB |
Output is correct |
| 6 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 7 |
Correct |
10 ms |
4216 KB |
Output is correct |
| 8 |
Correct |
12 ms |
4216 KB |
Output is correct |
| 9 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 10 |
Correct |
13 ms |
4216 KB |
Output is correct |
| 11 |
Correct |
11 ms |
4216 KB |
Output is correct |
| 12 |
Correct |
11 ms |
4216 KB |
Output is correct |
| 13 |
Correct |
13 ms |
4216 KB |
Output is correct |
| 14 |
Correct |
11 ms |
4216 KB |
Output is correct |
| 15 |
Correct |
11 ms |
4344 KB |
Output is correct |
| 16 |
Correct |
12 ms |
4364 KB |
Output is correct |
| 17 |
Correct |
11 ms |
4216 KB |
Output is correct |
| 18 |
Correct |
11 ms |
4216 KB |
Output is correct |
| 19 |
Correct |
11 ms |
4344 KB |
Output is correct |
| 20 |
Correct |
11 ms |
4344 KB |
Output is correct |
| 21 |
Correct |
11 ms |
4348 KB |
Output is correct |
| 22 |
Correct |
12 ms |
4476 KB |
Output is correct |
| 23 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 24 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 25 |
Correct |
12 ms |
4388 KB |
Output is correct |
| 26 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 27 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 28 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 29 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 30 |
Correct |
13 ms |
4348 KB |
Output is correct |
| 31 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 32 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 33 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 34 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 35 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 36 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 37 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 38 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 39 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 40 |
Correct |
12 ms |
4344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 2 |
Correct |
11 ms |
4344 KB |
Output is correct |
| 3 |
Correct |
11 ms |
4344 KB |
Output is correct |
| 4 |
Correct |
11 ms |
4344 KB |
Output is correct |
| 5 |
Correct |
14 ms |
4344 KB |
Output is correct |
| 6 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 7 |
Correct |
10 ms |
4216 KB |
Output is correct |
| 8 |
Correct |
12 ms |
4216 KB |
Output is correct |
| 9 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 10 |
Correct |
13 ms |
4216 KB |
Output is correct |
| 11 |
Correct |
11 ms |
4216 KB |
Output is correct |
| 12 |
Correct |
11 ms |
4216 KB |
Output is correct |
| 13 |
Correct |
13 ms |
4216 KB |
Output is correct |
| 14 |
Correct |
11 ms |
4216 KB |
Output is correct |
| 15 |
Correct |
11 ms |
4344 KB |
Output is correct |
| 16 |
Correct |
12 ms |
4364 KB |
Output is correct |
| 17 |
Correct |
11 ms |
4216 KB |
Output is correct |
| 18 |
Correct |
11 ms |
4216 KB |
Output is correct |
| 19 |
Correct |
11 ms |
4344 KB |
Output is correct |
| 20 |
Correct |
11 ms |
4344 KB |
Output is correct |
| 21 |
Correct |
11 ms |
4348 KB |
Output is correct |
| 22 |
Correct |
12 ms |
4476 KB |
Output is correct |
| 23 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 24 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 25 |
Correct |
12 ms |
4388 KB |
Output is correct |
| 26 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 27 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 28 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 29 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 30 |
Correct |
13 ms |
4348 KB |
Output is correct |
| 31 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 32 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 33 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 34 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 35 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 36 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 37 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 38 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 39 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 40 |
Correct |
12 ms |
4344 KB |
Output is correct |
| 41 |
Execution timed out |
3 ms |
376 KB |
Time limit exceeded (wall clock) |
| 42 |
Halted |
0 ms |
0 KB |
- |
