Submission #171635

#	Time	Username	Problem	Language	Result	Execution time	Memory
171635		Milki	Ljetopica (COI19_ljetopica)	C++14	100 / 100	156 ms	32248 KiB

ljetopica

#include<bits/stdc++.h>
using namespace std;

#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define REP(i, n) FOR(i, 0, n)
#define _ << " " <<
#define sz(x) ((int) x.size())
#define pb(x) push_back(x)
#define TRACE(x) cerr << #x << " = " << x << endl

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

const int mod = 1e9 + 7;

int add(int x, int y) {x += y; if(x >= mod) return x - mod; return x;}
int sub(int x, int y) {x -= y; if(x < 0) return x + mod; return x;}
int mul(int x, int y) {return (ll) x * y % mod;}

const int MAXN = 1e3 + 5;

int n, k, pot[MAXN];
string s, A, B;
point dp[MAXN][MAXN][2][2];

bool reduce(string &border){
  bool ret = false;
  REP(i, sz(border))
    if(border[i] == '1')
      ret = true;

  for(int i = sz(border) - 1; i >= 0; --i)
    if(border[i] == '1'){
      border[i] = '0';
      FOR(j, i + 1, sz(border))
        border[j] = '1';
      break;
    }
  return ret;
}

point rek(int depth, int changes, bool flipped, bool take_all, string &border){
  point &ret = dp[depth][changes][flipped][take_all];
  if(ret != point(-1, -1)) return ret;
  if(changes > k) return ret = {0, 0};
  if(depth == n - 1){
    if(changes == k) { return ret = {1, 0}; }
    else return ret = {0, 0};
  }

  int border_value = (border[depth + 1] == '1');
  int curr_value = (s[depth] == 'R');
  if(flipped) curr_value = !curr_value;

  if(!take_all && curr_value < border_value)
    take_all = true;
  if(!take_all && curr_value > border_value)
    return ret = {0, 0};

  int ways = 0, sum = 0;

  REP(flip, 2){
    if(depth == n - 2 && flip == 1) continue;

    int new_flip = flipped ^ flip;
    point tmp = rek(depth + 1, changes + flip, new_flip, take_all, border);
    ways = add(ways, tmp.first);
    sum = add(sum, tmp.second);
  }
  if(curr_value)
    sum = add(sum, mul(ways, pot[n - depth - 2]));

  return ret = {ways, sum};
}

void merge(point &A, point &B){
  A.first = add(A.first, B.first);
  A.second = add(A.second, B.second);
}

int solve(string &border){
  if(border[0] == '0') return 0;

  REP(i, MAXN) REP(j, MAXN) REP(it1, 2) REP(it2, 2)
    dp[i][j][it1][it2] = {-1, -1};

  point ret1 = rek(0, 0, false, false, border);
  point ret2 = rek(0, 1, true, false, border);
  point ret3 = rek(0, 0, true, false, border);
  point ret4 = rek(0, 1, false, false, border);

  merge(ret1, ret2);
  merge(ret1, ret3);
  merge(ret1, ret4);

  return add(ret1.second, mul(ret1.first, pot[n - 1]));
}

int main(){
  ios_base::sync_with_stdio(false); cin.tie(0);

  pot[0] = 1;
  FOR(i, 1, MAXN)
    pot[i] = mul(pot[i - 1], 2);

  cin >> n >> k;
  cin >> s >> A >> B;

  if(!reduce(A))
    cout << solve(B);
  else
    cout << sub( solve(B), solve(A) );
  //reduce(A); cout << solve(A);
}

• Subtask 1: 8 / 8
• Subtask 2: 14 / 14
• Subtask 3: 17 / 17
• Subtask 4: 61 / 61