oj.uz

Submission #23733

# Submission time Handle Problem Language Result Execution time Memory
23733 2017-05-24T10:40:10 Z gs14004 Popeala (CEOI16_popeala) C++11
100 / 100
 1093 ms 27908 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

int m, n, k, a[20005];
char buf[20005];
int low[20005][55];
lint dp[55][20005];

lint getmin(lint *dp, int coeff, int s, int e){
	lint ret = 1e18;
	for(int i=s; i<=e; i++){
		ret = min(ret, dp[i] - coeff * a[i]);
	}
	return ret;
}

struct rmin{
	lint dq[20005];
	int idx[20005];
	int s, e, x;
	int rs, re;
	void init(int coeff){
		s = e = rs = re = 0;
		re = -1;
		x = coeff;
	}
	lint query(lint *dp, int qs, int qe){
		while(re < qe){
			re++;
			while(s < e && dq[e-1] >= dp[re] - 1ll * x * a[re]){
				e--;
			}
			dq[e] = dp[re] - 1ll * x * a[re];
			idx[e] = re;
			e++;
		}
		rs = qs;
		while(s < e && idx[s] < qs){
			s++;
		}
		if(s == e) return 1e18;
		return dq[s];
	}
}rmin[55];

int main(){
	cin >> m >> n >> k;
	for(int i=1; i<=n; i++){
		scanf("%d",&a[i]);
		a[i] += a[i-1];
	}
	for(int i=0; i<m; i++){
		scanf("%s", buf + 1);
		int pos = 0;
		for(int j=1; j<=n; j++){
			if(buf[j] == '0') pos = j;
			low[j][i] = pos;
		}
	}
	for(int i=1; i<=n; i++){
		sort(low[i], low[i] + m);
		low[i][m] = i;
	}
	memset(dp, 0x3f, sizeof(dp));
	dp[0][0] = 0;
	for(int i=1; i<=k; i++){
		for(int j=0; j<=m; j++){
			rmin[j].init(j);
		}
		// 0 ~ m deque structure init
		for(int j=1; j<=n; j++){
			dp[i][j] = rmin[0].query(dp[i-1], 0, low[j][0] - 1);
			for(int k=0; k<m; k++){
				dp[i][j] = min(dp[i][j], rmin[k+1].query(dp[i-1], low[j][k], low[j][k+1] - 1) + 1ll * (k+1) * a[j]);
			}
		}
		printf("%lld\n", dp[i][n]);
	}
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:52:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
                    ^
popeala.cpp:56:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", buf + 1);
                       ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 27908 KB Output is correct
2 Correct 0 ms 27908 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 27908 KB Output is correct
2 Correct 23 ms 27908 KB Output is correct
3 Correct 26 ms 27908 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 27908 KB Output is correct
2 Correct 183 ms 27908 KB Output is correct
3 Correct 219 ms 27908 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 27908 KB Output is correct
2 Correct 0 ms 27908 KB Output is correct
3 Correct 33 ms 27908 KB Output is correct
4 Correct 23 ms 27908 KB Output is correct
5 Correct 26 ms 27908 KB Output is correct
6 Correct 143 ms 27908 KB Output is correct
7 Correct 183 ms 27908 KB Output is correct
8 Correct 219 ms 27908 KB Output is correct
9 Correct 303 ms 27908 KB Output is correct
10 Correct 453 ms 27908 KB Output is correct
11 Correct 903 ms 27908 KB Output is correct
12 Correct 863 ms 27908 KB Output is correct
13 Correct 1086 ms 27908 KB Output is correct
14 Correct 1093 ms 27908 KB Output is correct
15 Correct 1079 ms 27908 KB Output is correct