oj.uz

Submission #204342

# Submission time Handle Problem Language Result Execution time Memory
204342 2020-02-25T13:02:26 Z mhy908 Sparklers (JOI17_sparklers) C++14
0 / 100
 5 ms 504 KB 
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sortvec(x) sort(all(x))
#define compress(x) x.erase(unique(all(x)), x.end())
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<LL, LL> pll;
typedef pair<int, LL> pil;
typedef pair<LL, int> pli;
const LL llinf=1987654321987654321;
const int inf=2000000000;
int n, k;
LL t, arr[100010], mv[100010];
bool poss(LL s){
    for(int i=1; i<=n; i++)mv[i]=arr[i]-2ll*s*t*i;
    if(mv[1]<mv[n])return false;
    int l1=k, r1=k, l2=1, r2=n;
    while(1){
        int l=l1-1, r=r1+1;
        bool br=true;
        while(l>=1&&mv[l]>=mv[r1]){
            if(mv[l]>=mv[l1]){
                l1=l;
                br=false;
                break;
            }
            l--;
        }
        while(r<=n&&mv[r]<=mv[l1]){
            if(mv[r]<=mv[r1]){
                r1=r;
                br=false;
                break;
            }
            r++;
        }
        if(br)break;
    }
    while(1){
        int l=l2+1, r=r2-1;
        bool br=true;
        while(l<=k&&mv[l]>=mv[r2]){
            if(mv[l]>=mv[l2]){
                l2=l;
                br=false;
                break;
            }
            l++;
        }
        while(r>=k&&mv[r]<=mv[l2]){
            if(mv[r]<=mv[r2]){
                r2=r;
                br=false;
                break;
            }
            r--;
        }
        if(br)break;
    }
    return l1<=l2&&r1>=r2;
}
int main(){
    scanf("%d %d %lld", &n, &k, &t);
    for(int i=1; i<=n; i++)scanf("%lld", &arr[i]);
    LL l=1, r=1000000000ll;
    while(l<r){
        LL mid=(l+r)/2;
        if(poss(mid))r=mid;
        else l=mid+1;
    }
    printf("%lld", l);
}

Compilation message

sparklers.cpp: In function 'int main()':
sparklers.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %lld", &n, &k, &t);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:69:33: 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("%lld", &arr[i]);
                            ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 50.0

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