답안 #831238

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
831238	2023-08-20T01:46:34 Z	DP_196	Exhibition (JOI19_ho_t2)	C++14	50 / 100	356 ms	13692 KB

joi2019_ho_t2

#include <bits/stdc++.h>
 
using namespace std;
 
#define sz(x) (int)x.size()
#define MASK(i) ((1LL) << (i))
#define all(x) x.begin(), x.end()
#define BIT(x, i) ((x) >> (i) & (1LL))
#define dbg(...) cerr << "#" << __LINE__ << ":[" << #__VA_ARGS__ \
<< "] = [" ,DBG(__VA_ARGS__)
 
string to_string(const string& s) { return '"' + s + '"'; }
void DBG() { cerr << "]" << endl; }
template<class H, class... T> void DBG(H h, T... t) {
        cerr << to_string(h); if(sizeof...(t)) cerr << ", "; DBG(t...);
}
 
template <class T>
inline bool maximize(T &a, const T &b) { return (a < b ? (a = b) : 0); }
template <class T>
inline bool minimize(T &a, const T &b) { return (a > b ? (a = b) : 0); }
 
const int MAXN = 1e5 + 6;
const int INF = 1e9;
const int MOD = 1e9 + 7;
 
int nPic, nFrame;
int frame_size[MAXN], dp[1005][1005];
 
struct dat {
	int Size, Val;
} pic[MAXN];
 
void solve() {
	cin >> nPic >> nFrame;
	
	for (int i = 1; i <= nPic; i++) {
		cin >> pic[i].Size >> pic[i].Val;
	}
	
	for (int i = 1; i <= nFrame; i++) cin >> frame_size[i];
	
	sort(pic + 1, pic + nPic + 1, [] (dat pic1, dat pic2) {
		if (pic1.Val == pic2.Val) return pic1.Size < pic2.Size;
		return pic1.Val < pic2.Val;
	});
	
	sort(frame_size + 1, frame_size + nFrame + 1);
	
	int res = 0, j = nFrame;
	
	for (int i = 1; i <= nPic; i++) {
		for (int j = 1; j <= nFrame; j++) {
			dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
			if (pic[i].Size <= frame_size[j]) maximize(dp[i][j], dp[i - 1][j - 1] + 1);
		}
	}
	
	cout << dp[nPic][nFrame];
}
 
#define TASK ""
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen(TASK".inp", "r", stdin);
    //freopen(TASK".out", "w", stdout);
 
    int ntest = 1;
    //cin >> ntest;
    while (ntest--) solve();
 
    return 0;
}
//612

Compilation message

joi2019_ho_t2.cpp: In function 'void solve()':
joi2019_ho_t2.cpp:50:6: warning: unused variable 'res' [-Wunused-variable]
   50 |  int res = 0, j = nFrame;
      |      ^~~
joi2019_ho_t2.cpp:50:15: warning: unused variable 'j' [-Wunused-variable]
   50 |  int res = 0, j = nFrame;
      |               ^

Subtask #1
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	336 KB	Output is correct
11	Correct	0 ms	336 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct

Subtask #2
40.0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	336 KB	Output is correct
11	Correct	0 ms	336 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	5 ms	4316 KB	Output is correct
21	Correct	5 ms	4396 KB	Output is correct
22	Correct	5 ms	4308 KB	Output is correct
23	Correct	5 ms	4308 KB	Output is correct
24	Correct	5 ms	4308 KB	Output is correct
25	Correct	5 ms	4228 KB	Output is correct
26	Correct	6 ms	4308 KB	Output is correct
27	Correct	5 ms	4308 KB	Output is correct
28	Correct	5 ms	4308 KB	Output is correct
29	Correct	5 ms	4308 KB	Output is correct
30	Correct	5 ms	4308 KB	Output is correct
31	Correct	5 ms	4308 KB	Output is correct
32	Correct	2 ms	4180 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	3 ms	4180 KB	Output is correct
35	Correct	1 ms	340 KB	Output is correct
36	Correct	5 ms	4308 KB	Output is correct
37	Correct	5 ms	4308 KB	Output is correct

Subtask #3
0 / 50.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	0 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	1 ms	332 KB	Output is correct
6	Correct	0 ms	340 KB	Output is correct
7	Correct	0 ms	340 KB	Output is correct
8	Correct	0 ms	340 KB	Output is correct
9	Correct	0 ms	340 KB	Output is correct
10	Correct	0 ms	336 KB	Output is correct
11	Correct	0 ms	336 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct
13	Correct	0 ms	340 KB	Output is correct
14	Correct	0 ms	340 KB	Output is correct
15	Correct	0 ms	340 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct
17	Correct	0 ms	340 KB	Output is correct
18	Correct	0 ms	340 KB	Output is correct
19	Correct	0 ms	340 KB	Output is correct
20	Correct	5 ms	4316 KB	Output is correct
21	Correct	5 ms	4396 KB	Output is correct
22	Correct	5 ms	4308 KB	Output is correct
23	Correct	5 ms	4308 KB	Output is correct
24	Correct	5 ms	4308 KB	Output is correct
25	Correct	5 ms	4228 KB	Output is correct
26	Correct	6 ms	4308 KB	Output is correct
27	Correct	5 ms	4308 KB	Output is correct
28	Correct	5 ms	4308 KB	Output is correct
29	Correct	5 ms	4308 KB	Output is correct
30	Correct	5 ms	4308 KB	Output is correct
31	Correct	5 ms	4308 KB	Output is correct
32	Correct	2 ms	4180 KB	Output is correct
33	Correct	1 ms	340 KB	Output is correct
34	Correct	3 ms	4180 KB	Output is correct
35	Correct	1 ms	340 KB	Output is correct
36	Correct	5 ms	4308 KB	Output is correct
37	Correct	5 ms	4308 KB	Output is correct
38	Runtime error	356 ms	13692 KB	Execution killed with signal 11
39	Halted	0 ms	0 KB	-

답안 #831238

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 40.0 / 40.0

Subtask #3 0 / 50.0

Subtask #1
10.0 / 10.0

Subtask #2
40.0 / 40.0

Subtask #3
0 / 50.0