oj.uz

Submission #376376

# Submission time Handle Problem Language Result Execution time Memory
376376 2021-03-11T10:35:42 Z i_am_noob Candies (JOI18_candies) C++17
100 / 100
 4519 ms 5636 KB 
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
#define rep(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define maxn 200005
signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int n,a[maxn];
    long long dp[3][maxn];
    cin >> n;
    rep(i,0,n) cin >> a[i];
    dp[0][0]=dp[1][0]=0,dp[1][1]=a[0];
    rep(i,1,n){
        int x=(i+1)%3,y=(i+2)%3,z=i%3,l=1,r=i+2>>1,mid;
        dp[x][0]=0;
        if(dp[z][i+2>>1]>dp[y][i>>1]+a[i]){
            rep(j,1,i+4>>1) dp[x][j]=dp[z][j];
            continue;
        }
        while(l<r){
            mid=l+r>>1;
            if(dp[z][mid]<=dp[y][mid-1]+a[i]) r=mid;
            else l=mid+1;
        }
        rep(j,1,l) dp[x][j]=dp[z][j];
        rep(j,l,i+4>>1) dp[x][j]=dp[y][j-1]+a[i];
    }
    rep(i,1,n+3>>1) cout << dp[n%3][i] << "\n";
}

Compilation message

candies.cpp: In function 'int main()':
candies.cpp:15:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |         int x=(i+1)%3,y=(i+2)%3,z=i%3,l=1,r=i+2>>1,mid;
      |                                             ~^~
candies.cpp:17:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |         if(dp[z][i+2>>1]>dp[y][i>>1]+a[i]){
      |                  ~^~
candies.cpp:18:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   18 |             rep(j,1,i+4>>1) dp[x][j]=dp[z][j];
      |                     ~^~
candies.cpp:5:44: note: in definition of macro 'rep'
    5 | #define rep(i,b,a) for(int i=(b); i<((int)(a)); i++)
      |                                            ^
candies.cpp:22:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |             mid=l+r>>1;
      |                 ~^~
candies.cpp:27:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |         rep(j,l,i+4>>1) dp[x][j]=dp[y][j-1]+a[i];
      |                 ~^~
candies.cpp:5:44: note: in definition of macro 'rep'
    5 | #define rep(i,b,a) for(int i=(b); i<((int)(a)); i++)
      |                                            ^
candies.cpp:29:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |     rep(i,1,n+3>>1) cout << dp[n%3][i] << "\n";
      |             ~^~
candies.cpp:5:44: note: in definition of macro 'rep'
    5 | #define rep(i,b,a) for(int i=(b); i<((int)(a)); i++)
      |                                            ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 2 ms 364 KB Output is correct
11 Correct 2 ms 364 KB Output is correct
12 Correct 2 ms 364 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 2 ms 364 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 364 KB Output is correct
17 Correct 2 ms 364 KB Output is correct
18 Correct 2 ms 364 KB Output is correct
19 Correct 2 ms 364 KB Output is correct
20 Correct 2 ms 364 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 2 ms 364 KB Output is correct
6 Correct 2 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 2 ms 364 KB Output is correct
11 Correct 2 ms 364 KB Output is correct
12 Correct 2 ms 364 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 2 ms 364 KB Output is correct
15 Correct 2 ms 384 KB Output is correct
16 Correct 2 ms 364 KB Output is correct
17 Correct 2 ms 364 KB Output is correct
18 Correct 2 ms 364 KB Output is correct
19 Correct 2 ms 364 KB Output is correct
20 Correct 2 ms 364 KB Output is correct
21 Correct 4405 ms 5580 KB Output is correct
22 Correct 4460 ms 5356 KB Output is correct
23 Correct 4434 ms 5308 KB Output is correct
24 Correct 4316 ms 5416 KB Output is correct
25 Correct 4325 ms 5376 KB Output is correct
26 Correct 4317 ms 5284 KB Output is correct
27 Correct 4415 ms 5228 KB Output is correct
28 Correct 4378 ms 5484 KB Output is correct
29 Correct 4404 ms 5352 KB Output is correct
30 Correct 4395 ms 5224 KB Output is correct
31 Correct 4403 ms 5284 KB Output is correct
32 Correct 4402 ms 5228 KB Output is correct
33 Correct 4424 ms 5372 KB Output is correct
34 Correct 4422 ms 5328 KB Output is correct
35 Correct 4420 ms 5252 KB Output is correct
36 Correct 4451 ms 5312 KB Output is correct
37 Correct 4451 ms 5636 KB Output is correct
38 Correct 4519 ms 5380 KB Output is correct
39 Correct 4335 ms 5560 KB Output is correct
40 Correct 4312 ms 5376 KB Output is correct
41 Correct 4291 ms 5396 KB Output is correct
42 Correct 4403 ms 5268 KB Output is correct
43 Correct 4366 ms 5316 KB Output is correct
44 Correct 4383 ms 5472 KB Output is correct
45 Correct 4364 ms 5288 KB Output is correct
46 Correct 4362 ms 5232 KB Output is correct
47 Correct 4409 ms 5200 KB Output is correct
48 Correct 4420 ms 5268 KB Output is correct
49 Correct 4420 ms 5252 KB Output is correct
50 Correct 4441 ms 5304 KB Output is correct