Submission #127256

#	Time	Username	Problem	Language	Result	Execution time	Memory
127256		win11905	Popeala (CEOI16_popeala)	C++11	17 / 100	2064 ms	8056 KiB

popeala

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

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