oj.uz

Submission #135642

# Submission time Handle Problem Language Result Execution time Memory
135642 2019-07-24T09:16:48 Z ekrem Popeala (CEOI16_popeala) C++17
26 / 100
 2000 ms 67704 KB 
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)>>1)
#define coc g[node][i]
#define mod 1000000007
#define inf 2000000009
#define LOGN 13
#define N 20005
using namespace std;

typedef long long ll;
typedef pair < int , int > ii;

int n, m, s, a[N], pre[N], git[N][55], dp[N][55], of[55][N][LOGN + 2], lg[N];

void bu(int d, int bas, int son, int x){
	// cout << "AMK -> " << d << " -> ";
	for(int i = bas; i <= son; i++){
		of[d][i][0] = (int)min(1ll*inf, 1ll*-pre[i]*d + 1ll*dp[i][x]);
		// cout << of[d][i][0] << " ";
	}
	// cout << endl;
	// cout << "AMK1" << endl;
	for(int i = 1; i <= LOGN; i++)
		for(int j = bas; j <= son; j++)
			if(j + (1<<(i-1)) <= son)
				of[d][j][i] = min(of[d][j][i - 1], of[d][j + (1<<(i-1))][i - 1]);
	// cout << "AMK2" << endl;
}

int ver(int d, int x, int y){
	if(x > y)
		return inf;
	int uz = y - x + 1;
	// cout << d << " " << x << " " << y << " = " <<min(of[d][x][lg[uz]], of[d][y - (1<<lg[uz]) + 1][lg[uz]]) << endl;
	return min(of[d][x][lg[uz]], of[d][y - (1<<lg[uz]) + 1][lg[uz]]);
}

int main() {
	// freopen("in.txt", "r", stdin);
	// freopen("out.txt", "w", stdout);
	scanf("%d %d %d",&n ,&m ,&s);
	for(int i = 1; i <= m; i++){
		scanf("%d",a + i);
		pre[i] = pre[i - 1] + a[i];
	}
	for(int i = 1; i <= n; i++){
		int son = 0;
		for(int j = 1; j <= m; j++){
			char x;scanf(" %c",&x);
			if(x == '0')
				son = j;
			git[j][i] = son;
		}
	}
	for(int i = 1; i <= m; i++){
		sort(git[i] + 1, git[i] + n + 1);
		git[i][n + 1] = i;
	}
	for(int i = 1; i <= s; i++)
		dp[0][i] = inf;
	for(int i = 1; i <= m; i++)
		dp[i][0] = inf;

	int off = 2;
	lg[1] = 0;
	for(int i = 2; i < N; i++){
		if(i == off){
			lg[i] = lg[i - 1] + 1;
			off *= 2;
		} else
			lg[i] = lg[i - 1];
	}

	for(int kac = 1; kac <= s; kac++){

		for(int i = 0; i <= n; i++)
			bu(i, 0, m, kac - 1);

		for(int ind = 1; ind <= m; ind++){
				int &r = dp[ind][kac];
				r = inf;
				int opt = 0;
				for(int i = 0; i <= n; i++)
					r = min(r, (int)min(1ll*inf, (1ll*ver(i, git[ind][i], git[ind][i + 1] - 1) + 1ll*i*pre[ind])) );

		}

	}
	for(int i = 1; i <= s; i++)
		printf("%d\n", dp[m][i]);
	return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:88:9: warning: unused variable 'opt' [-Wunused-variable]
     int opt = 0;
         ^~~
popeala.cpp:47:7: 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:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",a + i);
   ~~~~~^~~~~~~~~~~~
popeala.cpp:55:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    char x;scanf(" %c",&x);
           ~~~~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 2424 KB Output is correct
2 Correct 40 ms 2456 KB Output is correct
3 Correct 41 ms 2552 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 8168 KB Output is correct
2 Correct 463 ms 11228 KB Output is correct
3 Correct 614 ms 14712 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 42 ms 2424 KB Output is correct
4 Correct 40 ms 2456 KB Output is correct
5 Correct 41 ms 2552 KB Output is correct
6 Correct 290 ms 8168 KB Output is correct
7 Correct 463 ms 11228 KB Output is correct
8 Correct 614 ms 14712 KB Output is correct
9 Correct 1148 ms 23404 KB Output is correct
10 Correct 1715 ms 30360 KB Output is correct
11 Execution timed out 2059 ms 67704 KB Time limit exceeded
12 Halted 0 ms 0 KB -