Submission #51869

#	Time	Username	Problem	Language	Result	Execution time	Memory
51869		chpipis	Popeala (CEOI16_popeala)	C++11	0 / 100	115 ms	2300 KiB

popeala

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define iter(v, i) for (__typeof__((v).begin()) i = (v).begin(); i != (v).end(); i++)
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

const double eps = 1e-9;
const double pi = 3.141592653589793238462;

const int inf = 2e9 + 10;

#define MAX_T 20005

int N, T, S;
int pts[MAX_T];
int res[55][MAX_T];
int dp[55][MAX_T];
int P[55][MAX_T];
char str[MAX_T];

int cost(int i, int j) {
//    if (i > j) return 200000000;
    if (i > j) return 0;
    int cnt = 0;
    for (int st = 1; st <= N; st++)
        cnt += (res[st][j] - res[st][i-1] == j - i + 1);
    //printf("for (%d, %d) cnt = %d and cost = %d\n", i, j, cnt, cnt * (pts[j] - pts[i-1]));
    return cnt * (pts[j] - pts[i-1]);
}

void solve(int k, int l1, int l2, int p1, int p2) {
    if (l1 > l2) return;

    int lm = (l1 + l2) >> 1;

    dp[k][lm] = inf;
    P[k][lm] = -1;

    for (int z = p1; z <= p2; z++) {
        if (z >= lm) break;
        int cur = dp[k-1][z] + cost(z+1, lm);
        if (cur < dp[k][lm]) {
            dp[k][lm] = cur;
            P[k][lm] = z;
        }
    }

    //printf("ans for pos %d (%d) is at pos %d of previous (j-1) dp\n", lm, k, P[k][lm]);

    if (P[k][lm] == -1) {
        solve(k, l1, lm - 1, p1, p2);
        solve(k, lm + 1, l2, p1, p2);
    }

    solve(k, l1, lm-1, p1, P[k][lm]);
    solve(k, lm+1, l2, P[k][lm], p2);
}

int main() {
    //freopen("popeala.in", "rt", stdin);
    //freopen("popeala.out", "wt", stdout);
	scanf("%d %d %d", &N, &T, &S);
    for (int i = 1; i <= T; i++) {
        scanf("%d", &pts[i]);
        pts[i] += pts[i-1];
    }
    for (int i = 1; i <= N; i++) {
        scanf(" %s", str+1);
        for (int j = 1; j <= T; j++)
            res[i][j] = res[i][j-1] + (str[j] == '1');
    }
    // for K = 1
    for (int i = 1; i <= T; i++)
        dp[1][i] = cost(1, i);
    printf("%d\n", dp[1][T]);
    /*
    for (int j = 2; j <= S; j++) {
        for (int i = 1; i <= T; i++) {
            dp[j][i] = inf;
            for (int k = j-1; k < i; k++)
                dp[j][i] = min(dp[j][i], dp[j-1][k] + cost(k+1, i));
        }
        printf("%d\n", dp[j][T]);
    }
    */
    for (int k = 2; k <= S; k++) {
        solve(k, k, T, k - 1, T);
        printf("%d\n", dp[k][T]);
    }
    return 0;
}

Compilation message (stderr)

popeala.cpp: In function 'int main()':
popeala.cpp:73:7: 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:75:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &pts[i]);
         ~~~~~^~~~~~~~~~~~~~~
popeala.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %s", str+1);
         ~~~~~^~~~~~~~~~~~~~

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