oj.uz

Submission #42467

# Submission time Handle Problem Language Result Execution time Memory
42467 2018-02-27T13:07:53 Z nonocut Popeala (CEOI16_popeala) C++14
26 / 100
 2000 ms 7768 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf = 2e9;
int n,m,s;
int a[55][20005];
int sum[20005];
int t[55];
vector<int> p[20005];
ll 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),0,last-1);
				dp[x] = min(dp[x], (ll)val*sum[x] + query(val,1,0,m,0,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:63:22: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
   printf("%d\n",dp[m]);
                      ^
popeala.cpp:28: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:31:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&val);
                         ^
popeala.cpp:37: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 760 KB Output is correct
2 Correct 4 ms 1124 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 1832 KB Output is correct
2 Correct 112 ms 1832 KB Output is correct
3 Correct 118 ms 1832 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 697 ms 4056 KB Output is correct
2 Correct 1100 ms 4436 KB Output is correct
3 Correct 1351 ms 4948 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 4 ms 1124 KB Output is correct
3 Correct 122 ms 1832 KB Output is correct
4 Correct 112 ms 1832 KB Output is correct
5 Correct 118 ms 1832 KB Output is correct
6 Correct 697 ms 4056 KB Output is correct
7 Correct 1100 ms 4436 KB Output is correct
8 Correct 1351 ms 4948 KB Output is correct
9 Execution timed out 2041 ms 7768 KB Time limit exceeded
10 Halted 0 ms 0 KB -