Submission #1072121

#TimeUsernameProblemLanguageResultExecution timeMemory
1072121vjudge1Double Attendance (CCO22_day1problem3)C++14
21 / 25
79 ms63368 KiB
#include<bits/stdc++.h> #include<fstream> using namespace std; #define sz(a) (int)a.size() #define ALL(v) v.begin(), v.end() #define ALLR(v) v.rbegin(), v.rend() #define ll long long #define pb push_back #define forr(i, a, b) for(int i = a; i < b; i++) #define dorr(i, a, b) for(int i = a; i >= b; i--) #define ld long double #define vt vector #include<fstream> #define fi first #define se second #define pll pair<ll, ll> #define pii pair<int, int> #define mpp make_pair const ld PI = 3.14159265359, prec = 1e-9;; //using u128 = __uint128_t; //const int x[4] = {1, 0, -1, 0}; //const int y[4] = {0, -1, 0, 1}; const ll mod =1e9 + 7, pr = 31; const int mxn = 1e6 + 5, mxq = 1e5 + 5, sq = 500, mxv = 5e4 + 1; //const int base = (1 <<18); const ll inf = 1e9 + 5, neg = -69420, inf2 = 1e14; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // have fun! int n1, n2, t; void comb(pii &a, pii b){ if(a.fi < b.fi)a = b; if(a.fi == b.fi && a.se > b.se)a = b; } pii dp[2005][2005][2], one[2005], two[2005]; void solve(){ cin >> n1 >> n2 >> t; for(int i = 1; i <= n1; i++){ cin >> one[i].fi >> one[i].se; } sort(one + 1, one + n1 + 1); for(int i = 1; i <= n2; i++){ cin >> two[i].fi >> two[i].se; } sort(two + 1, two + n2 + 1); for(int i = 0; i <= n1; i++){ for(int j = 0; j <= n2; j++){ dp[i][j][0] = dp[i][j][1] = mpp(-inf, inf); } } dp[0][0][0] = mpp(0, 0); int ans = 0; for(int i = 0; i <= n1; i++){ for(int j = 0; j <= n2; j++){ for(int k = 0; k < 2; k++){ if(dp[i][j][k].fi == -inf)continue; if(k == 0){ if(i < n1){ assert(dp[i][j][k].se <= one[i + 1].fi); comb(dp[i + 1][j][0], mpp(dp[i][j][k].fi + 1, one[i + 1].fi)); }if(j < n2){ comb(dp[i][j + 1][0], dp[i][j][k]); if(dp[i][j][k].se + t < two[j + 1].se){ comb(dp[i][j + 1][1], mpp(dp[i][j][k].fi + 1, max(dp[i][j][k].se + t, two[j + 1].fi))); } } }else{ if(j < n2){ assert(dp[i][j][k].se <= two[j + 1].fi); comb(dp[i][j + 1][1], mpp(dp[i][j][k].fi + 1, two[j + 1].fi)); }if(i < n1){ comb(dp[i + 1][j][1], dp[i][j][k]); if(dp[i][j][k].se + t < one[i + 1].se){ comb(dp[i + 1][j][0], mpp(dp[i][j][k].fi + 1, max(dp[i][j][k].se + t, one[i + 1].fi))); } } } ans = max(ans, dp[i][j][k].fi); } } } cout << ans; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("THREE.inp", "r", stdin); //freopen("THREE.out", "w", stdout); int tt; tt = 1; while(tt--){ solve(); } return(0); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...