oj.uz

Submission #91012

# Submission time Handle Problem Language Result Execution time Memory
91012 2018-12-25T15:20:45 Z Flying_dragon_02 Popeala (CEOI16_popeala) C++14
100 / 100
 1342 ms 28348 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][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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 892 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1864 KB Output is correct
2 Correct 26 ms 1864 KB Output is correct
3 Correct 27 ms 2012 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 3860 KB Output is correct
2 Correct 164 ms 4940 KB Output is correct
3 Correct 201 ms 6200 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 892 KB Output is correct
3 Correct 27 ms 1864 KB Output is correct
4 Correct 26 ms 1864 KB Output is correct
5 Correct 27 ms 2012 KB Output is correct
6 Correct 128 ms 3860 KB Output is correct
7 Correct 164 ms 4940 KB Output is correct
8 Correct 201 ms 6200 KB Output is correct
9 Correct 349 ms 9236 KB Output is correct
10 Correct 572 ms 11784 KB Output is correct
11 Correct 1203 ms 23588 KB Output is correct
12 Correct 1227 ms 25160 KB Output is correct
13 Correct 1342 ms 26228 KB Output is correct
14 Correct 1334 ms 27296 KB Output is correct
15 Correct 1253 ms 28348 KB Output is correct