oj.uz

Submission #494015

# Submission time Handle Problem Language Result Execution time Memory
494015 2021-12-13T18:15:50 Z cadmiumsky Popeala (CEOI16_popeala) C++14
0 / 100
 17 ms 644 KB 
#include <iostream>

using namespace std;
using ll=long long;
#define int ll
const int tmax=20005;

int v[tmax];
int t;

namespace cost {
  ll coef[tmax];
  ll rmq[tmax][14];
  ll sum[tmax];
  #define sum (sum + 1)
  void construct() {
    for(int i=0; i<t; i++)
      sum[i]=sum[i-1]+v[i],rmq[i][0]=coef[i];
    for(int step = 1; step < 14; step++) {
      for(int i = 0; i < t; i++) {
        rmq[i][step]=(rmq[i][step-1]&rmq[i + (1 << step - 1)][step - 1]);
      }
    }
  }
  int cost(int x, int y) {
    int len=y-x+1,step=31-__builtin_clz(len);
    return (sum[y]-sum[x-1])*
           __builtin_popcount(rmq[x][step]&rmq[y - (1 << step) + 1][step]);
  }
};
int dp[tmax],prevdp[tmax];
#define dp (dp+1)
#define prevdp (prevdp+1)

static void solve(int l, int r, int bl, int br) {
  if(l>r)
    return;
  int mid=l+r>>1;
  dp[mid]=tmax*50000;
  int cut=bl;
  for(int i=bl; i<=min(mid-1,br); i++) {
    if(prevdp[i]+cost::cost(i+1,mid)<dp[mid]) {
      dp[mid]=prevdp[i]+cost::cost(i+1,mid);
      cut=i;
    }
  }
  solve(l,mid-1,bl,cut);
  solve(mid+1,r,cut,br);
}

signed main() {
  int n,s;
  cin >> n >> t >> s;
  for(int i=0; i<t; i++) {
    cin >> v[i];
    prevdp[i]=0;
  }
  for(int i=0; i<n; i++) {
    for(int j=0; j<t; j++) {
      char x;
      cin >> x;
      x-='0';
      cost::coef[j]|=(x<<i);
    }
  }
  cost::construct();
  //cout << cost::cost(0,t-1) <<'\n';
  for(int i = 0; i < s; i++) {
    solve(0,t-1,i-1,t);
    cout << dp[t-1] <<'\n';
    for(int j = 0; j < t; j++)
      prevdp[j]=dp[j];
  }
}

Compilation message

popeala.cpp: In function 'void cost::construct()':
popeala.cpp:21:57: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   21 |         rmq[i][step]=(rmq[i][step-1]&rmq[i + (1 << step - 1)][step - 1]);
      |                                                    ~~~~~^~~
popeala.cpp: In function 'void solve(ll, ll, ll, ll)':
popeala.cpp:38:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |   int mid=l+r>>1;
      |           ~^~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 644 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct