Submission #563908

#	Time	Username	Problem	Language	Result	Execution time	Memory
563908		tqbfjotld	Two Dishes (JOI19_dishes)	C++14	15 / 100	183 ms	47628 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 prefA2[1000005];
int prefB2[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];
    }
    if (n<=2000&&m<=2000){
        printf("%lld\n",dp(n,m));
        return 0;
    }
    for (int x = 1; x<=n; x++){
        prefA2[x] = prefA2[x-1]+P[x-1];
    }
    for (int x = 1; x<=m; x++){
        prefB2[x] = prefB2[x-1]+Q[x-1];
    }
    int ans = -999999999999999999;
    for (int x = 0; x<=n; x++){
        if (prefA[x]<=S[0]){
            int t = S[0]-prefA[x];
            int t2 = upper_bound(prefB,prefB+m+1,t)-prefB-1;
            ans = max(ans,prefA2[x]+prefB2[t2]);
        }
    }
    printf("%lld",ans);

    /*for (int x = 0; x<=n; x++){
        for (int y = 0; y<=m; y++){
            printf("%4lld ",dp(x,y));
        }
        printf("\n");
    }*/

}

Compilation message (stderr)

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

• Subtask 1: 5 / 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