Submission #135642

#	Time	Username	Problem	Language	Result	Execution time	Memory
135642		ekrem	Popeala (CEOI16_popeala)	C++17	26 / 100	2059 ms	67704 KiB

popeala

#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 (stderr)

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 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 0 / 74