Submission #494015

#	Time	Username	Problem	Language	Result	Execution time	Memory
494015		cadmiumsky	Popeala (CEOI16_popeala)	C++14	0 / 100	17 ms	644 KiB

popeala

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

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
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 74