Submission #42463

#	Time	Username	Problem	Language	Result	Execution time	Memory
42463		nonocut	Popeala (CEOI16_popeala)	C++14	17 / 100	772 ms	4204 KiB

popeala

#include<bits/stdc++.h>
using namespace std;
const int inf = 2e9;
int n,m,s;
int a[55][20005], sum[20005];
int t[55];
vector<int> p[20005];
int dp[20005];
int tree[55][60005];
void build(int val, int pos, int l, int r) {
	if(l==r) {
		tree[val][pos] = -val*sum[l] + dp[l];
		return ;
	}
	int mid = (l+r)/2;
	build(val,pos<<1,l,mid); build(val,pos<<1|1,mid+1,r);
	tree[val][pos] = min(tree[val][pos<<1], tree[val][pos<<1|1]);
}
int query(int val, int pos, int l, int r, int x, int y) {
	if(l>r || r<x || y<l) return inf;
	if(x<=l && r<=y) return tree[val][pos];
	int mid = (l+r)/2;
	return min(query(val,pos<<1,l,mid,x,y), query(val,pos<<1|1,mid+1,r,x,y));
}
int main() {
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<=m;i++) {
        int val;
        scanf("%d",&val);
        sum[i] = sum[i-1] + val;
	}
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			char tc;
			scanf(" %c",&tc);
			a[i][j] = tc-'0';
		}
	}
	for(int x=1;x<=m;x++) {
		for(int i=1;i<=n;i++) {
			if(a[i][x]==0) t[i] = x;
			if(t[i]) p[x].push_back(t[i]);
		}
		p[x].push_back(0);
		sort(p[x].rbegin(),p[x].rend());
	}
	for(int x=1;x<=m;x++) dp[x] = inf;
	for(int val=0;val<=n;val++) build(val,1,0,m);
	for(int k=1;k<=s;k++) {
        for(int x=0;x<=m;x++) dp[x] = inf;
		for(int x=1;x<=m;x++) {
			int val = n, last = x;
			for(auto y : p[x]) {
//                printf("\t%d * %d + %d [%d, %d]\n",val,sum[x],query(val,1,0,m,y,last-1),y,last-1);
				dp[x] = min(dp[x], val*sum[x] + query(val,1,0,m,y,last-1));
				val--; last = y;
			}
//            printf("dp %d = %d\n",x,dp[x]);
		}
		for(int val=0;val<=n;val++) build(val,1,0,m);
		printf("%d\n",dp[m]);
	}
}

Compilation message (stderr)

popeala.cpp: In function 'int main()':
popeala.cpp:26:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&m,&s);
                          ^
popeala.cpp:29:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&val);
                         ^
popeala.cpp:35:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf(" %c",&tc);
                    ^

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