답안 #775804

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
775804	2023-07-07T03:28:09 Z	marvinthang	Chorus (JOI23_chorus)	C++17	40 / 100	17 ms	2772 KB

chorus

/*************************************
*    author: marvinthang             *
*    created: 07.07.2023 10:11:54    *
*************************************/

#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }

// end of template

const int MAX = 523;
const int INF = 1e9;

int N, K;
string S;
vector <int> pos[2];

void init(void) {
	cin >> N >> K >> S;
}

int cost[MAX][MAX];
int dp[MAX][MAX];

void process(void) {
	REP(i, 2 * N) pos[S[i] - 'A'].push_back(i);
	REP(l, N) {
		int p = l;
		int cur = 0;
		FOR(r, l, N) {
			while (p < N && pos[1][p] < pos[0][r]) ++p;
			cur += p - l;
			cost[l][r] = cur;
		}
	}
	memset(dp, 0x3f, sizeof(dp));
	dp[0][0] = 0;
	REP(k, K) REP(i, N) if (dp[k][i] < INF) FORE(j, i + 1, N) 
		minimize(dp[k + 1][j], dp[k][i] + cost[i][j - 1]);
	cout << dp[K][N] << '\n';
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr); // cout.tie(nullptr);
	file("chorus");
	init();
	process();
	cerr << "Time elapsed: " << TIME << " s.\n";
	return (0^0);
}

Compilation message

chorus.cpp: In function 'int main()':
chorus.cpp:30:61: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
chorus.cpp:81:2: note: in expansion of macro 'file'
   81 |  file("chorus");
      |  ^~~~
chorus.cpp:30:94: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
      |                                                                                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
chorus.cpp:81:2: note: in expansion of macro 'file'
   81 |  file("chorus");
      |  ^~~~

Subtask #1
16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1364 KB	Output is correct
2	Correct	1 ms	1364 KB	Output is correct
3	Correct	1 ms	1352 KB	Output is correct
4	Correct	1 ms	1364 KB	Output is correct
5	Correct	1 ms	1364 KB	Output is correct
6	Correct	1 ms	1364 KB	Output is correct
7	Correct	1 ms	1364 KB	Output is correct
8	Correct	1 ms	1364 KB	Output is correct
9	Correct	1 ms	1364 KB	Output is correct
10	Correct	1 ms	1364 KB	Output is correct
11	Correct	1 ms	1352 KB	Output is correct
12	Correct	1 ms	1352 KB	Output is correct
13	Correct	1 ms	1364 KB	Output is correct
14	Correct	1 ms	1364 KB	Output is correct
15	Correct	1 ms	1364 KB	Output is correct
16	Correct	1 ms	1364 KB	Output is correct

Subtask #2
24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1364 KB	Output is correct
2	Correct	1 ms	1364 KB	Output is correct
3	Correct	1 ms	1352 KB	Output is correct
4	Correct	1 ms	1364 KB	Output is correct
5	Correct	1 ms	1364 KB	Output is correct
6	Correct	1 ms	1364 KB	Output is correct
7	Correct	1 ms	1364 KB	Output is correct
8	Correct	1 ms	1364 KB	Output is correct
9	Correct	1 ms	1364 KB	Output is correct
10	Correct	1 ms	1364 KB	Output is correct
11	Correct	1 ms	1352 KB	Output is correct
12	Correct	1 ms	1352 KB	Output is correct
13	Correct	1 ms	1364 KB	Output is correct
14	Correct	1 ms	1364 KB	Output is correct
15	Correct	1 ms	1364 KB	Output is correct
16	Correct	1 ms	1364 KB	Output is correct
17	Correct	2 ms	1732 KB	Output is correct
18	Correct	8 ms	2388 KB	Output is correct
19	Correct	15 ms	2388 KB	Output is correct
20	Correct	1 ms	2380 KB	Output is correct
21	Correct	2 ms	2388 KB	Output is correct
22	Correct	17 ms	2424 KB	Output is correct
23	Correct	16 ms	2388 KB	Output is correct
24	Correct	2 ms	2388 KB	Output is correct
25	Correct	16 ms	2420 KB	Output is correct
26	Correct	16 ms	2412 KB	Output is correct
27	Correct	12 ms	2388 KB	Output is correct
28	Correct	12 ms	2388 KB	Output is correct

Subtask #3
0 / 21.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1364 KB	Output is correct
2	Correct	1 ms	1364 KB	Output is correct
3	Correct	1 ms	1352 KB	Output is correct
4	Correct	1 ms	1364 KB	Output is correct
5	Correct	1 ms	1364 KB	Output is correct
6	Correct	1 ms	1364 KB	Output is correct
7	Correct	1 ms	1364 KB	Output is correct
8	Correct	1 ms	1364 KB	Output is correct
9	Correct	1 ms	1364 KB	Output is correct
10	Correct	1 ms	1364 KB	Output is correct
11	Correct	1 ms	1352 KB	Output is correct
12	Correct	1 ms	1352 KB	Output is correct
13	Correct	1 ms	1364 KB	Output is correct
14	Correct	1 ms	1364 KB	Output is correct
15	Correct	1 ms	1364 KB	Output is correct
16	Correct	1 ms	1364 KB	Output is correct
17	Correct	2 ms	1732 KB	Output is correct
18	Correct	8 ms	2388 KB	Output is correct
19	Correct	15 ms	2388 KB	Output is correct
20	Correct	1 ms	2380 KB	Output is correct
21	Correct	2 ms	2388 KB	Output is correct
22	Correct	17 ms	2424 KB	Output is correct
23	Correct	16 ms	2388 KB	Output is correct
24	Correct	2 ms	2388 KB	Output is correct
25	Correct	16 ms	2420 KB	Output is correct
26	Correct	16 ms	2412 KB	Output is correct
27	Correct	12 ms	2388 KB	Output is correct
28	Correct	12 ms	2388 KB	Output is correct
29	Runtime error	16 ms	2772 KB	Execution killed with signal 11
30	Halted	0 ms	0 KB	-

Subtask #4
0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1364 KB	Output is correct
2	Correct	1 ms	1364 KB	Output is correct
3	Correct	1 ms	1352 KB	Output is correct
4	Correct	1 ms	1364 KB	Output is correct
5	Correct	1 ms	1364 KB	Output is correct
6	Correct	1 ms	1364 KB	Output is correct
7	Correct	1 ms	1364 KB	Output is correct
8	Correct	1 ms	1364 KB	Output is correct
9	Correct	1 ms	1364 KB	Output is correct
10	Correct	1 ms	1364 KB	Output is correct
11	Correct	1 ms	1352 KB	Output is correct
12	Correct	1 ms	1352 KB	Output is correct
13	Correct	1 ms	1364 KB	Output is correct
14	Correct	1 ms	1364 KB	Output is correct
15	Correct	1 ms	1364 KB	Output is correct
16	Correct	1 ms	1364 KB	Output is correct
17	Correct	2 ms	1732 KB	Output is correct
18	Correct	8 ms	2388 KB	Output is correct
19	Correct	15 ms	2388 KB	Output is correct
20	Correct	1 ms	2380 KB	Output is correct
21	Correct	2 ms	2388 KB	Output is correct
22	Correct	17 ms	2424 KB	Output is correct
23	Correct	16 ms	2388 KB	Output is correct
24	Correct	2 ms	2388 KB	Output is correct
25	Correct	16 ms	2420 KB	Output is correct
26	Correct	16 ms	2412 KB	Output is correct
27	Correct	12 ms	2388 KB	Output is correct
28	Correct	12 ms	2388 KB	Output is correct
29	Runtime error	16 ms	2772 KB	Execution killed with signal 11
30	Halted	0 ms	0 KB	-

Subtask #5
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	1364 KB	Output is correct
2	Correct	1 ms	1364 KB	Output is correct
3	Correct	1 ms	1352 KB	Output is correct
4	Correct	1 ms	1364 KB	Output is correct
5	Correct	1 ms	1364 KB	Output is correct
6	Correct	1 ms	1364 KB	Output is correct
7	Correct	1 ms	1364 KB	Output is correct
8	Correct	1 ms	1364 KB	Output is correct
9	Correct	1 ms	1364 KB	Output is correct
10	Correct	1 ms	1364 KB	Output is correct
11	Correct	1 ms	1352 KB	Output is correct
12	Correct	1 ms	1352 KB	Output is correct
13	Correct	1 ms	1364 KB	Output is correct
14	Correct	1 ms	1364 KB	Output is correct
15	Correct	1 ms	1364 KB	Output is correct
16	Correct	1 ms	1364 KB	Output is correct
17	Correct	2 ms	1732 KB	Output is correct
18	Correct	8 ms	2388 KB	Output is correct
19	Correct	15 ms	2388 KB	Output is correct
20	Correct	1 ms	2380 KB	Output is correct
21	Correct	2 ms	2388 KB	Output is correct
22	Correct	17 ms	2424 KB	Output is correct
23	Correct	16 ms	2388 KB	Output is correct
24	Correct	2 ms	2388 KB	Output is correct
25	Correct	16 ms	2420 KB	Output is correct
26	Correct	16 ms	2412 KB	Output is correct
27	Correct	12 ms	2388 KB	Output is correct
28	Correct	12 ms	2388 KB	Output is correct
29	Runtime error	16 ms	2772 KB	Execution killed with signal 11
30	Halted	0 ms	0 KB	-

답안 #775804

Compilation message

Subtask #1 16.0 / 16.0

Subtask #2 24.0 / 24.0

Subtask #3 0 / 21.0

Subtask #4 0 / 26.0

Subtask #5 0 / 13.0

Subtask #1
16.0 / 16.0

Subtask #2
24.0 / 24.0

Subtask #3
0 / 21.0

Subtask #4
0 / 26.0

Subtask #5
0 / 13.0