oj.uz

Submission #537352

# Submission time Handle Problem Language Result Execution time Memory
537352 2022-03-15T03:06:26 Z pavement Popeala (CEOI16_popeala) C++17
26 / 100
 2000 ms 1252 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
using db = double;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;
using iiii = tuple<int, int, int, int>;
template<class key, class value = null_type, class cmp = less<key> >
using ordered_set = tree<key, value, cmp, rb_tree_tag, tree_order_statistics_node_update>;

int N, T, S, P[20005], lim[55], dp[20005], ndp[20005];
bool R[55][20005];
char C;
vector<ii> vec;
map<int, int> mpp;

int qry(int l, int r, int x, int idx) {
	assert(l <= r);
	int ret = LLONG_MAX;
	for (int i = l; i <= r; i++)
		ret = min(ret, dp[i - 1] + x * P[idx] - x * P[i - 1]);
	return ret;
}

void go() {
	for (int i = 1; i <= T; i++) {
		mpp.clear();
		vec.clear();
		for (int k = 1; k <= N; k++) {
			if (R[k][i]) lim[k] = (lim[k] ? lim[k] : i);
			else lim[k] = 0;
			if (lim[k]) mpp[lim[k]]++;
		}
		for (auto k : mpp) vec.eb(k.first, k.second);
		if (vec.empty()) {
			ndp[i] = qry(1, i, 0, i);
			continue;
		}
		int cum = 0;
		ndp[i] = LLONG_MAX;
		for (int k = 0, prv = i; k < vec.size(); k++) {
			cum += vec[k].second;
			//cout << "! " << vec[k].first << ' ' << (k + 1 < vec.size() ? vec[k + 1].first - 1 : i) << ' ' << cum << '\n';
			ndp[i] = min(ndp[i], qry(vec[k].first, (k + 1 < vec.size() ? vec[k + 1].first - 1 : i), cum, i));
			prv = vec[k].first - 1;
		}
		if (vec[0].first != 1) {
			//cout << 1 << ' ' << vec[0].first - 1 << " 0\n";
			ndp[i] = min(ndp[i], qry(1, vec[0].first - 1, 0, i));
		}
	}
}

main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> T >> S;
	for (int i = 1; i <= T; i++) cin >> P[i], P[i] += P[i - 1];
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= T; j++) {
			cin >> C;
			R[i][j] = (C == '1');
		}
	dp[0] = 0;
	for (int i = 1; i <= T; i++) dp[i] = 1e16;
	for (int i = 1; i <= S; i++) {
		for (int j = 1; j <= N; j++) lim[j] = 0;
		go();
		swap(dp, ndp);
		cout << dp[T] << '\n';
		dp[0] = 1e16;
	}
}

Compilation message

popeala.cpp: In function 'void go()':
popeala.cpp:59:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |   for (int k = 0, prv = i; k < vec.size(); k++) {
      |                            ~~^~~~~~~~~~~~
popeala.cpp:62:50: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |    ndp[i] = min(ndp[i], qry(vec[k].first, (k + 1 < vec.size() ? vec[k + 1].first - 1 : i), cum, i));
      |                                            ~~~~~~^~~~~~~~~~~~
popeala.cpp:59:19: warning: variable 'prv' set but not used [-Wunused-but-set-variable]
   59 |   for (int k = 0, prv = i; k < vec.size(); k++) {
      |                   ^~~
popeala.cpp: At global scope:
popeala.cpp:72:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   72 | main() {
      | ^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 724 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 852 KB Output is correct
2 Correct 94 ms 876 KB Output is correct
3 Correct 95 ms 860 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 629 ms 940 KB Output is correct
2 Correct 824 ms 1124 KB Output is correct
3 Correct 1275 ms 1200 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 106 ms 852 KB Output is correct
4 Correct 94 ms 876 KB Output is correct
5 Correct 95 ms 860 KB Output is correct
6 Correct 629 ms 940 KB Output is correct
7 Correct 824 ms 1124 KB Output is correct
8 Correct 1275 ms 1200 KB Output is correct
9 Execution timed out 2077 ms 1252 KB Time limit exceeded
10 Halted 0 ms 0 KB -