Submission #1210776

#TimeUsernameProblemLanguageResultExecution timeMemory
1210776sunflowerExam (eJOI20_exam)C++17
65 / 100
254 ms99388 KiB
#include <bits/stdc++.h> using namespace std; #define BIT(x, i) (((x) >> (i)) & 1) template <class X, class Y> bool maximize(X &x, Y y) { if (x < y) return x = y, true; else return false; } template <class T> void remove_dup(vector <T> &v) { sort(v.begin(), v.end()); v.resize(unique(v.begin(), v.end()) - v.begin()); } int POS(int x, vector <int> &v) { return lower_bound(v.begin(), v.end(), x) - v.begin() + 1; } const int inf = (int) 1e9 + 7; int n; #define MAX_N 100'100 int a[MAX_N + 2], b[MAX_N + 2]; #undef MAX_N namespace subtask2 { bool check() { return (*max_element(b + 1, b + 1 + n) == *min_element(b + 1, b + 1 + n)); } void solve() { int ans = 0, cnt = 0; bool ok = false; a[n + 1] = inf; for (int i = 1; i <= n + 1; ++i) { if (a[i] > b[1]) { if (ok) ans += cnt; cnt = 0; ok = false; } else { ++cnt; if (a[i] == b[1]) ok = true; } } cout << ans; } }; namespace subtask3 { bool check() { for (int i = 1; i < n; ++i) { if (a[i] >= a[i + 1]) return false; } return (n <= 5000); } int f[5050][5050]; //f[i][j]: ap dung nhung thay doi tu A[1] -> A[i] cho nhung thang tu 1 -> j void solve(){ int N = n; vector <int> lef(n + 2), rig(n + 2); for(int i = 1; i <= N; i++){ lef[i] = i - 1; while(lef[i] > 0 && a[i] >= a[lef[i]]) lef[i] = lef[lef[i]]; } for(int i = N; i >= 1; i--){ rig[i] = i + 1; while(rig[i] <= N && a[i] >= a[rig[i]]) rig[i] = rig[rig[i]]; } int ans = 0; for(int j = 1; j <= n; j++){ for(int i = 1; i <= n; i++){ f[i][j] = max(f[i - 1][j], f[i][j - 1]); if(a[i] == b[j] && lef[i] < j && j < rig[i]){ maximize(f[i][j], f[i][j - 1] + 1); } maximize(ans, f[i][j]); } } cout << ans << '\n'; } }; int main() { ios_base::sync_with_stdio(false);cin.tie(nullptr); if (fopen("test.inp","r")) { freopen("test.inp","r",stdin); freopen("test.out","w",stdout); } cin >> n; vector <int> v; for (int i = 1; i <= n; ++i) cin >> a[i], v.push_back(a[i]); for (int i = 1; i <= n; ++i) cin >> b[i], v.push_back(b[i]); remove_dup(v); for (int i = 1; i <= n; ++i) { a[i] = POS(a[i], v); b[i] = POS(b[i], v); } // if (subtask2 :: check()) return subtask2 :: solve(), 0; // if (subtask3 :: check()) return subtask3 :: solve(), 0; return 0; }

Compilation message (stderr)

exam.cpp: In function 'int main()':
exam.cpp:96:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     freopen("test.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
exam.cpp:97:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     freopen("test.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...