Submission #91007

#	Time	Username	Problem	Language	Result	Execution time	Memory
91007		Flying_dragon_02	Popeala (CEOI16_popeala)	C++14	0 / 100	29 ms	3064 KiB

popeala

#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 (stderr)

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
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 74