oj.uz

Submission #376366

# Submission time Handle Problem Language Result Execution time Memory
376366 2021-03-11T10:07:32 Z i_am_noob Candies (JOI18_candies) C++17
100 / 100
 4506 ms 9652 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 ll long long
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define inf 1010000000
//#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {static int cnt=0;cerr << x << endl;cnt++;if(cnt>1000) exit(0);}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 826
#endif

inline char readchar(){
    const int maxn=1000000;
    static char buf[maxn],*p=buf,*q=buf;
    if(p==q&&(q=(p=buf)+fread(buf,1,maxn,stdin))==buf) return EOF;
    else return *p++;
}
inline int readint(){
    int c=readchar(),x=0,neg=0;
    while((c<'0'||c>'9')&&c!='-'&&c!=EOF) c=readchar();
    if(c=='-') neg=1,c=readchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^'0'),c=readchar();
    return neg?-x:x;
}

const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod;
const int maxn=200005;
//i_am_noob


signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    #ifdef i_am_noob
    freopen("input1.txt","r",stdin);
    freopen("output1.txt","w",stdout);
    freopen("output2.txt","w",stderr);
    #endif
    int n,a[maxn];
    ll dp[3][maxn];
    n=readint();
    rep(n) a[i]=readint();
    rep(n) dp[0][i]=dp[1][i]=-inf;
    dp[0][0]=dp[1][0]=0,dp[1][1]=a[0];
    rep2(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]){
            rep2(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;
        }
        rep2(j,1,l) dp[x][j]=dp[z][j];
        rep2(j,l,i+4>>1) dp[x][j]=dp[y][j-1]+a[i];
        //rep2(j,1,i+4>>1) w=dp[y][j-1]+a[i],dp[x][j]=dp[z][j]>w?dp[z][j]:w;
        //rep2(j,1,i+4>>1) if(dp[z][j]>dp[y][j-1]+a[i]) bug(i,j);
    }
    rep2(i,1,n+3>>1) cout << dp[n%3][i] << "\n";
    return 0;
}

Compilation message

candies.cpp: In function 'int main()':
candies.cpp:64:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |         int x=(i+1)%3,y=(i+2)%3,z=i%3,l=1,r=i+2>>1,mid;
      |                                             ~^~
candies.cpp:66:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |         if(dp[z][i+2>>1]>dp[y][i>>1]+a[i]){
      |                  ~^~
candies.cpp:67:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   67 |             rep2(j,1,i+4>>1) dp[x][j]=dp[z][j];
      |                      ~^~
candies.cpp:11:45: note: in definition of macro 'rep2'
   11 | #define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
      |                                             ^
candies.cpp:71:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |             mid=l+r>>1;
      |                 ~^~
candies.cpp:76:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |         rep2(j,l,i+4>>1) dp[x][j]=dp[y][j-1]+a[i];
      |                  ~^~
candies.cpp:11:45: note: in definition of macro 'rep2'
   11 | #define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
      |                                             ^
candies.cpp:80:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |     rep2(i,1,n+3>>1) cout << dp[n%3][i] << "\n";
      |              ~^~
candies.cpp:11:45: note: in definition of macro 'rep2'
   11 | #define rep2(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 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 2 ms 492 KB Output is correct
14 Correct 3 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 2 ms 492 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 1 ms 492 KB Output is correct
19 Correct 1 ms 492 KB Output is correct
20 Correct 1 ms 492 KB Output is correct

Subtask #2
92.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 2 ms 492 KB Output is correct
14 Correct 3 ms 492 KB Output is correct
15 Correct 1 ms 492 KB Output is correct
16 Correct 2 ms 492 KB Output is correct
17 Correct 1 ms 492 KB Output is correct
18 Correct 1 ms 492 KB Output is correct
19 Correct 1 ms 492 KB Output is correct
20 Correct 1 ms 492 KB Output is correct
21 Correct 4468 ms 8404 KB Output is correct
22 Correct 4497 ms 9616 KB Output is correct
23 Correct 4503 ms 9636 KB Output is correct
24 Correct 4406 ms 9316 KB Output is correct
25 Correct 4493 ms 9356 KB Output is correct
26 Correct 4477 ms 9340 KB Output is correct
27 Correct 4374 ms 9432 KB Output is correct
28 Correct 4447 ms 9524 KB Output is correct
29 Correct 4426 ms 9452 KB Output is correct
30 Correct 4506 ms 9536 KB Output is correct
31 Correct 4343 ms 9492 KB Output is correct
32 Correct 4350 ms 9460 KB Output is correct
33 Correct 4407 ms 9324 KB Output is correct
34 Correct 4417 ms 9600 KB Output is correct
35 Correct 4439 ms 9324 KB Output is correct
36 Correct 4421 ms 9452 KB Output is correct
37 Correct 4388 ms 9512 KB Output is correct
38 Correct 4423 ms 9652 KB Output is correct
39 Correct 4284 ms 9320 KB Output is correct
40 Correct 4281 ms 9564 KB Output is correct
41 Correct 4298 ms 9424 KB Output is correct
42 Correct 4347 ms 9452 KB Output is correct
43 Correct 4374 ms 9520 KB Output is correct
44 Correct 4361 ms 9452 KB Output is correct
45 Correct 4352 ms 9624 KB Output is correct
46 Correct 4342 ms 9520 KB Output is correct
47 Correct 4353 ms 9452 KB Output is correct
48 Correct 4401 ms 9196 KB Output is correct
49 Correct 4380 ms 9496 KB Output is correct
50 Correct 4397 ms 9508 KB Output is correct