Submission #27892

#	Time	Username	Problem	Language	Result	Execution time	Memory
27892		rondojim	Popeala (CEOI16_popeala)	C++14	100 / 100	533 ms	33820 KiB

popeala

#include "bits/stdc++.h"
using namespace std;
#define prev sdkjflksd
 
int points[20010];
long long pref[20010];
 
int result[55][20010];
int prev[55][20010];
vector <int> v[20010];
 
long long dp[55][20010];
const long long inf = 1e16;
long long maxn[55][20010];
char s[20010];
 
int main(int argc, char const *argv[])
{
	int N, T, S;
	scanf("%d %d %d", &N, &T, &S);
 
	for(int i = 1; i <= T; i++) {
		scanf("%d", &points[i]);
		pref[i] = pref[i - 1] + points[i];
	}
	for(int i = 1; i <= N; i++) {
		scanf("%s", s);
		for(int j = 1; j <= T; j++) {
			result[i][j] = s[j-1] - '0';
		}
	} 
	for(int i = 1; i <= N; i++) {
		for(int j = 1; j <= T; j++) {
			if(result[i][j] == 1) {
				prev[i][j] = 1 + prev[i][j - 1];
			} else {
				prev[i][j] = 0;
			}
		}
	}
	for(int i = 1; i <= T; i++) {
		vector <int> h;
		for(int j = 1; j <= N; j++) {
			h.push_back(prev[j][i]);
		}
		sort(h.begin(), h.end());
		reverse(h.begin(), h.end());
		for(auto j : h) {
			v[i].push_back(i - j);
		}
		v[i].push_back(i);
	}
 
	dp[0][0] = 0;
	for(int i = 1; i <= T; i++) {
		dp[0][i] = inf;
	}
	for(int x = 0; x < (int) v[1].size(); x++) {
		maxn[x][0] = dp[0][0] - x * pref[0];
		for(int j = 1; j <= T; j++) {
			maxn[x][j] = min(maxn[x][j - 1], dp[0][j] - x * pref[j]);
		}
	}
	for(int i = 1; i <= S; i++) {
		dp[i][0] = inf;
		for(int j = 1; j <= T; j++) {
			dp[i][j] = inf;
			for(int x = 0; x < (int) v[j].size(); x++) {
				if(v[j][x] > 0) dp[i][j] = min(dp[i][j], maxn[x][v[j][x] - 1] + pref[j] * x);
			}
		}
		for(int x = 0; x < (int) v[i].size(); x++) {
			maxn[x][0] = dp[i][0] - x * pref[0];
			for(int j = 1; j <= T; j++) {
				maxn[x][j] = min(maxn[x][j - 1], dp[i][j] - x * pref[j]);
			}
		}
	}
	for(int i = 1; i <= S; i++) {
		printf("%lld\n", dp[i][T]);
	}
	return 0;
}

Compilation message (stderr)

popeala.cpp: In function 'int main(int, const char**)':
popeala.cpp:20:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &N, &T, &S);
                               ^
popeala.cpp:23:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &points[i]);
                          ^
popeala.cpp:27:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s);
                 ^

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 74 / 74