Submission #151973

#	Time	Username	Problem	Language	Result	Execution time	Memory
151973		doowey	Candies (JOI18_candies)	C++14	0 / 100	79 ms	16120 KiB

candies

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)2e5 + 9;
const int K = 450;
const int M = 450;
const ll inf = (ll)1e15;
ll dp[M][K][2][2];
ll cur[K + 1][K][2][2];
ll best[2][N];

int main(){
  fastIO;
  for(int i = 0 ; i < M ; i ++ )
    for(int j = 0 ; j < K; j ++ )
      for(int x = 0; x < 2; x ++ )
        for(int y = 0 ;y < 2; y ++ )
          dp[i][j][x][y] = -inf;
  int n;
  cin >> n;
  vector<int> t;
  t.push_back(0);
  int a;
  for(int i = 1; i <= n; i ++ ){
    cin >> a;
    t.push_back(a);
  }
  int m = (n + K - 1) / K;
  int L=1, R;
  int idx;
  for(int i = 1 ; i <= m ; i ++ ){
    R = min(L + K - 1, n);
    if(L == R){
      dp[i][0][0][0] = 0;
      dp[i][1][1][1] = t[L];
    }
    else if(R == L + 1){
      dp[i][0][0][0] = 0;
      dp[i][1][0][1] = t[L + 1];
      dp[i][1][1][0] = t[L];
    }
    else{
      for(int x = 0 ; x < K ; x ++ ){
        for(int y = 0 ; y < K; y ++ ){
          for(int a =0 ; a < 2 ; a ++ ){
            for(int b = 0 ;b < 2; b ++ ){
              if(x == 0 && y == 0)
                cur[x][y][a][b] = 0;
              else
                cur[x][y][a][b] = -inf;
          
            }
          }
        }
      }
      idx = 0;
      for(int j = L ; j <= R; j ++ ){
        idx ++ ;
        for(int x = 0 ; x < idx; x ++ ){
          for(int a = 0; a < 2; a ++ ){
            for(int b = 0 ;b < 2; b ++ ){
              if(j == L){
                if(a)cur[idx][x + 1][a][b] = cur[idx - 1][x][a][b] + (a * t[idx]);
                else cur[idx][x][a][b] = cur[idx - 1][x][a][b];
              }
              else if(j == R){
                if(b)cur[idx][x + 1][a][b] =cur[idx - 2][x][a][b] + (b * t[idx]);
                else cur[idx][x][a][b] = cur[idx - 1][x][a][b];
              }
              else{
                cur[idx][x][a][b] = max(cur[idx][x][a][b], cur[idx - 1][x][a][b]);
                if(idx > 2 || !a){
                  cur[idx][x + 1][a][b] = max(cur[idx][x + 1][a][b], cur[idx - 2][x][a][b] + t[idx]);
                }
              }
            }
          }
        }
      }
      for(int x = 0 ; x <= K ; x ++ ){
        for(int a = 0 ;a < 2; a ++ ){
          for(int b =0 ; b < 2; b ++ ){
            dp[i][x][a][b] = cur[idx][x][a][b];
          }
        }
      }
    }
    L += K;
  }
  for(int i = 0 ; i < 2; i ++ ){
    for(int j=  0;  j < N ; j ++ ){
      best[i][j] = -inf;
    }
  }
  best[0][0] = 0;
  int lim = 0;
  for(int i = 1; i <= m ; i ++ ){
    for(int j = n ; j  >= 0 ; j -- ){
      for(int t = 0 ;t <= K ;t ++ ){
        for(int f = 0; f < 2; f ++ ){
          for(int a= 0 ; a < 2; a ++ ){
            for(int b = 0 ;b < 2; b ++ ){
              if(f && a) continue;
              if(j + t > n) continue;
              best[b][j + t] = max(best[b][j + t], best[f][j] + dp[i][t][a][b]);
            }
          }
        }
      }
    }
    lim += K;
  }
  for(int i = 1; i <= (n + 1) / 2; i ++ ){
    cout << max(best[0][i], best[1][i]) << "\n";
  }
  return 0;
}

Compilation message (stderr)

candies.cpp: In function 'int main()':
candies.cpp:92:46: warning: iteration 450 invokes undefined behavior [-Waggressive-loop-optimizations]
             dp[i][x][a][b] = cur[idx][x][a][b];
                              ~~~~~~~~~~~~~~~~^
candies.cpp:89:25: note: within this loop
       for(int x = 0 ; x <= K ; x ++ ){
                       ~~^~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 92