oj.uz

Submission #127256

# Submission time Handle Problem Language Result Execution time Memory
127256 2019-07-09T07:32:28 Z win11905 Popeala (CEOI16_popeala) C++11
17 / 100
 2000 ms 8056 KB 
#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
#define all(x) (x).begin(), (x).end()
using namespace std;

const int INF = 2e9+1;
const int N = 2e4+5;

int n, t, s;
char inp[55][N];
int far[55][N];
int score[N];
int dp[55][N];
vector<pii> add[N], del[N];
multiset<int> S[55];

int main() {
    scanf("%d %d %d", &n, &t, &s);
    for(int i = 1; i <= t; ++i) scanf("%d", score + i), score[i] += score[i-1];
    for(int i = 1; i <= n; ++i) scanf("%s", inp[i] + 1), inp[i][t+1] = '0';
    for(int i = 1; i <= n; ++i) {
        int l = 1, r = 1;
        while(l <= t) {
            if(inp[i][r] == '1') {
                r++;
                if(inp[i][r] == '0') {
                    while(l < r) far[i][l++] = r-1;
                } 
            } else l++, r++;
        }
    }
    for(int i = 1; i <= s; ++i) {
        for(int j = 0; j <= n; ++j) S[j].clear();
        for(int j = i; j <= t; ++j) {
            // add section
            if(i != 1 || (i == 1 && j == 1)) {
                map<int, int> Mp;
                int sumval = 0;
                for(int k = 1; k <= n; ++k) if(far[k][j]) Mp[far[k][j]]++, sumval++; 
                vector<pii> vec;
                for(auto x : Mp) vec.emplace_back(x);
                int pre = j;
                for(auto z : vec) {
                    int v = dp[i-1][j-1] - sumval * score[j-1];
                    add[pre].emplace_back(sumval, v);
                    del[z.x].emplace_back(sumval, v);
                    pre = z.x+1;
                    sumval -= z.y;
                }
                if(pre != t+1) add[pre].emplace_back(sumval, dp[i-1][j-1]), del[t].emplace_back(sumval, dp[i-1][j-1]);
            }
            // add section
            for(auto z : add[j]) 
                S[z.x].emplace(z.y); 
            add[j].clear();
            // compute dp section
            dp[i][j] = INF;
            for(int k = 0; k <= n; ++k) if(S[k].size()) dp[i][j] = min(dp[i][j], score[j] * k + *S[k].begin());
            // delete section
            for(auto z : del[j]) 
                S[z.x].erase(S[z.x].find(z.y));
            del[j].clear();
        }
        printf("%d\n", dp[i][t]);
    } 
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &n, &t, &s);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:21:55: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= t; ++i) scanf("%d", score + i), score[i] += score[i-1];
                                 ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:22:56: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; ++i) scanf("%s", inp[i] + 1), inp[i][t+1] = '0';
                                 ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1272 KB Output is correct
2 Correct 4 ms 1656 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 2580 KB Output is correct
2 Correct 185 ms 2552 KB Output is correct
3 Correct 190 ms 2552 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1012 ms 4768 KB Output is correct
2 Correct 1494 ms 6188 KB Output is correct
3 Execution timed out 2064 ms 8056 KB Time limit exceeded

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1272 KB Output is correct
2 Correct 4 ms 1656 KB Output is correct
3 Correct 195 ms 2580 KB Output is correct
4 Correct 185 ms 2552 KB Output is correct
5 Correct 190 ms 2552 KB Output is correct
6 Correct 1012 ms 4768 KB Output is correct
7 Correct 1494 ms 6188 KB Output is correct
8 Execution timed out 2064 ms 8056 KB Time limit exceeded