Submission #91012

#	Time	Username	Problem	Language	Result	Execution time	Memory
91012		Flying_dragon_02	Popeala (CEOI16_popeala)	C++14	100 / 100	1342 ms	28348 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][N], 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++) {
        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] = j;
            else
                last[i][j] = last[i][j - 1];
        }
    }
    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++) {
        vector<int> v;
        for(int j = i; j <= t; j++) {
            vector<int> temp;
            for(int k = 1; k <= n; k++) {
                if(last[k][j] == j)
                    temp.pb(k);
            }
            for(int k = 0; k < v.size(); k++) {
                if(last[v[k]][j] != j)
                    temp.pb(v[k]);
            }
            v = temp;
            for(int k = 0; k <= v.size(); k++) {
                //if(k != v.size())
                //cout << last[v[k]][j] << " ";
                int lef, rig;
                if(k == v.size())
                    lef = 1;
                else
                    lef = last[v[k]][j] + 1;
                if(k == 0)
                    rig = j;
                else
                    rig = last[v[k - 1]][j];
                //cout << "\nwtf\n";
                //cout << lef << " " << rig << " " << i << " " << j << " " << n - k << "\n";
                if(lef <= rig)
                    dp[i][j] = min(dp[i][j], mn[n - k][rig - 1] + (n - k) * sum[j]);
            }
            //cout << dp[i][j] << " " << "i:" << i << " " << "j:" << j << "\n";
            //cout << "\n";
        }
        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:69:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k = 0; k < v.size(); k++) {
                            ~~^~~~~~~~~~
popeala.cpp:74:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int k = 0; k <= v.size(); k++) {
                            ~~^~~~~~~~~~~
popeala.cpp:78:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(k == v.size())
                    ~~^~~~~~~~~~~
popeala.cpp:56:9: warning: unused variable 'pter' [-Wunused-variable]
     int pter = 0;
         ^~~~

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