oj.uz

답안 #225389

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
225389 2020-04-20T12:56:33 Z CaroLinda Solar Storm (NOI20_solarstorm) C++14
100 / 100
 649 ms 150100 KB 
#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

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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 98168 KB Output is correct
2 Correct 52 ms 98556 KB Output is correct
3 Correct 52 ms 98680 KB Output is correct
4 Correct 52 ms 98432 KB Output is correct
5 Correct 54 ms 98168 KB Output is correct
6 Correct 50 ms 98428 KB Output is correct
7 Correct 56 ms 98552 KB Output is correct
8 Correct 51 ms 98552 KB Output is correct
9 Correct 58 ms 98424 KB Output is correct
10 Correct 53 ms 98556 KB Output is correct
11 Correct 52 ms 98552 KB Output is correct
12 Correct 48 ms 98424 KB Output is correct

Subtask #2
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 375 ms 129144 KB Output is correct
2 Correct 268 ms 117880 KB Output is correct
3 Correct 309 ms 119288 KB Output is correct
4 Correct 298 ms 121208 KB Output is correct
5 Correct 347 ms 125176 KB Output is correct
6 Correct 478 ms 133208 KB Output is correct
7 Correct 302 ms 121848 KB Output is correct

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 98168 KB Output is correct
2 Correct 52 ms 98556 KB Output is correct
3 Correct 52 ms 98680 KB Output is correct
4 Correct 52 ms 98432 KB Output is correct
5 Correct 54 ms 98168 KB Output is correct
6 Correct 50 ms 98428 KB Output is correct
7 Correct 56 ms 98552 KB Output is correct
8 Correct 51 ms 98552 KB Output is correct
9 Correct 58 ms 98424 KB Output is correct
10 Correct 53 ms 98556 KB Output is correct
11 Correct 52 ms 98552 KB Output is correct
12 Correct 48 ms 98424 KB Output is correct
13 Correct 375 ms 129144 KB Output is correct
14 Correct 268 ms 117880 KB Output is correct
15 Correct 309 ms 119288 KB Output is correct
16 Correct 298 ms 121208 KB Output is correct
17 Correct 347 ms 125176 KB Output is correct
18 Correct 478 ms 133208 KB Output is correct
19 Correct 302 ms 121848 KB Output is correct
20 Correct 284 ms 120440 KB Output is correct
21 Correct 355 ms 125552 KB Output is correct
22 Correct 405 ms 130040 KB Output is correct
23 Correct 374 ms 129140 KB Output is correct
24 Correct 362 ms 128376 KB Output is correct
25 Correct 389 ms 128376 KB Output is correct
26 Correct 299 ms 120672 KB Output is correct
27 Correct 382 ms 126968 KB Output is correct
28 Correct 380 ms 126748 KB Output is correct
29 Correct 477 ms 135288 KB Output is correct
30 Correct 390 ms 128504 KB Output is correct
31 Correct 348 ms 124788 KB Output is correct

Subtask #4
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 460 ms 134108 KB Output is correct
2 Correct 252 ms 116856 KB Output is correct
3 Correct 257 ms 117756 KB Output is correct
4 Correct 374 ms 126840 KB Output is correct
5 Correct 354 ms 125816 KB Output is correct
6 Correct 369 ms 127352 KB Output is correct
7 Correct 536 ms 140216 KB Output is correct

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 98168 KB Output is correct
2 Correct 52 ms 98556 KB Output is correct
3 Correct 52 ms 98680 KB Output is correct
4 Correct 52 ms 98432 KB Output is correct
5 Correct 54 ms 98168 KB Output is correct
6 Correct 50 ms 98428 KB Output is correct
7 Correct 56 ms 98552 KB Output is correct
8 Correct 51 ms 98552 KB Output is correct
9 Correct 58 ms 98424 KB Output is correct
10 Correct 53 ms 98556 KB Output is correct
11 Correct 52 ms 98552 KB Output is correct
12 Correct 48 ms 98424 KB Output is correct
13 Correct 55 ms 98552 KB Output is correct
14 Correct 51 ms 98556 KB Output is correct
15 Correct 51 ms 98552 KB Output is correct
16 Correct 55 ms 98424 KB Output is correct
17 Correct 51 ms 98424 KB Output is correct
18 Correct 52 ms 98552 KB Output is correct
19 Correct 57 ms 98552 KB Output is correct
20 Correct 50 ms 98424 KB Output is correct
21 Correct 53 ms 98680 KB Output is correct
22 Correct 55 ms 98680 KB Output is correct
23 Correct 51 ms 98552 KB Output is correct
24 Correct 53 ms 98552 KB Output is correct
25 Correct 53 ms 98556 KB Output is correct
26 Correct 52 ms 98552 KB Output is correct
27 Correct 50 ms 98424 KB Output is correct
28 Correct 52 ms 98552 KB Output is correct
29 Correct 51 ms 98552 KB Output is correct
30 Correct 56 ms 98680 KB Output is correct

Subtask #6
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 98168 KB Output is correct
2 Correct 52 ms 98556 KB Output is correct
3 Correct 52 ms 98680 KB Output is correct
4 Correct 52 ms 98432 KB Output is correct
5 Correct 54 ms 98168 KB Output is correct
6 Correct 50 ms 98428 KB Output is correct
7 Correct 56 ms 98552 KB Output is correct
8 Correct 51 ms 98552 KB Output is correct
9 Correct 58 ms 98424 KB Output is correct
10 Correct 53 ms 98556 KB Output is correct
11 Correct 52 ms 98552 KB Output is correct
12 Correct 48 ms 98424 KB Output is correct
13 Correct 375 ms 129144 KB Output is correct
14 Correct 268 ms 117880 KB Output is correct
15 Correct 309 ms 119288 KB Output is correct
16 Correct 298 ms 121208 KB Output is correct
17 Correct 347 ms 125176 KB Output is correct
18 Correct 478 ms 133208 KB Output is correct
19 Correct 302 ms 121848 KB Output is correct
20 Correct 284 ms 120440 KB Output is correct
21 Correct 355 ms 125552 KB Output is correct
22 Correct 405 ms 130040 KB Output is correct
23 Correct 374 ms 129140 KB Output is correct
24 Correct 362 ms 128376 KB Output is correct
25 Correct 389 ms 128376 KB Output is correct
26 Correct 299 ms 120672 KB Output is correct
27 Correct 382 ms 126968 KB Output is correct
28 Correct 380 ms 126748 KB Output is correct
29 Correct 477 ms 135288 KB Output is correct
30 Correct 390 ms 128504 KB Output is correct
31 Correct 348 ms 124788 KB Output is correct
32 Correct 420 ms 133752 KB Output is correct
33 Correct 356 ms 125556 KB Output is correct
34 Correct 479 ms 135776 KB Output is correct
35 Correct 313 ms 120768 KB Output is correct
36 Correct 335 ms 122304 KB Output is correct
37 Correct 343 ms 124792 KB Output is correct
38 Correct 524 ms 138856 KB Output is correct
39 Correct 408 ms 128636 KB Output is correct
40 Correct 521 ms 139044 KB Output is correct

Subtask #7
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 47 ms 98168 KB Output is correct
2 Correct 52 ms 98556 KB Output is correct
3 Correct 52 ms 98680 KB Output is correct
4 Correct 52 ms 98432 KB Output is correct
5 Correct 54 ms 98168 KB Output is correct
6 Correct 50 ms 98428 KB Output is correct
7 Correct 56 ms 98552 KB Output is correct
8 Correct 51 ms 98552 KB Output is correct
9 Correct 58 ms 98424 KB Output is correct
10 Correct 53 ms 98556 KB Output is correct
11 Correct 52 ms 98552 KB Output is correct
12 Correct 48 ms 98424 KB Output is correct
13 Correct 375 ms 129144 KB Output is correct
14 Correct 268 ms 117880 KB Output is correct
15 Correct 309 ms 119288 KB Output is correct
16 Correct 298 ms 121208 KB Output is correct
17 Correct 347 ms 125176 KB Output is correct
18 Correct 478 ms 133208 KB Output is correct
19 Correct 302 ms 121848 KB Output is correct
20 Correct 284 ms 120440 KB Output is correct
21 Correct 355 ms 125552 KB Output is correct
22 Correct 405 ms 130040 KB Output is correct
23 Correct 374 ms 129140 KB Output is correct
24 Correct 362 ms 128376 KB Output is correct
25 Correct 389 ms 128376 KB Output is correct
26 Correct 299 ms 120672 KB Output is correct
27 Correct 382 ms 126968 KB Output is correct
28 Correct 380 ms 126748 KB Output is correct
29 Correct 477 ms 135288 KB Output is correct
30 Correct 390 ms 128504 KB Output is correct
31 Correct 348 ms 124788 KB Output is correct
32 Correct 460 ms 134108 KB Output is correct
33 Correct 252 ms 116856 KB Output is correct
34 Correct 257 ms 117756 KB Output is correct
35 Correct 374 ms 126840 KB Output is correct
36 Correct 354 ms 125816 KB Output is correct
37 Correct 369 ms 127352 KB Output is correct
38 Correct 536 ms 140216 KB Output is correct
39 Correct 55 ms 98552 KB Output is correct
40 Correct 51 ms 98556 KB Output is correct
41 Correct 51 ms 98552 KB Output is correct
42 Correct 55 ms 98424 KB Output is correct
43 Correct 51 ms 98424 KB Output is correct
44 Correct 52 ms 98552 KB Output is correct
45 Correct 57 ms 98552 KB Output is correct
46 Correct 50 ms 98424 KB Output is correct
47 Correct 53 ms 98680 KB Output is correct
48 Correct 55 ms 98680 KB Output is correct
49 Correct 51 ms 98552 KB Output is correct
50 Correct 53 ms 98552 KB Output is correct
51 Correct 53 ms 98556 KB Output is correct
52 Correct 52 ms 98552 KB Output is correct
53 Correct 50 ms 98424 KB Output is correct
54 Correct 52 ms 98552 KB Output is correct
55 Correct 51 ms 98552 KB Output is correct
56 Correct 56 ms 98680 KB Output is correct
57 Correct 420 ms 133752 KB Output is correct
58 Correct 356 ms 125556 KB Output is correct
59 Correct 479 ms 135776 KB Output is correct
60 Correct 313 ms 120768 KB Output is correct
61 Correct 335 ms 122304 KB Output is correct
62 Correct 343 ms 124792 KB Output is correct
63 Correct 524 ms 138856 KB Output is correct
64 Correct 408 ms 128636 KB Output is correct
65 Correct 521 ms 139044 KB Output is correct
66 Correct 308 ms 122740 KB Output is correct
67 Correct 491 ms 136420 KB Output is correct
68 Correct 373 ms 126428 KB Output is correct
69 Correct 443 ms 131948 KB Output is correct
70 Correct 312 ms 123684 KB Output is correct
71 Correct 509 ms 138872 KB Output is correct
72 Correct 331 ms 123768 KB Output is correct
73 Correct 442 ms 131784 KB Output is correct
74 Correct 286 ms 119160 KB Output is correct
75 Correct 439 ms 132584 KB Output is correct
76 Correct 309 ms 122104 KB Output is correct
77 Correct 411 ms 130296 KB Output is correct
78 Correct 297 ms 121184 KB Output is correct
79 Correct 375 ms 127736 KB Output is correct
80 Correct 469 ms 135288 KB Output is correct
81 Correct 305 ms 122620 KB Output is correct
82 Correct 421 ms 129144 KB Output is correct
83 Correct 290 ms 118776 KB Output is correct
84 Correct 305 ms 120568 KB Output is correct
85 Correct 290 ms 119160 KB Output is correct
86 Correct 486 ms 135132 KB Output is correct
87 Correct 282 ms 119136 KB Output is correct
88 Correct 457 ms 135160 KB Output is correct
89 Correct 378 ms 128116 KB Output is correct
90 Correct 350 ms 125280 KB Output is correct
91 Correct 649 ms 150100 KB Output is correct
92 Correct 527 ms 140004 KB Output is correct
93 Correct 604 ms 145156 KB Output is correct
94 Correct 600 ms 145036 KB Output is correct
95 Correct 464 ms 134728 KB Output is correct
96 Correct 397 ms 126836 KB Output is correct
97 Correct 521 ms 138096 KB Output is correct
98 Correct 374 ms 126064 KB Output is correct
99 Correct 473 ms 133032 KB Output is correct
100 Correct 452 ms 131660 KB Output is correct