oj.uz

Submission #1032817

# Submission time Handle Problem Language Result Execution time Memory
1032817 2024-07-24T09:11:56 Z 정민찬(#10967) Popeala (CEOI16_popeala) C++17
0 / 100
 172 ms 36180 KB 
#include <bits/stdc++.h>

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

const int inf = 2e9;

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

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL);
    int n, t, s;
    cin >> n >> t >> s;
    for (int i=1; i<=t; i++) {
        cin >> p[i];
        S[i] = S[i-1] + p[i];
    }
    for (int i=1; i<=n; i++) {
        string temp;
        cin >> temp;
        for (int j=1; j<=t; j++) {
            R[i][j] = temp[j-1] - '0';
        }
    }
    for (int i=0; i<=s; i++) {
        for (int 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 (int i=1; i<=t; i++) {
        vector<int> idx;
        for (int 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 (int j=2; j<=s; j++) {
            dp[i][j] = inf;
            if (j > i) break;
            for (int k=0; k<=idx.size(); k++) {
                int nxt = k == idx.size() ? i+1 : idx[k];
                
                int 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;
                int val = st[j-1][k][it];
                dp[i][j] = min(dp[i][j], dp[val][j-1] + (S[i] - S[val]) * k);
            }
        }
        for (int j=1; j<=s; j++) {
            for (int 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 (int i=1; i<=s; i++) {
        cout << dp[t][i] << '\n';
    }
}

Compilation message

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

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Incorrect 1 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 6172 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 172 ms 36180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Incorrect 1 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -