oj.uz

Submission #42463

# Submission time Handle Problem Language Result Execution time Memory
42463 2018-02-27T12:49:57 Z nonocut Popeala (CEOI16_popeala) C++14
17 / 100
 772 ms 4204 KB 
#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

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.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 1868 KB Output is correct
2 Correct 140 ms 1904 KB Output is correct
3 Correct 133 ms 2004 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 772 ms 4204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 764 KB Output is correct
2 Correct 3 ms 1248 KB Output is correct
3 Correct 145 ms 1868 KB Output is correct
4 Correct 140 ms 1904 KB Output is correct
5 Correct 133 ms 2004 KB Output is correct
6 Incorrect 772 ms 4204 KB Output isn't correct
7 Halted 0 ms 0 KB -