oj.uz

답안 #96509

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
96509 2019-02-10T02:39:25 Z jasony123123 조교 (CEOI16_popeala) C++11
100 / 100
 369 ms 14600 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef unsigned long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll INF = 1e14;
/***********************CEOI 2016 D2 Popeala*****************************************/

const int MAXN = 50, MAXT = 20000;

int N, T, S;
ll P[MAXT];
int res[MAXN][MAXT];

ll dp[MAXN + 1][MAXT + 1];
int G[MAXT];
ll best[MAXN + 1];

int last[MAXN];
v<int> badIntv[MAXT];

int main() {
	io();
	cin >> N >> T >> S;
	FOR(i, 0, T) cin >> P[i];
	FOR(i, 0, N) FOR(j, 0, T) {
		char c; cin >> c;
		res[i][j] = c - '0';
	}

	FORE(i, 0, S) FORE(j, 0, T)
		dp[i][j] = INF;
	dp[0][T] = 0;

	FOR(i, 0, N) last[i] = T;
	RFORE(i, T - 1, 0) {
		FOR(c, 0, N) if (res[c][i] == 0) {
			if (i + 1 < last[c])
				badIntv[i].push_back(last[c] - 1);
			last[c] = i;
		}
		sort(all(badIntv[i]));
	}

	FORE(k, 1, S) {
		FORE(g, 0, N) best[g] = INF;

		RFORE(i, T - 1, 0) {
			FORE(g, 0, N) best[g] += g*P[i];
			
			for (auto j : badIntv[i])
				best[G[j]] = INF;

			if (!badIntv[i].empty()) {
				int pb = 0; // pointer to first j<badintv[i][pb]
				int sum = P[i];
				FOR(j, i + 1, T) {
					G[j] -= badIntv[i].size() - pb;
					sum += P[j];
					minn(best[G[j]], G[j] * sum + dp[k - 1][j + 1]);
					while (pb < badIntv[i].size() && badIntv[i][pb] <= j)
						pb++;
					if (pb == badIntv[i].size())
						break;
				}
			}
			
			// add i into best
			int num1 = 0;
			FOR(c, 0, N) if (res[c][i] == 1) 
				num1++;
			G[i] = num1;
			minn(best[num1], P[i] * num1 + dp[k - 1][i + 1]);


			// calc dp[k][i]
			FORE(g, 0, N)
				minn(dp[k][i], best[g]);
			//cout << "dp " << k << " " << i << " = " << dp[k][i] << "\n";
			//

			//int temp[MAXT];
			//memset(temp, 0, sizeof temp);
			//FOR(c, 0, N) {
			//	for (int x = i; x < T && res[c][x] == 1; x++)
			//		temp[x]++;
			//}
			//cout << "correct G\n";
			//FOR(x, i, T)
			//	cout << temp[x] << " ";
			//cout << "\n";
			//cout << "my G\n";
			//FOR(x, i, T)
			//	cout << G[x] << " ";
			//cout << "\n";
			//cout << "\n";
		}
	}
	FORE(i, 1, S)
		cout << dp[i][0] << "\n";
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:93:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      while (pb < badIntv[i].size() && badIntv[i][pb] <= j)
             ~~~^~~~~~~~~~~~~~~~~~~
popeala.cpp:95:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if (pb == badIntv[i].size())
          ~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 888 KB Output is correct
2 Correct 3 ms 1016 KB Output is correct

Subtask #2
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 1660 KB Output is correct
2 Correct 9 ms 1656 KB Output is correct
3 Correct 9 ms 1528 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 2680 KB Output is correct
2 Correct 47 ms 3448 KB Output is correct
3 Correct 63 ms 3960 KB Output is correct

Subtask #4
74.0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 888 KB Output is correct
2 Correct 3 ms 1016 KB Output is correct
3 Correct 11 ms 1660 KB Output is correct
4 Correct 9 ms 1656 KB Output is correct
5 Correct 9 ms 1528 KB Output is correct
6 Correct 34 ms 2680 KB Output is correct
7 Correct 47 ms 3448 KB Output is correct
8 Correct 63 ms 3960 KB Output is correct
9 Correct 105 ms 5756 KB Output is correct
10 Correct 157 ms 7208 KB Output is correct
11 Correct 369 ms 14200 KB Output is correct
12 Correct 332 ms 14388 KB Output is correct
13 Correct 338 ms 14564 KB Output is correct
14 Correct 341 ms 14584 KB Output is correct
15 Correct 343 ms 14600 KB Output is correct