Submission #1262732

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262732		biank	조교 (CEOI16_popeala)	C++20	100 / 100	1024 ms	17124 KiB

popeala

#include <bits/stdc++.h>
 
using namespace std;
 
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
 
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
 
using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;
using ii = pair<int, int>;
using vii = vector<ii>;
 
#define fst first
#define snd second
 
#define pb push_back
#define eb emplace_back

const ll INF = 1e18;

template<typename T>
void chmin(T &x, T v) {
    if (v < x) x = v;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n, t, s;
    cin >> n >> t >> s;
    vi points(t);
    forn(i, t) cin >> points[i];
    vll pref(t + 1);
    pref[0] = 0LL;
    forn(i, t) pref[i + 1] = pref[i] + points[i];
    vector<vi> results(n, vi(t));
    forn(i, n) {
        string r; cin >> r;
        forn(j, t) results[i][j] = r[j] - '0'; 
    }
    vector<vi> nextZero(n, vi(t, t));
    forn(i, n) {
        forn(j, t) if (!results[i][j]) {
            nextZero[i][j] = j;
        }
        dforn(j, t - 1) if (results[i][j]) {
            nextZero[i][j] = nextZero[i][j + 1];
        }
    }
    vector<vll> dp(t + 1, vll(s + 1, INF));
    dp[t][0] = 0;
    forn(k, s) {
        vll best(n + 1, INF);
        vi prevX(n + 1, t);
        dforn(i, t) {
            vi x(n + 1);
            forn(j, n) x[j] = nextZero[j][i];
            x[n] = i;
            sort(all(x));
            forn(cnt, n + 1) {
                forsn(j, x[cnt] + 1, prevX[cnt] + 1) {
                    chmin(best[cnt], dp[j][k] + (n - cnt) * pref[j]);
                }
            }
            forn(cnt, n + 1) {
                chmin(dp[i][k + 1], best[cnt] - (n - cnt) * pref[i]);
            }
            prevX = x;
        }
    }
    forsn(i, 1, s + 1) cout << dp[0][i] << '\n';
    
    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74