Submission #971480

#	Time	Username	Problem	Language	Result	Execution time	Memory
971480		KiaRez	Double Attendance (CCO22_day1problem3)	C++17	15 / 25	360 ms	28256 KiB

Main

/*
    IN THE NAME OF GOD
*/
#include <bits/stdc++.h>

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

#define F                                      first
#define S                                      second
#define Mp                                     make_pair
#define pb                                     push_back
#define pf                                     push_front
#define size(x)                                ((ll)x.size())
#define all(x)                                 (x).begin(),(x).end()
#define kill(x)		                           cout << x << '\n', exit(0);
#define fuck(x)                                cout << "(" << #x << " , " << x << ")" << endl
#define endl                                   '\n'

const int N = 3e5+23, lg = 18;
ll Mod = 1e9+7; //998244353;

inline ll MOD(ll a, ll mod=Mod) {a%=mod; (a<0)&&(a+=mod); return a;}
inline ll poww(ll a, ll b, ll mod=Mod) {
    ll ans = 1;
    a=MOD(a, mod);
    while (b) {
        if (b & 1) ans = MOD(ans*a, mod);
        b >>= 1;
        a = MOD(a*a, mod);
    }
    return ans;
}

int n, m, k, dp[2][2005][2005];
set<pii> st[2];
int main () {
	ios_base::sync_with_stdio(false), cin.tie(0);

	cin>>n>>m>>k;
    if(n>2000 || m>2000) kill(0);
    for(int x,y,i=1; i<=n; i++) {
        cin>>x>>y;
        st[0].insert({y, x});
    }
    for(int x,y,i=1; i<=m; i++) {
        cin>>x>>y;
        st[1].insert({y, x});
    }
    for(int i=2000; i>=0; i--) {
        for(int j=2000; j>=i; j--) {
            auto t1 = (st[0].lower_bound({j+1, 0}));
            int x = 0, y = 0;
            if(t1!=st[0].end()&&(*t1).F==j+1&&(*t1).S>=i) x++;
            if(t1!=st[0].end()&&(*t1).S>=i&&(*t1).S<=j) y++;

            if(j+k > 2000) {
                dp[0][i][j] += (dp[0][i][j+1]+x);
            } else {
                auto t2 = st[1].lower_bound({j+k+1, 0});
                if(t2!=st[1].end()&&(*t2).S>=i&&(*t2).S<=j) {
dp[0][i][j] = max((dp[0][i][j+1]+x), y+dp[1][j+1][j+k]+1);
                } else {
dp[0][i][j] = max((dp[0][i][j+1]+x), y+dp[1][j+1][j+k]);
                }
            }

            auto t2 = (st[1].lower_bound({j+1, 0}));
            x = 0, y = 0;
            if(t2!=st[1].end()&&(*t2).F==j+1&&(*t2).S>=i) x++;
            if(t2!=st[1].end()&&(*t2).S>=i&&(*t2).S<=j) y++;

            if(j+k > 2000) {
                dp[1][i][j] += (dp[1][i][j+1]+x);
            } else {
                auto t3 = st[0].lower_bound({j+k+1, 0});
                if(t3!=st[0].end()&&(*t3).S>=i&&(*t3).S<=j) {
dp[1][i][j] = max((dp[1][i][j+1]+x), y+dp[0][j+1][j+k]+1);
                } else {
dp[1][i][j] = max((dp[1][i][j+1]+x), y+dp[0][j+1][j+k]);
                }
            }
        }
    }

    cout<<dp[0][0][0]<<endl;

	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 6
• Subtask 4: 0 / 4