oj.uz

Submission #91007

# Submission time Handle Problem Language Result Execution time Memory
91007 2018-12-25T14:54:41 Z Flying_dragon_02 Popeala (CEOI16_popeala) C++14
0 / 100
 29 ms 3064 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair

typedef pair<int, int> ii;

const int N = 20005;

const int M = 55;

int n, t, s, last[M], used[N];

long long sum[N], dp[M][N], p[N], mn[M][N];

const long long inf = 1e14;

vector<int> pos;

char c[M][N];

void update(int x) {
    for(int i = 0; i <= n; i++) {
        for(int j = 1; j <= t; j++) {
            mn[i][j] = dp[x][j] - i * sum[j];
            if(j >= 2)
                mn[i][j] = min(mn[i][j], mn[i][j - 1]);
        }
    }
}

int main() {
    cin.tie(0), ios::sync_with_stdio(0);
    //freopen("test.inp", "r", stdin);
    cin >> n >> t >> s;
    for(int i = 1; i <= t; i++) {
        cin >> p[i];
        sum[i] = p[i];
    }
    for(int i = 1; i <= t; i++)
        sum[i] += sum[i - 1];
    for(int i = 1; i <= n; i++) {
        last[i] = INT_MAX;
        for(int j = 1; j <= t; j++)
            cin >> c[i][j];
        for(int j = 1; j <= t; j++) {
            if(c[i][j] == '0') {
                last[i] = j;
                break;
            }
        }
        if(last[i] != INT_MAX) {
            used[last[i]]++;
            pos.pb(last[i]);
        }
    }
    sort(pos.begin(), pos.end());
    pos.erase(unique(pos.begin(), pos.end()), pos.end());
    int pter = 0;
    for(int i = 1; i <= s; i++) {
        for(int j = 1; j <= t; j++)
            dp[i][j] = inf;
    }
    for(int i = 1; i <= s; i++) {
        pter = 0;
        for(int j = i; j <= t; j++) {
            while(pter < pos.size() && pos[pter] <= j) pter++;
            if(used[j] == 0)
                dp[i][j] = min(dp[i][j], mn[n][j - 1] + n * sum[j]);
            int cnt = n;
            for(int k = min(pter, (int)(pos.size()) - 1); k >= 0; k--) {
                int r = pos[k];
                if(r <= j) {
                    cnt -= used[r];
                    dp[i][j] = min(dp[i][j], mn[cnt][r - 1] + cnt * sum[j]);
                }
            }
        }
        update(i);
    }
    for(int i = 1; i <= s; i++)
        cout << dp[i][t] << "\n";
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:71:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             while(pter < pos.size() && pos[pter] <= j) pter++;
                   ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 760 KB Output isn't correct

Subtask #2
0 / 9.0

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

Subtask #3
0 / 9.0

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

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 760 KB Output isn't correct