Submission #363256

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
363256	2021-02-05 11:47:17	denkendoemeer	Sparklers (JOI17_sparklers)	C++14	100 / 100	43 ms	2924 KiB

sparklers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
#define ll long long
const ll inf=1e18;
using namespace std;
ll t,x[100005],dp[100005];
int n,k;
bool calc(ll nr)
{
    nr=nr*2;
    if (t*nr>(ll)1e9)
        return 1;
    int i;
    for(i=1;i<=n;i++)
        dp[i]=x[i]-i*t*nr;
    int st=1,dr=n;
    for(i=1;i<=k;i++)
        if (dp[st]<=dp[i])
            st=i;
    for(i=k;i<=n;i++)
        if (dp[dr]>=dp[i])
            dr=i;
    int l=k,r=k;
    ll v1=dp[l],v2=dp[r];
    while(st<=l || r<=dr){
        int auxl=l,auxr=r;
        while(l>=st && dp[l]>=v2){
            v1=max(v1,dp[l]);
            l--;
        }
        while(r<=dr && dp[r]<=v1){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

sparklers.cpp: In function 'int main()':
sparklers.cpp:60:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |     scanf("%d%d%lld",&n,&k,&t);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
sparklers.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |         scanf("%lld",&x[i]);
      |         ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 20 / 20
• Subtask 3: 50 / 50