oj.uz

Submission #591322

# Submission time Handle Problem Language Result Execution time Memory
591322 2022-07-07T09:25:42 Z 조영욱(#8419) Two Dishes (JOI19_dishes) C++17
0 / 100
 184 ms 39528 KB 
#include <bits/stdc++.h>
using namespace std;

int n,m;
long long a[1000001];
long long s[1000001];
long long p[1000001];
long long b[1000001];
long long t[1000001];
long long q[1000001];
long long asum[1000002];
long long bsum[1000002];
typedef pair<long long,long long> P;
vector<P> vec[1000001]; //P(i,j) : i ���Ϸ� ���� j��
const int sz=1048576;
long long seg[sz*2];

long long sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
    if (r<nodel||l>noder) {
        return 0;
    }
    if (l<=nodel&&noder<=r) {
        return seg[node];
    }
    int mid=(nodel+noder)/2;
    return max(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,nodel,mid));
}

void update(int i,long long val) {
    i+=sz;
    seg[i]=max(seg[i],val);
    while (i>1) {
        i/=2;
        seg[i]=max(seg[i*2],seg[i*2+1]);
    }
}

long long dp[2001][2001];
long long psum[1000001];
long long qsum[1000001];

int main() {
    long long ret=-1e18;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) {
        scanf("%lld %lld %lld",a+i,s+i,p+i);
        asum[i]=asum[i-1]+a[i];
        psum[i]=psum[i-1]+p[i];
    }
    asum[n+1]=1e18;
    for(int i=1;i<=m;i++) {
        scanf("%lld %lld %lld",b+i,t+i,q+i);
        bsum[i]=bsum[i-1]+b[i];
        qsum[i]=qsum[i-1]+q[i];
    }
    for(int i=0;i<=n;i++) {
        int ind=upper_bound(bsum,bsum+m+1,s[1]-asum[i]+1)-bsum-1;
        long long left=s[1]-asum[i]-bsum[ind];
        if (i==n&&ind==m)
        ret=max(ret,psum[i]+qsum[ind]);
        else if ((i!=n&&a[i+1]>left)||(ind!=m&&b[ind+1]>left)) {
            ret=max(ret,psum[i]+qsum[ind]);
        }
    }
    printf("%lld",ret);
    return 0;
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
dishes.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |         scanf("%lld %lld %lld",a+i,s+i,p+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf("%lld %lld %lld",b+i,t+i,q+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 39416 KB Output is correct
2 Correct 162 ms 39248 KB Output is correct
3 Correct 174 ms 39528 KB Output is correct
4 Correct 181 ms 39244 KB Output is correct
5 Incorrect 13 ms 23808 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Incorrect 14 ms 23764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Incorrect 14 ms 23764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Incorrect 14 ms 23764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Incorrect 14 ms 23764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23764 KB Output is correct
2 Incorrect 14 ms 23764 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 39416 KB Output is correct
2 Correct 162 ms 39248 KB Output is correct
3 Correct 174 ms 39528 KB Output is correct
4 Correct 181 ms 39244 KB Output is correct
5 Incorrect 13 ms 23808 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 39416 KB Output is correct
2 Correct 162 ms 39248 KB Output is correct
3 Correct 174 ms 39528 KB Output is correct
4 Correct 181 ms 39244 KB Output is correct
5 Incorrect 13 ms 23808 KB Output isn't correct
6 Halted 0 ms 0 KB -