Submission #204343

#	Time	Username	Problem	Language	Result	Execution time	Memory
204343		mhy908	Sparklers (JOI17_sparklers)	C++14	100 / 100	543 ms	2936 KiB

sparklers

#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=0, r=1000000000ll;
    while(l<r){
        LL mid=(l+r)/2;
        if(poss(mid))r=mid;
        else l=mid+1;
    }
    printf("%lld", l);
}

Compilation message (stderr)

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: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 50 / 50