Submission #447052

#	Time	Username	Problem	Language	Result	Execution time	Memory
447052		raid	Colouring a rectangle (eJOI19_colouring)	C++17	0 / 100	406 ms	54700 KiB

colouring

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define int long long
#define pb push_back
#define pii pair<int, int>
#define lin first
#define col second

using namespace std;

const int MAX = 600005;
const int INF = (int)1e18;

int n, m;
int costP[MAX], costS[MAX];
pii stP[MAX], drP[MAX], stS[MAX], drS[MAX];
vector<int> redP, redS, blueP, blueS;

int convRedP[MAX], convRedS[MAX];
int convBlueP[MAX], convBlueS[MAX];

int sumP[MAX], sumS[MAX];
int minP[MAX], minS[MAX];

void buildConv() {
  int np = redP.size() - 1, ns = redS.size() - 1;
  for ( int i = 1; i <= np; ++i ) {
	convRedP[redP[i]] = i;
  }
  for ( int i = 1; i <= ns; ++i ) {
	convRedS[redS[i]] = i;
  }
  np = blueP.size() - 1, ns = redS.size() - 1;
  for ( int i = 1; i <= np; ++i ) {
	convBlueP[blueP[i]] = i;
  }
  for ( int i = 1; i <= ns; ++i ) {
	convBlueS[blueS[i]] = i;
  }
}

void updStoP_red( int i ) {
  int indS = redS[i];
  pii st = stS[indS], dr = drS[indS];
  int sum = dr.lin + dr.col;
  int dpIndex = convRedP[sum - 1];

  int sum1 = st.lin + dr.col;
  int stIndex = convRedP[sum1 - 1];

  minP[dpIndex] = min( minP[dpIndex], minS[i] + sumP[dpIndex] - sumP[stIndex - 1] );
}
void updPtoS_red( int i ) {
  int indP = redP[i];
  pii st = stP[indP], dr = drP[indP];
  int diff = dr.lin - dr.col;
  int dpIndex = convRedS[diff + m];

  int diff1 = st.lin - st.col;
  int stIndex = convRedS[diff1 + m];

  minS[dpIndex] = min( minS[dpIndex], minP[i] + sumS[dpIndex] - sumS[stIndex - 1] );
}
int solve_red() {
  int np = redP.size() - 1, ns = redS.size() - 1;
  
  for ( int i = 1; i <= np; ++i ) {
	sumP[i] = sumP[i-1] + redP[i];  
    minP[i] = INF;
  }
  for ( int i = 1; i <= ns; ++i ) {
	sumS[i] = sumS[i-1] + redS[i]; 
    minS[i] = INF; 
  }
  for ( int i = 0; i <= min(np, ns); ++i ) {
	minP[i+1] = min( minP[i+1], minP[i] + costP[redP[i+1]] );
	minS[i+1] = min( minS[i+1], minS[i] + costS[redS[i+1]] );
    if ( i > 0 ) {
	  updStoP_red(i);
	  updPtoS_red(i);
	}
  }
  return min( minP[np], minS[ns] );
}

void updStoP_blue( int i ) {
  int indS = blueS[i];
  pii st = stS[indS], dr = drS[indS];
  int sum = dr.lin + dr.col;
  int dpIndex = convBlueP[sum - 1];

  int sum1 = st.lin + dr.col;
  int stIndex = convBlueP[sum1 - 1];

  minP[dpIndex] = min( minP[dpIndex], minS[i] + sumP[dpIndex] - sumP[stIndex - 1] );
}
void updPtoS_blue( int i ) {
  int indP = blueP[i];
  pii st = stP[indP], dr = drP[indP];
  int diff = dr.lin - dr.col;
  int dpIndex = convBlueS[diff + m];

  int diff1 = st.lin - st.col;
  int stIndex = convBlueS[diff1 + m];

  minS[dpIndex] = min( minS[dpIndex], minP[i] + sumS[dpIndex] - sumS[stIndex - 1] );
}
int solve_blue() {
  int np = blueP.size() - 1, ns = blueS.size() - 1;
  
  for ( int i = 1; i <= np; ++i ) {
	sumP[i] = sumP[i-1] + blueP[i];  
    minP[i] = INF;
  }
  for ( int i = 1; i <= ns; ++i ) {
	sumS[i] = sumS[i-1] + blueS[i]; 
    minS[i] = INF; 
  }
  for ( int i = 0; i <= min(np, ns); ++i ) {
	minP[i+1] = min( minP[i+1], minP[i] + costP[blueP[i+1]] );
	minS[i+1] = min( minS[i+1], minS[i] + costS[blueS[i+1]] );
    if ( i > 0 ) {
	  updStoP_blue(i);
	  updPtoS_blue(i);
	}
  }
  return min( minP[np], minS[ns] );
}


signed main() {
  int d;

  cin >> n >> m;
  d = n + m - 1;
  for ( int i = 1; i <= d; ++i ) {
    cin >> costP[i];
	int diff = -m + i; 
	if ( i <= m ) {
	  stP[i] = {1, 1 - diff};
	} else {
	  stP[i] = {1 + diff, 1};
	}
	if ( i <= n ) {
	  drP[i] = {m + diff, m};
	} else {
      drP[i] = {n, n - diff};
	}
  }
  for ( int i = 1; i <= d; ++i ) {
    cin >> costS[i];
	int sum = i + 1;
	if ( i <= m ) {
	  stP[i] = {1, sum - 1};
	} else {
	  stP[i] = {sum - m, m};
	}
	if ( i <= n ) {
	  drP[i] = {sum - 1, 1};
	} else {
	  drP[i] = {n, sum - n};
	}
  }
  redS.pb(0), redP.pb(0), blueS.pb(0), blueP.pb(0);
  if ( n & 1 ) {
	for ( int i = 1; i <= d; i += 2 ) {
      redS.pb( i );
	  redP.pb( i );
	}
	for ( int i = 2; i <= d; i += 2 ) {
	  blueS.pb( i );
	  blueP.pb( i );
	}
  } else {
	for ( int i = 1; i <= d; i += 2 ) {
      redS.pb( i );
	  blueP.pb( i );
	} 
	for ( int i = 2; i <= d; i += 2 ) {
	  blueS.pb( i );
	  redP.pb( i );
	}
  }
  buildConv();
  cout << solve_red() + solve_blue();
  return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 20
• Subtask 5: 0 / 10
• Subtask 6: 0 / 20
• Subtask 7: 0 / 20