oj.uz

Submission #97521

# Submission time Handle Problem Language Result Execution time Memory
97521 2019-02-16T17:11:06 Z popovicirobert Popeala (CEOI16_popeala) C++14
100 / 100
 523 ms 28700 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define ld long double
// 217
// 44

using namespace std;

const ll INF = 1e15;
const int MAXN = 50;
const int MAXT = 20000;

int pts[MAXT + 1], sp[MAXT + 1];
char res[MAXN + 1][MAXT + 1];
int ind[MAXN + 1][MAXT + 1];

ll dp[2][MAXT + 1];
ll mn[2][MAXN + 1][MAXT + 1];

int main() {
    //ifstream cin("A.in");
    //ofstream cout("A.out");
    int i, j, n, t, s;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> t >> s;
    for(i = 1; i <= t; i++) {
        cin >> pts[i];
        sp[i] = sp[i - 1] + pts[i];
    }
    for(i = 1; i <= n; i++) {
        cin >> res[i] + 1;
        for(j = 1; j <= t; j++) {
            res[i][j] -= '0';
            if(res[i][j] == 0) {
                ind[i][j] = j;
            }
            else {
                ind[i][j] = ind[i][j - 1];
            }
        }
    }
    vector < vector <int> > pos(t + 1);
    for(i = 1; i <= t; i++) {
        for(j = 1; j <= n; j++) {
            pos[i].push_back(ind[j][i]);
        }
        sort(pos[i].begin(), pos[i].end());
        pos[i].push_back(i);
    }
    dp[0][0] = 0;
    for(j = 1; j <= t; j++) {
        dp[0][j] = INF;
    }
    for(int k = 1; k <= s; k++) {
        for(i = 0; i <= n; i++) {
            mn[1 - k & 1][i][0] = dp[1 - k & 1][0];
            for(j = 1; j <= t; j++) {
                mn[1 - k & 1][i][j] = min(mn[1 - k & 1][i][j - 1], dp[1 - k & 1][j] - sp[j] * i);
            }
        }
        dp[k & 1][0] = INF;
        for(j = 1; j <= t; j++) {
            dp[k & 1][j] = INF;
            for(i = 0; i < pos[j].size(); i++) {
                if(pos[j][i] > 0) {
                    dp[k & 1][j] = min(dp[k & 1][j], mn[1 - k & 1][i][pos[j][i] - 1] + sp[j] * i);
                    //cerr << pos[j][i] << " ";
                }
            }
            //cerr << " ";
            //cerr << dp[k & 1][j] << " ";
        }
        //cerr << "\n";
        cout << dp[k & 1][t] << "\n";
    }
    //cin.close();
    //cout.close();
    return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:34:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         cin >> res[i] + 1;
                ~~~~~~~^~~
popeala.cpp:59:18: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
             mn[1 - k & 1][i][0] = dp[1 - k & 1][0];
                ~~^~~
popeala.cpp:59:40: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
             mn[1 - k & 1][i][0] = dp[1 - k & 1][0];
                                      ~~^~~
popeala.cpp:61:22: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
                 mn[1 - k & 1][i][j] = min(mn[1 - k & 1][i][j - 1], dp[1 - k & 1][j] - sp[j] * i);
                    ~~^~~
popeala.cpp:61:48: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
                 mn[1 - k & 1][i][j] = min(mn[1 - k & 1][i][j - 1], dp[1 - k & 1][j] - sp[j] * i);
                                              ~~^~~
popeala.cpp:61:73: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
                 mn[1 - k & 1][i][j] = min(mn[1 - k & 1][i][j - 1], dp[1 - k & 1][j] - sp[j] * i);
                                                                       ~~^~~
popeala.cpp:67:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(i = 0; i < pos[j].size(); i++) {
                        ~~^~~~~~~~~~~~~~~
popeala.cpp:69:59: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
                     dp[k & 1][j] = min(dp[k & 1][j], mn[1 - k & 1][i][pos[j][i] - 1] + sp[j] * i);
                                                         ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 1020 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 2048 KB Output is correct
2 Correct 14 ms 1792 KB Output is correct
3 Correct 14 ms 1920 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 4088 KB Output is correct
2 Correct 80 ms 5376 KB Output is correct
3 Correct 126 ms 6876 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 1020 KB Output is correct
3 Correct 15 ms 2048 KB Output is correct
4 Correct 14 ms 1792 KB Output is correct
5 Correct 14 ms 1920 KB Output is correct
6 Correct 41 ms 4088 KB Output is correct
7 Correct 80 ms 5376 KB Output is correct
8 Correct 126 ms 6876 KB Output is correct
9 Correct 123 ms 10460 KB Output is correct
10 Correct 266 ms 13248 KB Output is correct
11 Correct 523 ms 27760 KB Output is correct
12 Correct 461 ms 28700 KB Output is correct
13 Correct 514 ms 28664 KB Output is correct
14 Correct 505 ms 28536 KB Output is correct
15 Correct 500 ms 28664 KB Output is correct