제출 #309207

#제출 시각아이디문제언어결과실행 시간메모리
309207caoash사다리꼴 (balkan11_trapezoid)C++14
14 / 100
1094 ms5368 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vi = vector<int>; using vl = vector<ll>; #define pb push_back #define rsz resize #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() using pi = pair<int,int>; #define f first #define s second #define mp make_pair const int MX = 200005; const int MOD = (int) (1e9 + 7); const ll INF = (ll) 1e18; namespace output { void pr(int x) { cout << x; } void pr(long x) { cout << x; } void pr(ll x) { cout << x; } void pr(unsigned x) { cout << x; } void pr(unsigned long x) { cout << x; } void pr(unsigned long long x) { cout << x; } void pr(float x) { cout << x; } void pr(double x) { cout << x; } void pr(long double x) { cout << x; } void pr(char x) { cout << x; } void pr(const char * x) { cout << x; } void pr(const string & x) { cout << x; } void pr(bool x) { pr(x ? "true" : "false"); } template < class T1, class T2 > void pr(const pair < T1, T2 > & x); template < class T > void pr(const T & x); template < class T, class...Ts > void pr(const T & t, const Ts & ...ts) { pr(t); pr(ts...); } template < class T1, class T2 > void pr(const pair < T1, T2 > & x) { pr("{", x.f, ", ", x.s, "}"); } template < class T > void pr(const T & x) { pr("{"); // const iterator needed for vector<bool> bool fst = 1; for (const auto & a: x) pr(!fst ? ", " : "", a), fst = 0; pr("}"); } void ps() { pr("\n"); } // print w/ spaces template < class T, class...Ts > void ps(const T & t, const Ts & ...ts) { pr(t); if (sizeof...(ts)) pr(" "); ps(ts...); } void pc() { cout << "]" << endl; } // debug w/ commas template < class T, class...Ts > void pc(const T & t, const Ts & ...ts) { pr(t); if (sizeof...(ts)) pr(", "); pc(ts...); } #define dbg(x...) pr("[", #x, "] = ["), pc(x); } #ifdef LOCAL using namespace output; #endif int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<pair<pi, pi>> vals(n); for (int i = 0; i < n; i++) { cin >> vals[i].f.f >> vals[i].f.s; cin >> vals[i].s.f >> vals[i].s.s; } sort(all(vals), [&](auto x, auto y) { return x.f.s < y.f.s; }); vector<pi> dp(n); auto isect = [&] (pi a, pi b) { if (a.s > b.s) swap(a, b); return a.s < b.f; }; for (int i = 0; i < n; i++) { dp[i].f = 1; dp[i].s = 1; for (int j = 0; j < i; j++) { if (isect(vals[i].f, vals[j].f) && isect(vals[i].s, vals[j].s)) { if (dp[j].f + 1 > dp[i].f) { dp[i].f = dp[j].f + 1; dp[i].s = dp[j].s; } else if (dp[j].f + 1 == dp[i].f) { dp[i].s += dp[j].s; } } } } int ans = 0; for (int i = 0; i < n; i++) { ans = max(ans, dp[i].f); } ll cnt = 0; for (int i = 0; i < n; i++) { if (dp[i].f == ans) { cnt += dp[i].s; cnt %= 30013; } } cout << ans << " " << cnt << '\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...