Coder's Brunch: 다시풀예정

레이블이 다시풀예정인 게시물을 표시합니다. 모든 게시물 표시

11498번: Odd Cycle

https://www.acmicpc.net/problem/11498

#include<cstdio>
#include<vector>
using namespace std;
int tc, n, m, ck[100001], valid[100001], cl[100001], flag[100001];
vector<int> adj[2][100001], vis;
void dfs(int h, int ty) {
    if (ck[h] ^ ty) return;
    ck[h] = !ty;
    for (auto &it : adj[ty][h]) dfs(it, ty);
    vis.push_back(h);
}
vector<int> via, via2;
bool dfs3(int h) {
    if (flag[h]) {
        int i = 0;
        while (via[i] ^ h) i++;
        printf("1\n%d\n", via2.size() + via.size() - i);
        for (auto &it : via2) printf("%d\n", it);
        for (; i < via.size(); i++) printf("%d\n", via[i]);
        return true;
    }
    int tt = valid[h];
    valid[h] = -1;
    via2.push_back(h);
    for (auto &it : adj[0][h]) if (valid[it] == tt && cl[it] - cl[h] & 1) {
        if (dfs3(it)) return true;
    }
    via2.pop_back();
    return false;
}
bool dfs2(int h) {
    via.push_back(h);
    flag[h] = 1;
    for (auto &it : adj[0][h]) if (valid[it] == valid[h]) {
        if (!~cl[it]) {
            cl[it] = cl[h] + 1;
            if (dfs2(it)) return true;
        }
        else if (cl[h] + 1 - cl[it] & 1) {
            via2.clear();
            dfs3(it);
            return true;
        }
    }
    via.pop_back();
    flag[h] = 0;
    return false;
}
int main() {
    for (scanf("%d", &tc); tc--;) {
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= n; i++) {
            adj[0][i].clear();
            adj[1][i].clear();
            valid[i] = cl[i] = -1;
            ck[i] = 0;
        }
        for (int i = 0, x, y; i < m; i++) {
            scanf("%d%d", &x, &y);
            adj[0][x].push_back(y);
            adj[1][y].push_back(x);
        }
        vis.clear();
        for (int i = 1; i <= n; i++) dfs(i, 0);
        vector<int> tvis = vis;
        int rr = 0;
        for (int i = n; i--;) if (ck[tvis[i]]) {
            vis.clear();
            dfs(tvis[i], 1);
            for (auto &it : vis) valid[it] = i, flag[it] = 0;
            cl[vis[0]] = 0;
            via.clear();
            if (dfs2(vis[0])) { rr = 1; break; }
        }
        if (!rr) puts("-1");
    }
    return 0;
}

10257번: Stains

https://www.acmicpc.net/problem/10257

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
int t, m, n, c, st[1001][10], dp[1001][60000];
vector<int> cd;
int f(int h, int b) {
    if (h > n) return 0;
    int &ret = dp[h][b];
    if (~ret) return ret;
    int ck[10] = {};
    ret = 1e9;
    for (int &it : cd) {
        int cnt = 0, flag = 0, nxt = 0;
        for (int i = b, j = 0; j < m; i /= 3, j++) ck[j] = i % 3;
        for (int i = 0; i < m - 2; i++) if (1 << i&it) {
            cnt++;
            for (int j = i; j < i + 3; j++) ck[j] = 3;
        }
        for (int i = m; i--;) {
            if (st[h][i] && !ck[i]) flag = 1;
            if (ck[i]) ck[i]--;
            nxt = nxt * 3 + ck[i];
        }
        if (!flag) ret = min(ret, cnt + f(h + 1, nxt));
    }
    return ret;
}
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d%d%d", &m, &n, &c);
        cd.clear();
        memset(dp, -1, sizeof(dp));
        memset(st, 0, sizeof(st));
        for (int i = 1 << m - 2; i--;) {
            int flag = 0;
            for (int j = 1; j < m - 3; j++) if (1 << j & i && 1 << j - 1 & i) flag = 1;
            for (int j = 2; j < m - 3; j++) if (1 << j & i && 1 << j - 2 & i) flag = 1;
            if (flag) continue;
            cd.push_back(i);
        }
        for (int i = 0, x, y; i < c; i++) {
            scanf("%d%d", &x, &y);
            st[y][x - 1] = 1;
        }
        printf("%d\n", f(1, 0));
    }
    return 0;
}

11064번: Diameter

https://www.acmicpc.net/problem/11064

#include<cstdio>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
int t, n, d;
int main() {
    for (scanf("%d", &t); t--;) {
        vector<pair<int, int> > adj[40001];
        priority_queue<pair<int, int> > pq;
        int r = 0, t = 0, cnt = 0, ind[40001] = {};
        scanf("%d%d", &n, &d);
        for (int i = 1, x, y, z; i < n; i++) {
            scanf("%d%d%d", &x, &y, &z);
            adj[x].push_back({ y,z });
            adj[y].push_back({ x,z });
            r += z;
            ind[x]++;
            ind[y]++;
        }
        for (int i = 1; i <= n; i++) if (ind[i] == 1) pq.push({ -adj[i][0].second,i }), cnt++;
        for (;;) {
            int h = pq.top().second, dis = -pq.top().first;
            pq.pop();
            if (2 * dis >= d) {
                printf("%.1lf\n", r - (d / 2.0 - t) * cnt);
                break;
            }
            r -= (dis - t)*cnt--;
            if (cnt == 1) {
                puts("0.0");
                break;
            }
            ind[h]--;
            for (auto u : adj[h]) if (--ind[u.first] == 1) {
                for (auto v : adj[u.first]) if (ind[v.first]) pq.push({ -dis - v.second,u.first }), cnt++;
            }
            t = dis;
        }
    }
    return 0;
}

10563번: Number Game

https://www.acmicpc.net/problem/10563

#include<cstdio>
#include<cstring>
int t, n, dp[100][100][100], a[100], l, r, lc, rc, g;
int f(int s, int e, int c) {
    if (c < 0 || s > g || e < g || s == e) return 1;
    int &ret = dp[s][e][c];
    if (!~ret) ret = !f(s + 1, e, s == l ? lc + c : c) | !f(s, e - 1, e == r ? rc + c : c) | !f(s, e, c - 1);
    return ret;
}
int main() {
    for (scanf("%d", &t); t--;) {
        scanf("%d", &n);
        lc = 0; rc = 0;
        memset(dp, -1, sizeof(dp));
        for (int i = 0; i < n; i++) {
            scanf("%d", a + i);
            if (a[i] == 1) l = r = g = i;
        }
        for (; l && a[l - 1] > a[l];) l--;
        for (; r < n - 1 && a[r] < a[r + 1];) r++;
        int i = l, j = r;
        for (; i && a[i - 1] < a[i]; i--) lc++;
        for (; j < n - 1 && a[j] > a[j + 1]; j++) rc++;
        puts(f(l, r, i + n - 1 - j) ? "Alice" : "Bob");
    }
    return 0;
}

5627번: BAKTERIJE

https://www.acmicpc.net/problem/5627

풀이는 http://hsin.hr/coci/archive/2012_2013/에서 contest #6의 6번 참조

#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 };
typedef long long ll;
int n, m, k, ex, ey, ck[51][51][4], u[51][51];
ll res = -1;
vector<pair<int, int> > v[5], pa;
int gcd(int x, int y) { return y ? gcd(y, x%y) : x; }
void ee(ll a, ll b, ll &x, ll &y) {
    if (b) ee(b, a%b, y, x), y -= a / b*x;
    else x = 1 / a, y = 0;
}
ll multi(ll x, ll y, ll mod) {
    if (!y) return 0;
    ll ret = multi(x, y / 2, mod);
    return (ret * 2 + y % 2 * x) % mod;
}
void crt() {
    int maxi = 0;
    vector<pair<int, int> > t = pa;
    for (int i = 0; i < k; i++) {
        if (maxi < t[i].second) maxi = t[i].second;
        if (!t[i].first) {
            for (auto it : t)
                if (!it.first && t[i].second != it.second || it.first && (t[i].second < it.second || (t[i].second - it.second) % it.first)) return;
            if (!~res || res > t[i].second) res = t[i].second;
            return;
        }
        for (int j = 0; j < i; j++) if ((t[i].second - t[j].second) % gcd(t[i].first, t[j].first)) return;
    }
    ll a = 1, b = 0;
    for (int i = 2; i < 1e4; i++) {
        ll tp, p = 1, r = 0, x, y, ta;
        for (int j = 0; j < k; j++) {
            tp = 1;
            while (t[j].first%i == 0) t[j].first /= i, tp *= i;
            if (p < tp) p = tp, r = t[j].second%p;
        }
        if (p > 1) {
            ee(p, a, x, y);
            ta = a*p;
            b = (multi(multi(p, x, ta), b, ta) + multi(multi(a, y, ta), r, ta)) % ta;
            a = ta;
        }
    }
    while (b < maxi) b += a;
    if (!~res || res > b) res = b;
}
void f(int h) {
    if (h == k) crt();
    else for (auto it : v[h]) {
        pa.push_back(it);
        f(h + 1);
        pa.pop_back();
    }
}
int main() {
    scanf("%d%d%d%d%d", &n, &m, &k, &ex, &ey);
    for (int i = 0; i < k; i++) {
        int x, y, d, cnt = 1;
        char c;
        scanf("%d%d %c", &x, &y, &c);
        for (int j = 1; j <= n; j++) for (int k = 1; k <= m; k++) scanf("%1d", u[j] + k);
        memset(ck, 0, sizeof(ck));
        for (int j = 0; j < 4; j++) if ("URDL"[j] == c) d = j;
        while (!ck[x][y][d]) {
            ck[x][y][d] = cnt++;
            d = (d + u[x][y]) % 4;
            if (x + dx[d] < 1 || x + dx[d] > n || y + dy[d] < 1 || y + dy[d] > m) d = (d + 2) % 4;
            x += dx[d]; y += dy[d];
        }
        for (int it : ck[ex][ey]) if (it) v[i].push_back({ it < ck[x][y][d] ? 0 : cnt - ck[x][y][d],it });
    }
    f(0);
    printf("%lld", res);
    return 0;
}

14553번: The Way

https://www.acmicpc.net/problem/14553

시간복잡도는 $O(n)$

#include<cstdio>
#define mod int(1e9 + 9)
int n;
long long dp[1001][3] = { { 1,0,0 },{ 1,1,1 } };
int main() {
    scanf("%d", &n);
    for (int i = 2; i <= n; i++) {
        dp[i][0] = (dp[i - 1][0] * 2 + dp[i - 1][1] + dp[i - 1][2] - dp[i - 2][0] - dp[i - 2][1] + mod * 2) % mod;
        dp[i][1] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % mod;
        dp[i][2] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] * 2 - dp[i - 2][1] - dp[i - 2][2] + mod * 2) % mod;
    }
    printf("%lld", dp[n][2]);
    return 0;
}

7984번: Rabbits

https://www.acmicpc.net/problem/7984

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n, k, a[2001], dp[2001][2001], s, res;
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", a + i), s += a[i];
    if (2 * k >= n) {
        printf("%d", s);
        return 0;
    }
    for (int i = 1; i <= k; i++) {
        int maxi = 0;
        for (int j = i; j <= n; j++) {
            maxi = max(maxi, dp[i - 1][j - 1]);
            dp[i][j] = maxi + a[j];
            if (i > 1 && j > i) dp[i][j] = max(dp[i][j], dp[i - 1][j - 2] + a[j] + a[j - 1]);
        }
    }
    for (int i = k; i <= n; i++) res = max(res, dp[k][i]);
    memset(dp, 0, sizeof(dp));
    dp[1][1] = a[1];
    for (int i = 2; i <= n; i++) dp[1][i] = -2e9;
    for (int i = 2; i <= k; i++) {
        int maxi = 0;
        for (int j = i; j <= n; j++) {
            maxi = max(maxi, dp[i - 1][j - 1]);
            dp[i][j] = maxi + a[j];
            if (i > 1 && j > i) dp[i][j] = max(dp[i][j], dp[i - 1][j - 2] + a[j] + a[j - 1]);
        }
    }
    for (int i = 1; i < k; i++) {
        int maxi = 0;
        for (int j = k - i; j <= n - 2 * i; j++) maxi = max(maxi, dp[k - i][j]);
        for (int j = n - 2 * i + 1; j <= n; j++) maxi += a[j];
        res = max(res, maxi);
    }
    rotate(a + 1, a + 2, a + 1 + n);
    memset(dp, 0, sizeof(dp));
    dp[1][1] = a[1];
    for (int i = 2; i <= n; i++) dp[1][i] = -2e9;
    for (int i = 2; i <= k; i++) {
        int maxi = 0;
        for (int j = i; j <= n; j++) {
            maxi = max(maxi, dp[i - 1][j - 1]);
            dp[i][j] = maxi + a[j];
            if (i > 1 && j > i) dp[i][j] = max(dp[i][j], dp[i - 1][j - 2] + a[j] + a[j - 1]);
        }
    }
    for (int i = 1; i < k; i++) {
        int maxi = 0;
        for (int j = k - i; j <= n - 2 * i; j++) maxi = max(maxi, dp[k - i][j]);
        for (int j = n - 2 * i + 1; j <= n; j++) maxi += a[j];
        res = max(res, maxi);
    }
    printf("%d", res);
    return 0;
}

2051번: 최소 버텍스 커버

https://www.acmicpc.net/problem/2051

$O(n^2m)$

#include<cstdio>
#include<vector>
using namespace std;
int n, m, r[1001], vis[1001], res, ck[1001], acnt, bcnt, b[1001];
vector<int> adj[1001];
int f(int h) {
    if (vis[h]) return 0;
    vis[h] = 1;
    for (int it : adj[h]) {
        if (!r[it] || f(r[it])) {
            r[it] = h;
            return 1;
        }
    }
    return 0;
}
void g(int h) {
    if (vis[h]) return;
    vis[h] = 1;
    acnt++;
    for (int it : adj[h]) bcnt += !b[it]++, g(r[it]);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, x, y; i <= n; i++)
        for (scanf("%d", &x); x--;) scanf("%d", &y), adj[i].push_back(y);
    for (int i = 1; i <= n; i++) {
        if (f(i)) ck[i] = 1, res++;
        for (int j = 1; j <= n; j++) vis[j] = 0;
    }
    for (int i = 1; i <= n; i++) if (!ck[i]) g(i);
    printf("%d\n%d", res, n - acnt);
    for (int i = 1; i <= n; i++) if (!vis[i]) printf(" %d", i);
    printf("\n%d", bcnt);
    for (int i = 1; i <= n; i++) if (b[i]) printf(" %d", i);
    return 0;
}

1742번: 레이싱결과

https://www.acmicpc.net/problem/1742

#include<cstdio>
#include<map>
#include<vector>
#define mod 1000003
using namespace std;
map<int, int> dp;
vector<int> adj[31], radj[31];
int n, m, r = 1, vis[31], c[31][31], cnt, ind[31], p, s;
void f(int h) {
    if (vis[h]) return;
    vis[h] = p;
    cnt++;
    for (int it : adj[h]) f(it);
    for (int it : radj[h]) f(it);
}
int g(int h) {
    if (dp.find(h) != dp.end()) return dp[h];
    if (!h) {
        for (int i = 1; i <= n; i++) if (vis[i] == p&&ind[i]) return 0;
        return 1;
    }
    int &ret = dp[h];
    for (int i = 1; i <= n; i++) if (h & 1 << i) {
        int t = h ^ 1 << i;
        for (int it : adj[i]) if (!--ind[it]) t ^= 1 << it;
        ret = (ret + g(t)) % mod;
        for (int it : adj[i]) ind[it]++;
    }
    return ret;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n; i++) {
        c[i][0] = 1;
        for (int j = 1; j <= i; j++) c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
    }
    for (int x, y; m--;) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
        radj[y].push_back(x);
        ind[y]++;
    }
    for (p = 1, s = n; p <= n; p++) if (!vis[p]) {
        cnt = 0;
        f(p);
        int t = 0;
        for (int i = p; i <= n; i++) if (vis[i] == p && !ind[i]) t |= 1 << i;
        r = 1LL * r * g(t) % mod*c[s][cnt] % mod;
        s -= cnt;
    }
    printf("%d", r);
    return 0;
}

1432번: 그래프 수정

https://www.acmicpc.net/problem/1432

#include<cstdio>
#include<queue>
#include<vector>
using namespace std;
int n, ind[300], res[300];
vector<int> adj[300];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0, x; j < n; j++) {
            scanf("%1d", &x);
            if (x) adj[j].push_back(i), ind[i]++;
        }
    }
    priority_queue<int> pq;
    for (int i = 0; i < n; i++) if (!ind[i]) pq.push(i);
    int m = n;
    while (!pq.empty()) {
        int h = pq.top();
        pq.pop();
        res[h] = m--;
        for (auto it : adj[h])
            if (!--ind[it]) pq.push(it);
    }
    if (m) puts("-1");
    else for (int i = 0; i < n; i++) printf("%d ", res[i]);
    return 0;
}

14226번: 이모티콘

https://www.acmicpc.net/problem/14226

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int dp[1200][20], s;
int f(int x, int y) {
    if (x == 0 || y > 19) return int(1e9);
    if (x == s) return 0;
    if (dp[x][y] != -1) return dp[x][y];
    int t = f(x - 1, y + 1) + 1;
    for (int i = 2; i*x < 1200; i++) t = min(t, f(i*x, y) + i);
    return dp[x][y] = t;
}
int main() {
    scanf("%d", &s);
    memset(dp, -1, sizeof(dp));
    printf("%d", f(1, 0));
    return 0;
}

7687번: 지구 직육면체설

https://www.acmicpc.net/problem/7687

#include<cstdio>
#include<algorithm>
using namespace std;
int a, b, c, x, y, z;
int main() {
    while (scanf("%d%d%d%d%d%d", &a, &b, &c, &x, &y, &z), a) {
        if (!x || !y || !z) {
            printf("%d\n", x*x + y*y + z*z);
        }
        else {
            int t = 1e9;
            if (a == x) {
                t = min({ t,(x + y)*(x + y) + z*z,(x + z)*(x + z) + y*y });
                t = min({ t,(c + y)*(c + y) + (a + c - z)*(a + c - z),(b + z)*(b + z) + (a + b - y)*(a + b - y) });
            }
            if (b == y) {
                t = min({ t,(x + y)*(x + y) + z*z,(y + z)*(y + z) + x*x });
                t = min({ t,(a + z)*(a + z) + (b + a - x)*(b + a - x),(c + x)*(c + x) + (b + c - z)*(b + c - z) });
            }
            if (c == z) {
                t = min({ t,(z + y)*(z + y) + x*x,(x + z)*(x + z) + y*y });
                t = min({ t,(a + y)*(a + y) + (c + a - x)*(c + a - x),(b + x)*(b + x) + (c + b - y)*(c + b - y) });
            }
            printf("%d\n", t);
        }
    }
    return 0;
}

1020번: 디지털 카운터

https://www.acmicpc.net/problem/1020

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int s[] = { 6,2,5,5,4,5,6,3,7,5,6 };
int a[15], n, d;
ll num, po = 1, dp[2][16][106];
int main() {
    while (~scanf("%1d", a + n)) {
        num = num * 10 + a[n];
        d += s[a[n++]];
        po *= 10;
    }
    fill(&dp[0][0][0], &dp[1][15][106], po * 2);
    dp[0][n][0] = 0;
    long long p = 1;
    for (int i = n; i--; p *= 10) {
        for (int j = 0; j < 10; j++) {
            for (int k = s[j]; k < 106; k++) {
                dp[0][i][k] = min(dp[0][i][k], dp[0][i + 1][k - s[j]] + j*p);
                if (j>a[i]) dp[1][i][k] = min(dp[1][i][k], dp[0][i + 1][k - s[j]] + j*p);
            }
        }
        for (int j = s[a[i]]; j < 106; j++) dp[1][i][j] = min(dp[1][i][j], dp[1][i + 1][j - s[a[i]]] + a[i] * p);
    }
    printf("%lld", min(dp[0][0][d] + po, dp[1][0][d]) - num);
    return 0;
}

4005번: 테이블 색칠하기

https://www.acmicpc.net/problem/4005

#include<cstdio>
#include<vector>
#define mod int(1e9)
using namespace std;
const int MX = 1e5;
int n, m, k, r = 1, vis[MX + 1], c[MX + 1], ck[MX + 1], tcnt, ccnt;
vector<pair<int, int> > row[MX + 1];
vector<int> col[MX + 1];
void f(int h) {
    if (vis[h]) return;
    vis[h] = 1;
    int cnt = 0, tot = 0;
    for (auto it : row[h]) if (ck[it.first]) {
        tot++;
        int ans = it.second ^ (h&it.first & 1);
        if (c[it.first] ^ ans) cnt++;
    }
    if (0 < cnt && cnt < tot) r = 0;
    for (auto it : row[h]) if (!ck[it.first]) {
        tcnt++;
        ck[it.first] = 1;
        c[it.first] = it.second^cnt > 0 ^ (h&it.first & 1);
    }
    for (auto it : row[h]) if (ck[it.first] == 1) {
        ck[it.first]++;
        for (int t : col[it.first]) f(t);
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &k);
    while (k--) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        row[a].push_back({ b,c });
        col[b].push_back(a);
    }
    ccnt = m - 1;
    for (int i = 1; i <= n; i++) {
        tcnt = 0;
        f(i);
        if (tcnt) ccnt -= tcnt - 1;
    }
    while (ccnt--) r = (r * 2) % mod;
    for (int i = 1; i <= n; i++) if (row[i].empty()) r = (r * 2) % mod;
    printf("%d", r);
    return 0;
}

4015번: DNA

https://www.acmicpc.net/problem/4015

$O(mk)$

#include<cstdio>
int m, k, s[50001];
long long r, dp[50001][11][5];
char g[] = " ACGT";
int main() {
    scanf("%d%d%lld", &m, &k, &r);
    for (int i = 0; i < m; i++) {
        char x;
        scanf(" %c", &x);
        if (x == 'A') s[i] = 1;
        if (x == 'C') s[i] = 2;
        if (x == 'G') s[i] = 3;
        if (x == 'T') s[i] = 4;
    }
    dp[m][1][4] = 1;
    for (int i = m; i--;) {
        for (int j = 1; j <= k; j++) {
            for (int l = 1; l <= 4; l++) if (!s[i] || s[i] == l) {
                for (int n = 1; n < l; n++) dp[i][j][l] += dp[i + 1][j - 1][n];
                for (int n = l; n <= 4; n++) dp[i][j][l] += dp[i + 1][j][n];
            }
        }
    }
    for (int i = m; i--;)
        for (int j = 1; j <= k; j++)
            for (int l = 1; l <= 4; l++) dp[i][j][l] += dp[i][j - 1][l];
    for (int i = 0; i < m; i++) {
        if (s[i]) putchar(g[s[i]]);
        else {
            for (int j = 1; j <= 4; j++) {
                int t = 0;
                if (i&&s[i - 1]>j) t = 1;
                if (dp[i][k - t][j] < r) r -= dp[i][k - t][j];
                else {
                    s[i] = j;
                    putchar(g[j]);
                    break;
                }
            }
        }
        if (i&&s[i - 1] > s[i]) k--;
    }
    return 0;
}

2797번: TRAMPOLIN

https://www.acmicpc.net/problem/2797

#include<cstdio>
#include<algorithm>
using namespace std;
const int MXN = 3e5;
int n, k, a[MXN], ck[MXN], cnt, dp[2][MXN];
char s[MXN + 1];
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    scanf("%s", s);
    for (int i = 0, t = 1e9; i < n; i++) {
        if (s[i] == 'T') t = 0;
        if (a[i] >= t) {
            t = a[i];
            cnt += !ck[i];
            ck[i] = 1;
        }
        else t = 1e9;
    }
    for (int i = n, t = 1e9; i--;) {
        if (s[i] == 'T') t = 0;
        if (a[i] >= t) {
            t = a[i];
            cnt += !ck[i];
            ck[i] = 1;
        }
        else t = 1e9;
    }
    dp[0][0] = !ck[0];
    for (int i = 1; i < n; i++) {
        if (!ck[i]) dp[0][i] = (a[i - 1] <= a[i])*dp[0][i - 1] + 1;
    }
    dp[1][n - 1] = !ck[n - 1];
    for (int i = n - 1; i--;) {
        if (!ck[i]) dp[1][i] = (a[i + 1] <= a[i])*dp[1][i + 1] + 1;
    }
    k--;
    if (ck[k]) {
        printf("%d", cnt + *max_element(dp[0], dp[2]));
    }
    else {
        int r = 0;
        for (int i = k; i >= 0 && a[i] == a[k]; i--) r = max({ r,dp[0][i],dp[1][i] });
        for (int i = k; i < n&&a[i] == a[k]; i++) r = max({ r,dp[0][i],dp[1][i] });
        printf("%d", r);
    }
    return 0;
}

2419번: Beetle

https://www.acmicpc.net/problem/2419

#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, x[301], dp[2][301][301][301], ck[2][301][301][301];
int f(int d, int l, int r, int c) {
    if (!c) return (r - l)*m;
    if (ck[d][l][r][c]) return dp[d][l][r][c];
    ck[d][l][r][c] = 1;
    int t = 0;
    if (l) t = f(0, l - 1, r, c - 1) - (d ? x[r] - x[l - 1] : x[l] - x[l - 1])*c;
    if (r < n) t = max(t, f(1, l, r + 1, c - 1) - (d ? x[r + 1] - x[r] : x[r + 1] - x[l])*c);
    return dp[d][l][r][c] = t;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", x + i);
    sort(x, x + 1 + n);
    int s = lower_bound(x, x + 1 + n, 0) - x, res = 0;
    for (int i = 1; i <= n; i++) res = max({ res,f(0,s,s,i),f(1,s,s,i) });
    printf("%d", res);
    return 0;
}

1180번: Cactus Reloaded

https://www.acmicpc.net/problem/1180

#include<cstdio>
#include<vector>
#include<deque>
#include<algorithm>
using namespace std;
const int MXN = 5e4;
int n, m, vis[MXN + 1], res, d[MXN + 1], cks[MXN + 1];
vector<int> adj[MXN + 1], stk;
vector<vector<int> > cyc[MXN + 1];
void f(int h, int p) {
    vis[h]++;
    cks[h]++;
    stk.push_back(h);
    for (auto it : adj[h]) if (it^p) {
        if (cks[it]) {
            vector<int> v = { 0 };
            for (int i = stk.size(); stk[--i] ^ it;) v.push_back(stk[i]), vis[stk[i]]++;
            cyc[it].push_back(v);
        }
        if (!vis[it]) f(it, h);
    }
    if (p&&vis[h] == 1) cyc[p].push_back({ 0,h });
    stk.pop_back();
    cks[h]--;
}
void g(int h) {
    int m1 = 0, m2 = 0;
    for (auto c : cyc[h]) {
        deque<pair<int, int> > dq;
        for (int i = 1; i < c.size(); i++) {
            g(c[i]);
            m2 = max(m2, d[c[i]] + min(i, int(c.size()) - i));
        }
        for (int i = c.size() / 2; i < c.size(); i++) {
            while (!dq.empty() && dq.back().second < d[c[i]] + c.size() - i) dq.pop_back();
            dq.push_back({ i - c.size(), d[c[i]] + c.size() - i });
        }
        for (int i = 0; i < c.size(); i++) {
            if (i - dq.front().first>c.size() / 2) dq.pop_front();
            res = max(res, d[c[i]] + dq.front().second + i);
            while (!dq.empty() && dq.back().second < d[c[i]] - i) dq.pop_back();
            dq.push_back({ i,d[c[i]] - i });
        }
        if (m1 < m2) swap(m1, m2);
    }
    res = max(res, m1 + m2);
    d[h] = m1;
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0, k, x, y; i < m; i++) {
        scanf("%d%d", &k, &x);
        for (int i = 1; i < k; i++) {
            scanf("%d", &y);
            adj[x].push_back(y);
            adj[y].push_back(x);
            x = y;
        }
    }
    f(1, 0);
    g(1);
    printf("%d", res);
    return 0;
}

7621번: Fish Catch

https://www.acmicpc.net/problem/7621

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int MXN = 1e3;
typedef long long ll;
int cx, cy, n, k, idx[MXN], ord[MXN];
ll ax[MXN], ay[MXN], bx[MXN], by[MXN];
double res;
vector<pair<double, pair<int, int> > > v;
pair<double, double> value(ll a, ll b, ll c) {
    if (!a) {
        if (!b) return{ -1,-1 };
        return{ -c*1.0 / b,-1 };
    }
    ll d = b*b - 4 * a*c;
    if (d < 0) return{ -1,-1 };
    return{ (sqrt(d) - b) / a / 2 ,(-sqrt(d) - b) / a / 2 };
}
double rad(int i, double t) {
    return sqrt((ax[i] + bx[i] * t)*(ax[i] + bx[i] * t) + (ay[i] + by[i] * t)*(ay[i] + by[i] * t));
}
int main() {
    scanf("%d%d%d%d", &cx, &cy, &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%lld%lld%lld%lld", ax + i, ay + i, bx + i, by + i);
        bx[i] -= ax[i];
        by[i] -= ay[i];
        ax[i] -= cx;
        ay[i] -= cy;
        for (int j = 0; j < i; j++) {
            pair<double, double> t = value(bx[i] * bx[i] + by[i] * by[i] - bx[j] * bx[j] - by[j] * by[j],
                2 * (ax[i] * bx[i] + ay[i] * by[i] - ax[j] * bx[j] - ay[j] * by[j]),
                ax[i] * ax[i] + ay[i] * ay[i] - ax[j] * ax[j] - ay[j] * ay[j]);
            if (t.first > 0) v.push_back({ t.first,{ j,i } });
            if (t.second > 0) v.push_back({ t.second,{ j,i } });
        }
        ord[i] = i;
        pair<double, double> t = value(0, bx[i] * bx[i] + by[i] * by[i], ax[i] * bx[i] + ay[i] * by[i]);
        if (t.first > 0) v.push_back({ t.first,{ i,i } });
    }
    sort(ord, ord + n, [](int u, int v) {return rad(u, 0) < rad(v, 0) || rad(u, 0) == rad(v, 0) && rad(u, 1e-9)<rad(v, 1e-9); });
    sort(v.begin(), v.end());
    res = rad(ord[k - 1], 0);
    for (int i = 0; i < n; i++) idx[ord[i]] = i;
    for (auto it : v) {
        swap(ord[idx[it.second.first]], ord[idx[it.second.second]]);
        swap(idx[it.second.first], idx[it.second.second]);
        res = min(res, rad(ord[k - 1], it.first));
    }
    printf("%lf", res);
    return 0;
}

피드 구독하기: 글 ( Atom )

페이지