Submission #329824

#	Time	Username	Problem	Language	Result	Execution time	Memory
329824		TLP39	Solar Storm (NOI20_solarstorm)	C++14	100 / 100	435 ms	118620 KiB

SolarStorm

#include<bits/stdc++.h>
using namespace std;


int main()
{
    int n,s;
    long long int k;
    scanf("%d %d %lld",&n,&s,&k);
    int d[n+1]={};
    int v[n]={};
    for(int i=1;i<n;i++)
    {
        scanf("%d",&d[i]);
    }
    for(int i=0;i<n;i++)
    {
        scanf("%d",&v[i]);
    }
    int ma[n]={};
    int po=0,pr=0;
    long long int sum=0;
    while(po<n || pr<n)
    {
        if(po==n)
        {
            ma[pr]=n-1;
            pr++;
        }
        else if(sum<=k)
        {
            po++;
            sum+=(long long)1*d[po];
        }
        else
        {
            ma[pr]=po-1;
            pr++;
            sum-=(long long)1*d[pr];
        }
    }
    int di[30]={};
    int pp=0;
    int temp=s;
    while(temp>0)
    {
        di[pp]=temp;
        pp++;
        temp=temp/2;
    }
    sort(di,di+pp);
    int res[pp][n];
    memset(res,0,sizeof res);
    for(int i=0;i<n;i++)
    {
        res[0][i]=ma[ma[i]];
    }
    for(int i=1;i<pp;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(di[i]%2==0)
            {
                if(res[i-1][j]==n-1)
                {
                    res[i][j]=n-1;
                }
                else
                {
                    res[i][j]=res[i-1][res[i-1][j]+1];
                }
            }
            else
            {
                if(res[i-1][j]==n-1)
                {
                    res[i][j]=n-1;
                }
                else
                {
                    res[i][j]=res[i-1][res[i-1][j]+1];
                    if(res[i][j]!=n-1)
                    {
                        res[i][j]=res[0][res[i][j]+1];
                    }
                }
            }
        }
    }
    long long int val[n+1];
    int be;
    val[0]=0;
    for(int i=1;i<=n;i++)
    {
        val[i]=val[i-1]+(long long)1*v[i-1];
    }
    long long int maxx=0,hol;
    for(int i=0;i<n;i++)
    {
        hol=val[res[pp-1][i]+1]-val[i];
        if(hol>maxx)
        {
            maxx=hol;
            be=i;
        }
    }
    printf("%d\n",s);
    for(int i=0;i<s;i++)
    {
        printf("%d ",ma[be]+1);
        be=res[0][be]+1;
        if(be>=n)
        {
            be=n-1;
        }
    }
}

Compilation message (stderr)

SolarStorm.cpp: In function 'int main()':
SolarStorm.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    9 |     scanf("%d %d %lld",&n,&s,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
SolarStorm.cpp:14:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   14 |         scanf("%d",&d[i]);
      |         ~~~~~^~~~~~~~~~~~
SolarStorm.cpp:18:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   18 |         scanf("%d",&v[i]);
      |         ~~~~~^~~~~~~~~~~~
SolarStorm.cpp:111:21: warning: 'be' may be used uninitialized in this function [-Wmaybe-uninitialized]
  111 |         be=res[0][be]+1;
      |            ~~~~~~~~~^

• Subtask 1: 10 / 10
• Subtask 2: 7 / 7
• Subtask 3: 11 / 11
• Subtask 4: 8 / 8
• Subtask 5: 18 / 18
• Subtask 6: 16 / 16
• Subtask 7: 30 / 30