## 【记录】Google KickStart 2019C

### A题

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 233;
char op[maxn];
typedef set<pair<int,int> > spi;
spi r[maxn], c[maxn];
void add(spi &s, int pos)
{
int l = pos, r = pos;
auto it = s.lower_bound({pos, pos});
auto jt = it--; // jt: >=   it <=
if(it->second == pos - 1) l = it->first;
if(jt->first == pos + 1) r = jt->second;
s.insert({l, r});
if(l != pos) s.erase(it);
if(r != pos) s.erase(jt);
}
void move(spi &s, int &pos, int dir)
{
if(dir == -1)
{
auto it = s.lower_bound({pos, pos});
it--;
if(it->second == pos - 1) pos = it->first - 1;
else pos = pos - 1;
}
else
{
auto it = s.lower_bound({pos, pos});
if(it->first == pos + 1) pos = it->second + 1;
else pos = pos + 1;
}
}
int main()
{
int T; cin >> T;
for(int cas = 1; cas <= T; cas++)
{
int q, n, m, x, y;
scanf("%d%d%d%d%d", &q, &n, &m, &x, &y);
scanf("%s", op + 1);
for(int i = 1; i <= n; i++) r[i].clear(), r[i].insert({-1e9,-1e9}), r[i].insert({1e9,1e9});
for(int i = 1; i <= m; i++) c[i].clear(), c[i].insert({-1e9,-1e9}), c[i].insert({1e9,1e9});
for(int i = 1; i <= q; i++)
{
int dx = x, dy = y;
if(op[i] == 'N') // up
move(c[dy], dx, -1);
else if(op[i] == 'S') // down
move(c[dy], dx, 1);
else if(op[i] == 'W') // left
move(r[dx], dy, -1);
else // right
move(r[dx], dy, 1);
add(c[y], x), add(r[x], y);
x = dx, y = dy;
//cerr << x << " " << y << ">" << r[x].size() << endl;
}
printf("Case #%d: %d %d\n", cas, x, y);
}
}


### B题

#include<bits/stdc++.h>
using namespace std;
int mp[303][303], len[303][303];
int s[303], w[303];
multiset<int> st;
int main()
{
int T; cin >> T;
for(int cas = 1; cas <= T; cas++)
{
int n, m, k;
memset(len, 0, sizeof len);
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) scanf("%d", &mp[i][j]);
for(int i = 1; i <= n; i++)
{
st.clear();
int l = 1;
for(int j = 1; j <= m; j++)
{
while(l < j && *st.begin() + k < mp[i][j]) st.erase(st.find(mp[i][l++]));
len[i][j] = max(len[i][j], l);
st.insert(mp[i][j]);
}
st.clear();
l = 1;
for(int j = 1; j <= m; j++)
{
while(l < j && *st.rbegin() > mp[i][j] + k) st.erase(st.find(mp[i][l++]));
len[i][j] = max(len[i][j], l);
st.insert(mp[i][j]);
}
}
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++) len[i][j] = j - len[i][j] + 1;

// for(int i = 1; i <= n; i++)
//     for(int j = 1; j <= m; j++) printf("%d%c", len[i][j], " \n"[j == m]);

int p = 0, ans = 0;
for(int j = 1; j <= m; j++)
{
memset(s, 0, sizeof s);
memset(w, 0, sizeof w);
len[n + 1][j] = p = 0;
for(int i = 1; i <= n + 1; i++)
{
if(len[i][j] > s[p]) s[++p] = len[i][j], w[p] = 1;
else
{
int wd = 0;
while(s[p] > len[i][j])
{
wd += w[p];
ans = max(ans, wd * s[p]);
p--;
}
s[++p] = len[i][j], w[p] = wd + 1;
}
}
}
printf("Case #%d: %d\n", cas, ans);
}
}


### C题

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1000 + 233;
int pos[maxn];
vector<int> c[maxn];
int f[maxn][maxn], g[maxn][maxn];
int main()
{
int T; cin >> T;
int cas = 0;
while(T--)
{
int n, m; scanf("%d%d", &n, &m);
for(int i = 1; i <= 1000; i++) c[i].clear();
for(int i = 1; i <= n; i++) scanf("%d", &pos[i]);
for(int i = 1; i <= n; i++)
{
int t; scanf("%d", &t);
c[t].push_back(pos[i]);
}
for(int i = 1; i <= 1000; i++) sort(c[i].begin(), c[i].end());
memset(f, 0x3f, sizeof f);
memset(g, 0x3f, sizeof g);
f[0][0] = 0; g[1001][0] = 0;
//for(int i = 0; i < c[3].size(); i++) cout << c[3][i] << ' '; puts("");
for(int i = 1; i <= 1000; i++)
{
for(int j = 0; j <= m; j++)
{
f[i][j] = f[i - 1][j];
for(int k = 0; k < c[i].size(); k++)
{
int t = k + 1;
if(j - t >= 0)
f[i][j] = min(f[i][j], f[i - 1][j - t] + c[i][k] * 2);
}
}
}
//cout << f[1000][3] << endl;
for(int i = 1000; i; i--)
{
for(int j = 0; j <= m; j++)
{
g[i][j] = g[i + 1][j];
for(int k = 0; k < c[i].size(); k++)
{
int t = k + 1;
if(j - t >= 0)
g[i][j] = min(g[i][j], g[i + 1][j - t] + c[i][k] * 2);
}
}
}
//cout << g[1][3] << endl;
int ans = INT_MAX;
for(int i = 1; i <= 1000; i++)
{
for(int j = 0; j < c[i].size() && j <= m; j++)
{
for(int k = 0; k <= 1000; k++)
{
if(m - k - j - 1 >= 0)
ans = min(ans, f[i - 1][k] + g[i + 1][m - k - j - 1] + c[i][j]);
}
}
}
printf("Case #%d: %d\n", ++cas, ans);
}
}