Submission #494037

#	Time	Username	Problem	Language	Result	Execution time	Memory
494037		cadmiumsky	Popeala (CEOI16_popeala)	C++14	17 / 100	36 ms	2368 KiB

popeala

#include <vector>
#include <iostream>

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

int v[tmax];
int t;

vector<int> list[tmax];

static int popcount(int x) {
  int cnt=0;
  while(x) {
    cnt++;
    x&=x-1;
  }
  return cnt;
}

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);
    //if(x==1 && y==t-1)
    //cout << sum[y]-sum[x-1] <<' '<< popcount(rmq[x][step]&rmq[y - (1 << step) + 1][step]) <<'\n';
    return (sum[y]-sum[x-1])*
           popcount(rmq[x][step]&rmq[y - (1 << step) + 1][step]);
  }
};
int dp[tmax],prevdp[tmax];
int c[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 = min(mid - 1, br);
  for(auto i:list[mid]) {
    i--;
    if(i>min(mid-1,br))
      break;
    if(i<bl)
      continue;
    if(prevdp[i]+ cost::cost(i + 1, mid) <= dp[mid]) {
      dp[mid] = prevdp[i] + cost::cost(i + 1, mid);
      cut = i;
    }
  }
  int i=bl;
  if(prevdp[i]+ cost::cost(i + 1, mid) <= dp[mid]) {
    dp[mid] = prevdp[i] + cost::cost(i + 1, mid);
    cut = i;
  }
  i=min(mid-1,br);
  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, br);
  solve(mid + 1, r, bl ,br);
}

signed main() {
  int n,s;
  cin >> n >> t >> s;
  for(int i=0; i<t; i++) {
    cin >> v[i];
    prevdp[i]=tmax*50000;
  }
  for(int i=0; i<n; i++) {
    int last=-1;
    for(int j=0; j<t; j++) {
      char x;
      cin >> x;
      x-='0';
      last = (x == 0 ? i : last);
      list[j].push_back(last);
      cost::coef[j]|=(((ll)x)<<i);
    }
  }
  cost::construct();
  //cout << cost::cost(0,0) <<'\n';
  for(int i = 0; i < s; i++) {
    for(int j = -1; j < i - 1; j++)
      prevdp[j]=tmax*500000;
    if(i==0) {
      for(int i=0; i<t;i++)
        dp[i]=cost::cost(0,i);
    }
    else
      solve(i,t-1,i-1,t);
    cout << dp[t-1] <<'\n';
    for(int j = 0; j < t; j++)
      prevdp[j]=dp[j];
  }
}

Compilation message (stderr)

popeala.cpp: In function 'void cost::construct()':
popeala.cpp:33:57: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   33 |         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:53:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |   int mid = l + r >> 1;
      |             ~~^~~
popeala.cpp:55:7: warning: variable 'cut' set but not used [-Wunused-but-set-variable]
   55 |   int cut = min(mid - 1, br);
      |       ^~~

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 74