AtCoder Beginner Contest 272（A~E）

A

void solve(int Case) {
    int n;
    cin >> n;
    vector<int>a(n);
    for (auto &i : a) cin >> i;
    cout << accumulate(all(a), 0) << nline;
}

B

const int N = 550;
int d[N][N];
void solve(int Case) {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        vector<int> v(x);
        for (auto &j : v) cin >> j;
        for (int j = 0; j < v.size(); j++) {
            for (int k = j + 1; k < v.size(); k++) {
                d[v[j]][v[k]] = 1;
            }
        }
    }
    bool ok = true;
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            ok &= d[i][j];
        }
    }
    if (ok) cout << "Yes" << nline;
    else cout << "No" << nline;

}

C

const int N = 200010;
int a[N];
void solve(int Case) {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + 1 + n);
    vector<int> v1, v2;
    for (int i = 1; i <= n; i++) {
        if (a[i] & 1) v1.push_back(a[i]);
        else v2.push_back(a[i]);
    }
    int mmax = -1;
    if (v1.size() >= 2) {
        mmax = max(mmax, v1[v1.size() - 1] + v1[v1.size() - 2]);
    }
    if (v2.size() >= 2) {
        mmax = max(mmax, v2[v2.size() - 1] + v2[v2.size() - 2]);
    }
    cout << mmax << nline;
}
 

D

using PII = pair<int, int>;
vector<PII> v;
int n, m;
bool vis[N][N];
int d[N][N];
void bfs() {
    queue<PII> q;
    q.push({1, 1});
    d[1][1] = 0;
    vis[1][1] = 1;
    while (q.size()) {
        auto [x, y] = q.front();
        q.pop();
        for (auto [dx, dy] : v) {
            int nx = x - dx, ny = y - dy;
            if (nx >= 1 and nx <= n and ny >= 1 and ny <= n) {
                if (!vis[nx][ny]) {
                    vis[nx][ny] = 1;
                    d[nx][ny] = d[x][y] + 1;
                    q.push({nx, ny});
                }
 
            }
            nx = x - dx, ny = y + dy;
            if (nx >= 1 and nx <= n and ny >= 1 and ny <= n) {
                if (!vis[nx][ny]) {
                    vis[nx][ny] = 1;
                    d[nx][ny] = d[x][y] + 1;
                    q.push({nx, ny});
                }
            }
            nx = x + dx, ny = y - dy;
            if (nx >= 1 and nx <= n and ny >= 1 and ny <= n) {
                if (!vis[nx][ny]) {
                    vis[nx][ny] = 1;
                    d[nx][ny] = d[x][y] + 1;
                    q.push({nx, ny});
                }
            }
            nx = x + dx, ny = y + dy;
            if (nx >= 1 and nx <= n and ny >= 1 and ny <= n) {
                if (!vis[nx][ny]) {
                    vis[nx][ny] = 1;
                    d[nx][ny] = d[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
 
    }
}
void solve(int Case) {
    cin >> n >> m;
    for (int i = 1; i <= 1010; i++) {
        int x = i * i;
        if (x > m) break;
        int y = m - x;
        int c = sqrt(y);
        if (c * c == y ) {
            v.push_back({i, c});
            v.push_back({c, i});
        }
    }
    memset(d, 0x3f, sizeof d);
    bfs();
    // cout << dfs(1, 2) << nline;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
 
            int x = d[i][j];
            if (x == 0x3f3f3f3f3f3f3f3f) x = -1;
            cout << x << ' ';
        }
        cout << nline;
    }
}

E

 
const int N = 200010;
int a[N];
vector<int> v;
struct T {
    int x, t;
};
vector<T> h[N];
void solve(int Case) {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] < 0) {
            int c = abs(a[i]) / i;
            if (c - 1 > N - 5) continue;
            h[max(0LL, c - 1)].push_back({a[i] + max(0LL, (c - 1)) * i, i});
        } else {
            h[0].push_back({a[i], i});
        }
    }
    vector<T> v;
    for (auto t : h[0]) v.push_back(t);
    for (int i = 1; i <= m; i++) {
        vector<T> cur;
        map<int, int> mp;
        int s = 0;
        for (auto &[x, y] : v) {
            x += y;
        }
        for (auto [x, y] : v) {
            mp[x]++;
        }
        while (mp[s]) s++;
        cout << s << nline;
        for (auto[x, y] : v) {
            if (x > n) continue;
            cur.push_back({x, y});
        }
        v = cur;
        for (auto t : h[i]) v.push_back(t);
    }
}