# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
102518 |
2019-03-25T15:25:31 Z |
jhnah917 |
None (KOI18_matrix) |
C++14 |
|
307 ms |
7024 KB |
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef pair<int, int> p;
typedef pair<int, p> pp;
void f2(){
int n; cin >> n;
vector<p> v(n);
for(int i=0; i<n; i++) cin >> v[i].x;
for(int i=0; i<n; i++) cin >> v[i].y;
sort(v.begin(), v.end());
int ans = 0;
vector<int> lis(1, -1);
for(auto &i : v){
int now = i.y;
if(now > lis.back()) lis.push_back(now), ans++;
else{
auto it = lower_bound(lis.begin(), lis.end(), now);
*it = now;
}
}
cout << ans;
}
void f3(){
int n; cin >> n;
vector<pp> v(n);
for(int i=0; i<n; i++) cin >> v[i].x;
for(int i=0; i<n; i++) cin >> v[i].y.x;
for(int i=0; i<n; i++) cin >> v[i].y.y;
sort(v.begin(), v.end());
vector<int> dp(n, 0);
dp[0] = 1;
int ans = 0;
for(int i=2; i<n; i++){
int now = 0;
for(int j=i-1; j>=0; j--){
if(v[j].y.x < v[i].y.x && v[j].y.y < v[i].y.y) now = max(now, dp[j]);
}
dp[i] = now+1;
ans = max(ans, dp[i]);
}
cout << ans;
}
int main(){
int n; cin >> n;
if(n == 2){
f2();
}else{
f3();
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
384 KB |
Output is correct |
2 |
Correct |
15 ms |
640 KB |
Output is correct |
3 |
Correct |
14 ms |
640 KB |
Output is correct |
4 |
Correct |
17 ms |
640 KB |
Output is correct |
5 |
Correct |
15 ms |
640 KB |
Output is correct |
6 |
Correct |
17 ms |
760 KB |
Output is correct |
7 |
Correct |
16 ms |
672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
81 ms |
768 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
384 KB |
Output is correct |
2 |
Correct |
15 ms |
640 KB |
Output is correct |
3 |
Correct |
14 ms |
640 KB |
Output is correct |
4 |
Correct |
17 ms |
640 KB |
Output is correct |
5 |
Correct |
15 ms |
640 KB |
Output is correct |
6 |
Correct |
17 ms |
760 KB |
Output is correct |
7 |
Correct |
16 ms |
672 KB |
Output is correct |
8 |
Correct |
221 ms |
5928 KB |
Output is correct |
9 |
Correct |
239 ms |
5952 KB |
Output is correct |
10 |
Correct |
236 ms |
6136 KB |
Output is correct |
11 |
Correct |
243 ms |
5752 KB |
Output is correct |
12 |
Correct |
238 ms |
5920 KB |
Output is correct |
13 |
Correct |
233 ms |
6388 KB |
Output is correct |
14 |
Correct |
289 ms |
6124 KB |
Output is correct |
15 |
Correct |
307 ms |
5880 KB |
Output is correct |
16 |
Correct |
224 ms |
7024 KB |
Output is correct |
17 |
Correct |
256 ms |
6404 KB |
Output is correct |
18 |
Correct |
227 ms |
6516 KB |
Output is correct |
19 |
Correct |
231 ms |
6032 KB |
Output is correct |
20 |
Correct |
205 ms |
5796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
81 ms |
768 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |