Submission #563804

#	Time	Username	Problem	Language	Result	Execution time	Memory
563804		tqbfjotld	Two Dishes (JOI19_dishes)	C++14	10 / 100	218 ms	103204 KiB

dishes

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n,m;
int A[1000005];
int S[1000005];
int P[1000005];
int B[1000005];
int T[1000005];
int Q[1000005];

int prefA[1000005];
int prefB[1000005];

int mem[2005][2005];

int dp(int a, int b){
    if (mem[a][b]!=-1) return mem[a][b];
    int ans = -999999999999999999LL;
    if (a==0&&b==0) ans = 0;
    if (a!=0){
        int t = dp(a-1,b);
        if (prefA[a]+prefB[b]<=S[a-1]){
            t += P[a-1];
        }
        ans = max(ans,t);
    }
    if (b!=0){
        int t = dp(a,b-1);
        if (prefA[a]+prefB[b]<=T[b-1]){
            t += Q[b-1];
        }
        ans = max(ans,t);
    }
    return mem[a][b] = ans;
}

 main(){
    scanf("%lld%lld",&n,&m);
    for (int x = 0; x<n; x++){
        scanf("%lld%lld%lld",&A[x],&S[x],&P[x]);
    }
    for (int x = 0; x<m; x++){
        scanf("%lld%lld%lld",&B[x],&T[x],&Q[x]);
    }
    memset(mem,-1,sizeof(mem));
    for (int x = 1; x<=n; x++){
        prefA[x] = prefA[x-1]+A[x-1];
    }
    for (int x = 1; x<=m; x++){
        prefB[x] = prefB[x-1]+B[x-1];
    }
    printf("%lld",dp(n,m));

}

Compilation message (stderr)

dishes.cpp:39:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   39 |  main(){
      |  ^~~~
dishes.cpp: In function 'int main()':
dishes.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%lld%lld",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~
dishes.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         scanf("%lld%lld%lld",&A[x],&S[x],&P[x]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf("%lld%lld%lld",&B[x],&T[x],&Q[x]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 0 / 39
• Subtask 5: 0 / 11
• Subtask 6: 0 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9