oj.uz

답안 #1032818

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1032818 2024-07-24T09:13:04 Z 정민찬(#10967) 조교 (CEOI16_popeala) C++17
0 / 100
 219 ms 66640 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

const ll inf = 2e18;

ll p[20010];
ll R[51][20010];
ll S[20010];
ll l[20010];
ll dp[20010][51];
vector<ll> st[51][51];
ll mn[20010];

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL);
    ll n, t, s;
    cin >> n >> t >> s;
    for (ll i=1; i<=t; i++) {
        cin >> p[i];
        S[i] = S[i-1] + p[i];
    }
    for (ll i=1; i<=n; i++) {
        string temp;
        cin >> temp;
        for (ll j=1; j<=t; j++) {
            R[i][j] = temp[j-1] - '0';
        }
    }
    for (ll i=0; i<=s; i++) {
        for (ll j=0; j<=n; j++) {
            st[i][j].push_back(0);
        }
        dp[0][i] = inf;
    }
    dp[0][0] = 0;
    memset(l, -1, sizeof(l));
    for (ll i=1; i<=t; i++) {
        vector<ll> idx;
        for (ll j=1; j<=n; j++) {
            if (R[j][i] == 0) l[j] = -1;
            else if (l[j] == -1) l[j] = i;
            if (l[j] != -1) idx.push_back(l[j]);
        }
        sort(idx.begin(), idx.end());
        for (auto &x : idx) {
            if (x == 1) dp[i][1] += S[i];
            else break;
        }
        for (ll j=2; j<=s; j++) {
            dp[i][j] = inf;
            if (j > i) break;
            for (ll k=0; k<=idx.size(); k++) {
                ll nxt = k == idx.size() ? i+1 : idx[k];
                
                ll it = lower_bound(st[j-1][k].begin(), st[j-1][k].end(), nxt-1) - st[j-1][k].begin() - 1;
                if (it == -1) continue;
                ll val = st[j-1][k][it];
                dp[i][j] = min(dp[i][j], dp[val][j-1] + (S[i] - S[val]) * k);
            }
        }
        for (ll j=1; j<=s; j++) {
            for (ll k=0; k<=n; k++) {
                if (dp[st[j][k].back()][j] - S[st[j][k].back()] * k > dp[i][j] - S[i] * k) {
                    st[j][k].push_back(i);
                }
            }
        }
    }
    for (ll i=1; i<=s; i++) {
        cout << dp[t][i] << '\n';
    }
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:56:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |             for (ll k=0; k<=idx.size(); k++) {
      |                          ~^~~~~~~~~~~~
popeala.cpp:57:28: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |                 ll nxt = k == idx.size() ? i+1 : idx[k];
      |                          ~~^~~~~~~~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 604 KB Output is correct
2 Incorrect 1 ms 860 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 11612 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 219 ms 66640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 604 KB Output is correct
2 Incorrect 1 ms 860 KB Output isn't correct
3 Halted 0 ms 0 KB -