# Kick Start 2019 Round C

2019-05-26 20:13 +0800

2019-06-06 23:24 +0800

## A - Wiggle Walk

$R \times C$的地图，每一格走过之后就会变滑（不会再次停在这个位置），问按照指定的方向走之后最后停在的位置的坐标。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

int n = 0, R = 0, C = 0;
bitset<50005> bx[50005];
bitset<50005> by[50005];

pii solve() {
int x = 0, y = 0;
string cmd;
cin >> n >> R >> C >> x >> y >> cmd;
for (int i = 1; i <= R; ++i) bx[i].reset();
for (int j = 1; j <= C; ++j) by[j].reset();
for (int i = 0; i < n; ++i) {
bx[x].set(y);
by[y].set(x);
switch (cmd[i]) {
case 'N':
while (by[y][x]) --x;
break;
case 'S':
while (by[y][x]) ++x;
break;
case 'E':
while (bx[x][y]) ++y;
break;
default:
while (bx[x][y]) --y;
break;
}
}
return make_pair(x, y);
}

int main() {
cin.sync_with_stdio(false);
cout.sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int _T;
cin >> _T;
for (int _t = 1; _t <= _T; ++_t) {
cout << "Case #" << _t << ": ";
pii ans = solve();
cout << ans.first << " " << ans.second;
cout << endl;
}
return 0;
}


## B - Circuit Board

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

int R = 0, C = 0, K = 0;
int len[305][305] = {};

void prepare() {
memset(len, 0, sizeof(len));
cin >> R >> C >> K;
int val[305] = {};
for (int i = 0; i < R; ++i) {
for (int j = 0; j < C; ++j) {
cin >> val[j];
}

deque<int> qmin, qmax;
int l = 0, r = 0;
while (l < C) {
while (r < C) {
while (!qmin.empty() && val[qmin.back()] >= val[r]) qmin.pop_back();
qmin.push_back(r);
while (!qmax.empty() && val[qmax.back()] <= val[r]) qmax.pop_back();
qmax.push_back(r);
if (val[qmax.front()] - val[qmin.front()] > K) break;
++r;
}
len[i][l] = r - l;
if (qmin.front() == l) qmin.pop_front();
if (qmax.front() == l) qmax.pop_front();
++l;
}
}
}

int solve() {
int ans = 0;
for (int l = 1; l <= C; ++l) {
for (int j = 0; j <= C - l; ++j) {
int cnt = 0;
for (int i = 0; i < R; ++i) {
if (len[i][j] >= l) cnt++;
else {
ans = max(ans, l * cnt);
cnt = 0;
}
}
ans = max(ans, l * cnt);
}
}
return ans;
}

int main() {
cin.sync_with_stdio(false);
cout.sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int _T;
cin >> _T;
for (int _t = 1; _t <= _T; ++_t) {
cout << "Case #" << _t << ": ";
prepare();
cout << solve() << endl;
}
return 0;
}


## C - Catch Some

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1000;
const int INF = 0x3f3f3f3f;

int n = 0, k = 0, maxd = 0;
int cnt[1005] = {};
int dp[1005][1005][2] = {};
vector<int> dogs[1005];

void prepare() {
maxd = 0;
memset(cnt, 0x00, sizeof(cnt));
for (int i = 0; i <= MAXN; ++i) dogs[i].clear();
for (int i = 0; i <= MAXN; ++i) dogs[i].push_back(0);
for (int i = 0; i <= MAXN; ++i)
for (int j = 0; j <= MAXN; ++j)
dp[i][j][0] = dp[i][j][1] = INF;
}

int solve() {
dp[0][0][0] = 0;
for (int i = 1; i <= MAXN; ++i) {
for (int j = 0; j <= cnt[i]; ++j) {
for (int lst = 0; lst <= k - j; ++lst) {
dp[i][lst + j][0] = min(dp[i][lst + j][0], dp[i - 1][lst][0] + 2 * dogs[i][j]);
dp[i][lst + j][1] = min(dp[i][lst + j][1], dp[i - 1][lst][1] + 2 * dogs[i][j]);
dp[i][lst + j][1] = min(dp[i][lst + j][1], dp[i - 1][lst][0] + 1 * dogs[i][j]);
}
}
}

return dp[MAXN][k][1];
}

int main() {
cin.sync_with_stdio(false);
cout.sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int _T;
cin >> _T;
for (int _t = 1; _t <= _T; ++_t) {
cout << "Case #" << _t << ": ";

prepare();
cin >> n >> k;
int color = 0;
int pos[1005] = {};
for (int i = 0; i < n; ++i) {
cin >> pos[i];
maxd = max(maxd, pos[i]);
}
for (int i = 0; i < n; ++i) {
cin >> color;
cnt[color]++;
dogs[color].push_back(pos[i]);
}
for (int i = 0; i < MAXN; ++i) {
sort(dogs[i].begin(), dogs[i].end());
}
cout << solve();

cout << endl;
}
return 0;
}


Comments are disabled due to technical issues.
Alternative: mail to blog.doowzs[at]outlook.com