Submission #225389

#	Time	Username	Problem	Language	Result	Execution time	Memory
225389		CaroLinda	Solar Storm (NOI20_solarstorm)	C++14	100 / 100	649 ms	150100 KiB

SolarStorm

#include <bits/stdc++.h>

#define debug
#define all(x) x.begin(),x.end()
#define lp(i,a,b) for(int i = a ; i< b ; i++)
#define ss second
#define ff first
#define ll long long
#define pb push_back

const int MAXN = 1e6+10 ;
const int LOG = 25 ;
const ll INF = 1e18+10 ;

using namespace std ;

int N , S ;
int ajuda[MAXN] ;
int dp[LOG][MAXN] ;
vector<int> seq ;
ll K ;
ll pref_val[MAXN] ;
ll d[MAXN] , meu_valor[MAXN] ;

ll dist( int x, int y ) { return d[y] - d[x] ; }
ll cost(int x, int y) { return pref_val[y] - pref_val[x-1] ; }


inline void pre_lca()
{
    lp(i,1,LOG)
        lp(j,1,N+1)
            if( dp[i-1][j] != -1 )
                dp[i][j] = dp[i-1][ dp[i-1][j] ] ;
}

inline void anda_S( int idx )
{
    int x = idx , aux = S ;

    for(int i = LOG - 1 ; i >= 0 ; i-- )
        if( aux-1 >= (1<<i) && dp[i][x] != -1 )
        {
            aux -= (1<<i) ;
            x = dp[i][x] ;
        }

    x = ajuda[x] ;

    meu_valor[idx] += cost( idx , x-1 ) ;
}

int main()
{

    scanf("%d%d%lld", &N, &S,&K ) ;
    lp(i,2,N+1)
    {
        scanf("%lld", &d[i] ) ;
        d[i] += d[i-1] ;
    }
    d[N+1] = INF ;
    lp(i,1,N+1)
    {
        scanf("%lld", &pref_val[i]) ;
        pref_val[i] += pref_val[i-1] ;
    }

    memset(dp, -1, sizeof dp );

    for(int i = N ; i > 0 ; i-- )
    {
        int best = lower_bound( d+1, d+i+1 , d[i] - K ) - d - 1;
        ajuda[i] = dp[0][i] = upper_bound( d+1, d+2+N , d[i] + K ) - d ;

        if( dp[0][i] != N+1 )
            ajuda[i] = dp[0][ dp[0][i] ] - 1 ;

        if( (best+1) <= (i-1) )
            meu_valor[i] = cost( best+1 , i-1 ) ;

    }

    lp(i,1,N+1) swap( ajuda[i] , dp[0][i] ) ;

    lp(i,1,N+1) debug("%d " , dp[0][i] ) ;
    debug("\n") ;

    pre_lca() ;

    lp(i,1,N+1) anda_S(i) ;

    ll mx = *max_element( meu_valor+1, meu_valor+1+N ) ;

    lp(i,1,N+1) debug("%lld " , meu_valor[i] ) ;
    debug("\n") ;

    lp(i,1,N+1)
        if( meu_valor[i] == mx )
        {
            int x = i ;

            while( S > 0 && x <= N )
            {
                seq.pb( x ) ;
                S -- ;

                x = dp[0][x] ;


            }

            break ;

        }

    printf("%lu\n", seq.size() ) ;
    for(int i : seq ) printf("%d " , i ) ;
    printf("\n") ;

}

Compilation message (stderr)

SolarStorm.cpp: In function 'int main()':
SolarStorm.cpp:86:38: warning: left operand of comma operator has no effect [-Wunused-value]
     lp(i,1,N+1) debug("%d " , dp[0][i] ) ;
                                      ^
SolarStorm.cpp:87:17: warning: statement has no effect [-Wunused-value]
     debug("\n") ;
                 ^
SolarStorm.cpp:95:44: warning: left operand of comma operator has no effect [-Wunused-value]
     lp(i,1,N+1) debug("%lld " , meu_valor[i] ) ;
                                            ^
SolarStorm.cpp:96:17: warning: statement has no effect [-Wunused-value]
     debug("\n") ;
                 ^
SolarStorm.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%lld", &N, &S,&K ) ;
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
SolarStorm.cpp:59:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &d[i] ) ;
         ~~~~~^~~~~~~~~~~~~~~~
SolarStorm.cpp:65:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld", &pref_val[i]) ;
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

• 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