Submission #376376

#	Time	Username	Problem	Language	Result	Execution time	Memory
376376		i_am_noob	Candies (JOI18_candies)	C++17	100 / 100	4519 ms	5636 KiB

candies

#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 (stderr)

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 / 8
• Subtask 2: 92 / 92