제출 #1324638

#제출 시각아이디문제언어결과실행 시간메모리
1324638Valters07Two Dishes (JOI19_dishes)C++20
10 / 100
25 ms31992 KiB
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define ld long double
#define en exit(0);
#define pb push_back
#define fi first
#define se second
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 2e3 + 5;
const ll INF = 1e18 + 5;
ll A[N], S[N], P[N], B[N], T[N], Q[N];
ll prefA[N], prefB[N];
ll prefP[N], prefQ[N];
ll dp[N][N];
int main()
{
    fio
//    ifstream cin("in.in");
    int n, m;
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
        cin >> A[i] >> S[i] >> P[i];
    for(int i = 1;i <= m;i++)
        cin >> B[i] >> T[i] >> Q[i];
    for(int i = 1;i <= n;i++)
        prefA[i] = prefA[i - 1] + A[i],
        prefP[i] = prefP[i - 1] + P[i];
    for(int i = 1;i <= m;i++)
        prefB[i] = prefB[i - 1] + B[i],
        prefQ[i] = prefQ[i - 1] + Q[i];
    // initialize the DP
    for(int i = 0;i <= n;i++)
        for(int j = 0;j <= m;j++)
            dp[i][j] = -INF;
    dp[0][0] = 0;
    for(int i = 0;i <= n;i++)
    {
        for(int j = 0;j <= m;j++)
        {
            // take IOI Donburi
            if(i - 1 >= 0)
            {
                ll pl = (prefA[i] + prefB[j] <= S[i] ? 1 : 0);
                dp[i][j] = max(dp[i][j], dp[i - 1][j] + pl);
            }
            // take JOI Curry
            if(j - 1 >= 0)
            {
                ll pl = (prefA[i] + prefB[j] <= T[j] ? 1 : 0);
                dp[i][j] = max(dp[i][j], dp[i][j - 1] + pl);
            }
        }
    }
    cout << dp[n][m];
    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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...