10월 개인과제(최승주)

1039.cpp

#include <cstdio>
#include <string>
#include <queue>
#include <algorithm>
 
using namespace std;
 
bool chk[1000003][13];
 
int value(string a){
 
    int s = a.size();
    int v = 0;
 
    for(int i=0; i<s; i++){
        v = v * 10 + a[i] - '0';
    }
 
    return v;
 
}
 
string pars(int v){
 
    string ret;
 
    while(v){
        ret += (char)(v % 10 + '0');
        v /= 10;
    }
 
    reverse(ret.begin(), ret.end());
 
    return ret;
 
}
 
int main(){
 
    int s, k;
    scanf("%d %d", &s, &k);
 
    queue < pair<int,int> > q;
 
    chk[s][0] = true;
    q.emplace(s, 0);
 
    int ans = -1;
 
    while(!q.empty()){
 
        pair <int,int> f = q.front(); q.pop();
 
        if(f.second == k)ans = max(ans, f.first);
        else{
 
            string a = pars(f.first);
 
            int l = a.size();
            int m = f.second + 1;
 
            for(int i=0; i<l; i++){
                for(int j=i+1; j<l; j++){
 
                    swap(a[i], a[j]);
 
                    if(a[0] != '0'){
                        int p = value(a);
                        if(chk[p][m]){
                            swap(a[i], a[j]);
                            continue;
                        }
                        chk[p][m] = true;
                        q.emplace(p, m);
                    }
 
                    swap(a[i], a[j]);
 
                }
            }
 
        }
 
    }
 
    printf("%d\n", ans);
 
}

11562.cpp

#include <cstdio>
#include <limits.h>
#include <algorithm>
 
using namespace std;
 
int d[253][253];
 
int main(){
 
    int n, m;
    scanf("%d %d", &n, &m);
 
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++)d[i][j] = INT_MAX;
        d[i][i] = 0;
    }
 
    for(int i=1; i<=m; i++){
        int a, b, t;
        scanf("%d %d %d", &a, &b, &t);
 
        if(t)d[a][b] = d[b][a] = 0;
        else
            d[a][b] = 0, d[b][a] = 1;
    }
 
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            if(d[i][k] == INT_MAX)continue;
            for(int j=1; j<=n; j++){
                if(d[k][j] == INT_MAX)continue;
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
 
    int q;
    scanf("%d", &q);
 
    while(q--){
        int a, b;
        scanf("%d %d", &a, &b);
 
        printf("%d\n", d[a][b]);
    }
 
}

11881.cpp

#include <cstdio>
 
#include <vector>
#include <map>
#include <algorithm>
 
using ll = long long;
 
const ll lmod = 1000000007;
 
using namespace std;
 
int main(){
 
    int n;
    scanf("%d", &n);
 
    vector <int> v(n);
 
    map <int, int> c;
 
    for(int i=0; i<n; i++){
        scanf("%d", &v[i]);
        c[v[i]]++;
    }
 
    sort(v.begin(), v.end());
 
    v.resize(unique(v.begin(), v.end()) - v.begin());
 
    vector <ll> lsum(v.size()), rsum(v.size());
 
    for(int i=0; i<v.size(); i++){
        lsum[i] = ((ll)v[i] * c[v[i]]) % lmod;
        if(i){
            lsum[i] += lsum[i-1];
            lsum[i] %= lmod;
        }
    }
 
    for(int i=v.size()-1; i>=0; i--){
        rsum[i] = ((ll)v[i] * c[v[i]]) % lmod;
        if(i != v.size()-1){
            rsum[i] += rsum[i+1];
            rsum[i] %= lmod;
        }
    }
 
    ll ans = 0;
 
    for(int i=1; i<=v.size()-2; i++){
        ll cnt = (lsum[i] - lsum[i-1] + lmod) % lmod;
        ans += (((cnt * lsum[i-1]) % lmod) * rsum[i+1]) % lmod;
        ans %= lmod;
    }
 
    printf("%lld\n", ans);
 
}

13334.cpp

#include <cstdio>
#include <algorithm>
using namespace std;
 
#define le(i) (i<<1)
#define ri(i) ((i<<1)|1)
 
using ll = long long;
 
int k;
ll t[1<<22];
 
ll ans = 0;
 
ll son(int c){
 
    if(c > k)return 0LL;
 
    ll l = son(le(c));
    ll r = son(ri(c));
 
    ans += t[c] + abs(l-r);
 
    return max(l, r) + t[c];
 
}
 
int main(){
 
    int n;
    scanf("%d", &n);
 
    k = (1<<(n+1))-1;
 
    for(int i=2; i<=k; i++)scanf("%lld", &t[i]);
 
    son(1);
 
    printf("%lld\n", ans);
 
}

13397.cpp

#include <cstdio>
#include <algorithm>
 
using namespace std;
 
int e[10003];
 
int main(){
 
    int n, k;
    scanf("%d %d", &n, &k);
 
    for(int i=1; i<=n; i++)scanf("%d", &e[i]);
 
    int l = 0, r = 10000, m;
 
    int ans = 10000;
 
    while(l <= r){
 
        m = (l+r) >> 1;
 
        int c = 1;
        int le = e[1], ri = e[1];
 
        for(int i=2; i<=n; i++){
 
            int nle = le, nri = ri;
 
            nle = min(nle, e[i]);
            nri = max(nri, e[i]);
 
            if(nri - nle > m){
                le = ri = e[i];
                c++;
            }else{
                le = nle, ri = nri;
            }
 
        }
 
        if(c <= k){
            ans = min(ans, m);
            r = m - 1;
        }else{
            l = m + 1;
        }
 
    }
 
    printf("%d\n", ans);
 
}

1415.cpp

#include <cstdio>
#include <algorithm>
#include <map>
#include <vector>
 
using ll = long long;
 
using namespace std;
 
int n;
 
ll dp[2][500002][2];
 
bool notPrime[500003] = {true, true};
 
int main(){
 
    scanf("%d", &n);
 
    int tot = 0;
 
    map <int,int> exist;
    vector <int> val, cnt;
    int top = 0;
 
    for(int i=0; i<n; i++){
        int e;
        scanf("%d", &e);
        tot += e;
        if(exist.find(e) == exist.end()){
            exist[e] = top++;
            val.push_back(e);
            cnt.push_back(0);
        }
        cnt[exist[e]]++;
    }
 
    for(int i=2; i*i <= tot; i++){
        if(!notPrime[i]){
            for(int j=i*i; j<=tot; j+=i)notPrime[j] = true;
        }
    }
 
    n = top;
 
    // use toggle
     
    ll ans = 0;
    
    dp[0][0][0] = 1;
 
    for(int i=0; i<n; i++){
        int p = i&1;
        int q = 1^p;
        for(int j=0; j<=tot; j++){
            dp[q][j][0] = dp[p][j][0] + dp[p][j][1];
            dp[q][j][1] = 0;
        }
        for(int j=0; j<tot; j++){
            for(int k=1; k<=cnt[i]; k++){
                int v = k*val[i]+j;
                if(v > tot)break;
                dp[q][v][1] += dp[q][j][0];
            }
        }
        for(int j=2; j<=tot; j++){
            if(!notPrime[j])ans += dp[q][j][1];
        }
    }
 
    printf("%lld\n", ans);
 
}

1733.cpp

#include <cstdio>
#include <vector>
#include <queue>
 
using namespace std;
 
// from https://github.com/kcm1700/algorithms
// in: n, m, graph
// out: match, matched
// vertex cover: (reached[0][left_node] == 0) || (reached[1][right_node] == 1)
struct BipartiteMatching
{
    int n, m;
    vector<vector<int> > graph;
    vector<int> matched, match;
    vector<int> edgeview;
    vector<int> level;
    vector<int> reached[2];
    BipartiteMatching(int n, int m) : n(n), m(m), graph(n), matched(m, -1), match(n, -1) {}
 
    bool assignLevel()
    {
        bool reachable = false;
        level.assign(n, -1);
        reached[0].assign(n, 0);
        reached[1].assign(m, 0);
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (match[i] == -1) {
                level[i] = 0;
                reached[0][i] = 1;
                q.push(i);
            }
        }
        while (!q.empty()) {
            auto cur = q.front(); q.pop();
            for (auto adj : graph[cur]) {
                reached[1][adj] = 1;
                auto next = matched[adj];
                if (next == -1) {
                    reachable = true;
                }
                else if (level[next] == -1) {
                    level[next] = level[cur] + 1;
                    reached[0][next] = 1;
                    q.push(next);
                }
            }
        }
        return reachable;
    }
 
    int findpath(int nod) {
        for (int &i = edgeview[nod]; i < graph[nod].size(); i++) {
            int adj = graph[nod][i];
            int next = matched[adj];
            if (next >= 0 && level[next] != level[nod] + 1) continue;
            if (next == -1 || findpath(next)) {
                match[nod] = adj;
                matched[adj] = nod;
                return 1;
            }
        }
        return 0;
    }
 
    int solve()
    {
        int ans = 0;
        while (assignLevel()) {
            edgeview.assign(n, 0);
            for (int i = 0; i < n; i++)
                if (match[i] == -1)
                    ans += findpath(i);
        }
        return ans;
    }
};
 
int main(){
 
    int n;
    scanf("%d", &n);
 
    BipartiteMatching btm(n+1, 1000001);
 
    for(int i=1; i<=n; i++){
        int a, b;
        scanf("%d %d", &a, &b);
 
        btm.graph[i].push_back(a);
        btm.graph[i].push_back(b);
    }
 
    if(btm.solve() == n){
        for(int i=1; i<=n; i++){
            printf("%d\n", btm.match[i]);
        }
    }else{
        printf("-1\n");
    }
 
}

2104.cpp

#include <cstdio>
#include <stack>
#include <algorithm>
 
using ll = long long;
 
using namespace std;
 
ll s[100003];
 
int main(){
     
    int n;
    scanf("%d", &n);
 
    stack < pair<int,int> > up;
 
    ll ans = 0;
 
    for(int i=1; i<=n; i++){
        int e;
        scanf("%d", &e);
 
        s[i] = s[i-1] + e;
 
        if(up.empty() || up.top().second <= e)up.emplace(i, e);
        else{
            int l = i;
            while(!up.empty() && up.top().second >= e){
                l = up.top().first;
                ans = max(ans, (ll)e * (s[i] - s[up.top().first-1]));
                ans = max(ans, (ll)up.top().second * (s[i-1] - s[up.top().first-1]));
                up.pop();
            }
            up.emplace(l, e);
        }
    }
 
    while(!up.empty()){
        ans = max(ans, (ll)up.top().second * (s[n] - s[up.top().first-1]));
        up.pop();
    }
 
    printf("%lld\n", ans);
 
}

2485.cpp

#include <cstdio>
#include <limits.h>
#include <algorithm>
 
using namespace std;
 
int gcd(int a, int b){
    int m = 1;
    while(m){
        m = a % b;
        a = b;
        b = m;
    }
    return a;
}
 
int p[100003];
 
int main(){
 
    int n;
    scanf("%d", &n);
 
    for(int i=1; i<=n; i++)scanf("%d", &p[i]);
 
    sort(p+1, p+1+n);
 
    int g = gcd(p[2]-p[1], p[3]-p[2]);
 
    for(int i=4; i<=n; i++){
        g = gcd(g, p[i]-p[i-1]);
    }
   
    int c = 0;
    for(int j=1; j<n; j++){
        int k = p[j+1] - p[j] - g;
        if(k < 0)k = 0;
        c += (k) / g;
    }

    printf("%d\n", c);
 
}

2842.cpp

#include <cstdio>
#include <queue>
#include <set>
#include <algorithm>
 
using namespace std;
 
#define x first
#define y second
 
char str[53][53];
int h[53][53];
 
int dx[] = {0, 0, -1, 1, 1, 1, -1, -1};
int dy[] = {-1, 1, 0, 0, -1, 1, -1, 1};
 
int main(){
 
    int n;
    scanf("%d", &n);
 
    pair <int,int> s;
 
    int tot = 0;
 
    for(int i=0; i<n; i++){
        scanf("%s", str[i]);
        for(int j=0; j<n; j++){
            if(str[i][j] == 'P'){
                s = {i, j};
            }else if(str[i][j] == 'K'){
                tot++;
            }
        }
    }
 
    set <int> lo;
 
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf("%d", &h[i][j]);
            lo.insert(h[i][j]);
        }
    }
 
    int l = 0, r = 1000000, m;
 
    int ans = 1000000;
 
    while(l <= r){
 
        m = (l+r) >> 1;
 
        bool pos = false;
 
        for(auto &mini : lo){
 
            queue < pair<int,int> > q;
             
            int maxi = mini + m;
 
            if(mini <= h[s.x][s.y] && h[s.x][s.y] <= maxi){
 
                vector < vector <bool> > chk;
                chk.resize(n);
                for(int j=0; j<n; j++)chk[j].resize(n, false);
 
                chk[s.x][s.y] = true;
                q.emplace(s);
 
                int cur = 0;
 
                while(!q.empty()){
 
                    pair <int,int> f = q.front(); q.pop();
 
                    for(int i=0; i<8; i++){
 
                        pair <int,int> g = {f.x + dx[i], f.y + dy[i]};
 
                        if(g.x < 0 || g.x >= n || g.y < 0 || g.y >= n)continue;
 
                        if(chk[g.x][g.y])continue;
 
                        if(mini <= h[g.x][g.y] && h[g.x][g.y] <= maxi){
 
                            if(str[g.x][g.y] == 'K'){
                                cur++;
                            }
 
                            chk[g.x][g.y] = true;
                            q.emplace(g);
 
                        }
 
                    }
 
                }
 
                if(cur == tot){
                    pos = true;
                    break;
                }
 
            }
 
        }
 
        if(pos){
            r = m - 1;
            ans = min(ans, m);
        }
        else{
            l = m + 1;
        }
 
    }
 
    printf("%d\n", ans);
 
}

3295.cpp

#include <cstdio>
#include <vector>
#include <queue>
 
using namespace std;
 
// from https://github.com/kcm1700/algorithms
// in: n, m, graph
// out: match, matched
// vertex cover: (reached[0][left_node] == 0) || (reached[1][right_node] == 1)
struct BipartiteMatching
{
    int n, m;
    vector<vector<int> > graph;
    vector<int> matched, match;
    vector<int> edgeview;
    vector<int> level;
    vector<int> reached[2];
    BipartiteMatching(int n, int m) : n(n), m(m), graph(n), matched(m, -1), match(n, -1) {}
 
    bool assignLevel()
    {
        bool reachable = false;
        level.assign(n, -1);
        reached[0].assign(n, 0);
        reached[1].assign(m, 0);
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (match[i] == -1) {
                level[i] = 0;
                reached[0][i] = 1;
                q.push(i);
            }
        }
        while (!q.empty()) {
            auto cur = q.front(); q.pop();
            for (auto adj : graph[cur]) {
                reached[1][adj] = 1;
                auto next = matched[adj];
                if (next == -1) {
                    reachable = true;
                }
                else if (level[next] == -1) {
                    level[next] = level[cur] + 1;
                    reached[0][next] = 1;
                    q.push(next);
                }
            }
        }
        return reachable;
    }
 
    int findpath(int nod) {
        for (int &i = edgeview[nod]; i < graph[nod].size(); i++) {
            int adj = graph[nod][i];
            int next = matched[adj];
            if (next >= 0 && level[next] != level[nod] + 1) continue;
            if (next == -1 || findpath(next)) {
                match[nod] = adj;
                matched[adj] = nod;
                return 1;
            }
        }
        return 0;
    }
 
    int solve()
    {
        int ans = 0;
        while (assignLevel()) {
            edgeview.assign(n, 0);
            for (int i = 0; i < n; i++)
                if (match[i] == -1)
                    ans += findpath(i);
        }
        return ans;
    }
};
 
int main(){
 
    int t;
    scanf("%d", &t);
 
    while(t--){
 
        int n, m;
        scanf("%d %d", &n, &m);
 
        BipartiteMatching btm(n, n);
 
        for(int i=0; i<m; i++){
            int a, b;
            scanf("%d %d", &a, &b);
            btm.graph[a].push_back(b);
        }
 
        printf("%d\n", btm.solve());
 
    }
 
}

9577.cpp

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
// from https://github.com/kcm1700/algorithms
// in: n, m, graph
// out: match, matched
// vertex cover: (reached[0][left_node] == 0) || (reached[1][right_node] == 1)
struct BipartiteMatching
{
    int n, m;
    vector<vector<int> > graph;
    vector<int> matched, match;
    vector<int> edgeview;
    vector<int> level;
    vector<int> reached[2];
    BipartiteMatching(int n, int m) : n(n), m(m), graph(n), matched(m, -1), match(n, -1) {}
 
    bool assignLevel()
    {
        bool reachable = false;
        level.assign(n, -1);
        reached[0].assign(n, 0);
        reached[1].assign(m, 0);
        queue<int> q;
        for (int i = 0; i < n; i++) {
            if (match[i] == -1) {
                level[i] = 0;
                reached[0][i] = 1;
                q.push(i);
            }
        }
        while (!q.empty()) {
            auto cur = q.front(); q.pop();
            for (auto adj : graph[cur]) {
                reached[1][adj] = 1;
                auto next = matched[adj];
                if (next == -1) {
                    reachable = true;
                }
                else if (level[next] == -1) {
                    level[next] = level[cur] + 1;
                    reached[0][next] = 1;
                    q.push(next);
                }
            }
        }
        return reachable;
    }
 
    int findpath(int nod) {
        for (int &i = edgeview[nod]; i < graph[nod].size(); i++) {
            int adj = graph[nod][i];
            int next = matched[adj];
            if (next >= 0 && level[next] != level[nod] + 1) continue;
            if (next == -1 || findpath(next)) {
                match[nod] = adj;
                matched[adj] = nod;
                return 1;
            }
        }
        return 0;
    }
 
    int solve()
    {
        int ans = 0;
        while (assignLevel()) {
            edgeview.assign(n, 0);
            for (int i = 0; i < n; i++)
                if (match[i] == -1)
                    ans += findpath(i);
        }
        return ans;
    }
};
 
int st[103], ed[103];
 
int main(){
 
    int t;
    scanf("%d", &t);
 
    while(t--){
 
        int n, q;
        scanf("%d %d", &n, &q);
 
        vector < vector <int> > dat;
        dat.resize(q+1);
 
        for(int i=1; i<=q; i++){
 
            scanf("%d %d", &st[i], &ed[i]);
 
            int c;
            scanf("%d", &c);
 
            while(c--){
 
                int v;
                scanf("%d", &v);
 
                dat[i].push_back(v);
 
            }
             
        }
 
        int l = 1, r = 102, m;
 
        int ans = 105;
 
        while(l <= r){
             
            m = (l+r) >> 1;
 
            BipartiteMatching btm(102, n+1);
 
            for(int i=1; i<=q; i++){
 
                for(int j=st[i]; j<ed[i]; j++){
 
                    if(j+1 > m)break;
 
                    for(auto &e : dat[i]){
                        btm.graph[j+1].push_back(e);
                    }
 
                }
 
            }
 
            if(btm.solve() == n){
                ans = min(ans, m);
                r = m - 1;
            }else{
                l = m + 1;
            }
 
        }
 
        if(ans == 105)ans = -1;
 
        printf("%d\n", ans);
 
    }
 
}