oj.uz

Submission #591261

# Submission time Handle Problem Language Result Execution time Memory
591261 2022-07-07T07:31:19 Z 조영욱(#8419) Two Dishes (JOI19_dishes) C++17
0 / 100
 3650 ms 305656 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];

int main() {
    long long ret=0;
    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];
    }
    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];
    }
    bsum[n+1]=1e18;
    for(int i=1;i<=n;i++) {
        long long left=s[i]-asum[i];
        if (left<0) {
            continue;
        }
        int ind=upper_bound(bsum,bsum+m+1,left)-bsum-1;
        if (ind==m) {
            ret+=p[i];
            continue;
        }
        vec[i].push_back(P(ind,p[i]));
    }
    for(int i=1;i<=m;i++) {
        long long left=t[i]-bsum[i];
        if (left<0) {
            continue;
        }
        int ind=upper_bound(asum,asum+n+1,left)-asum;
        ret+=q[i];
        vec[ind].push_back(P(i-1,-q[i]));
    }
    for(int i=1;i<=n;i++) {
        sort(vec[i].begin(),vec[i].end());
        reverse(vec[i].begin(),vec[i].end());
    }
    for(int x=1;x<=n;x++) {
        vector<P> upd;
        long long pl=0;
        long long mx=-1e18;
        for(int i=0;i<=m;i++) {
            dp[x][i]=max(mx,dp[x-1][i]);
            mx=max(mx,dp[x-1][i]);
        }
        int pr=m;
        for(int i=0;i<vec[x].size();i++) {
            for(int j=pr;j>vec[x][i].first;j--) {
                dp[x][j]+=pl;
            }
            pl+=vec[x][i].second;
            pr=vec[x][i].first;
        }
        for(int j=pr;j>=0;j--) {
            dp[x][j]+=pl;
        }
    }
    long long mx=-1e18;
    for(int i=0;i<=m;i++) {
        mx=max(mx,dp[n][i]);
    }
    printf("%lld",mx+ret);
    return 0;
}

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:87:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for(int i=0;i<vec[x].size();i++) {
      |                     ~^~~~~~~~~~~~~~
dishes.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     scanf("%d %d",&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+i,s+i,p+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:49:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         scanf("%lld %lld %lld",b+i,t+i,q+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 3650 ms 305656 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23892 KB Output is correct
2 Correct 13 ms 23800 KB Output is correct
3 Correct 13 ms 23824 KB Output is correct
4 Correct 14 ms 23796 KB Output is correct
5 Correct 16 ms 23800 KB Output is correct
6 Correct 13 ms 23800 KB Output is correct
7 Correct 12 ms 23860 KB Output is correct
8 Correct 14 ms 23872 KB Output is correct
9 Correct 13 ms 23796 KB Output is correct
10 Correct 12 ms 23796 KB Output is correct
11 Correct 12 ms 23800 KB Output is correct
12 Correct 13 ms 23892 KB Output is correct
13 Incorrect 13 ms 23884 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23892 KB Output is correct
2 Correct 13 ms 23800 KB Output is correct
3 Correct 13 ms 23824 KB Output is correct
4 Correct 14 ms 23796 KB Output is correct
5 Correct 16 ms 23800 KB Output is correct
6 Correct 13 ms 23800 KB Output is correct
7 Correct 12 ms 23860 KB Output is correct
8 Correct 14 ms 23872 KB Output is correct
9 Correct 13 ms 23796 KB Output is correct
10 Correct 12 ms 23796 KB Output is correct
11 Correct 12 ms 23800 KB Output is correct
12 Correct 13 ms 23892 KB Output is correct
13 Incorrect 13 ms 23884 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23892 KB Output is correct
2 Correct 13 ms 23800 KB Output is correct
3 Correct 13 ms 23824 KB Output is correct
4 Correct 14 ms 23796 KB Output is correct
5 Correct 16 ms 23800 KB Output is correct
6 Correct 13 ms 23800 KB Output is correct
7 Correct 12 ms 23860 KB Output is correct
8 Correct 14 ms 23872 KB Output is correct
9 Correct 13 ms 23796 KB Output is correct
10 Correct 12 ms 23796 KB Output is correct
11 Correct 12 ms 23800 KB Output is correct
12 Correct 13 ms 23892 KB Output is correct
13 Incorrect 13 ms 23884 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23892 KB Output is correct
2 Correct 13 ms 23800 KB Output is correct
3 Correct 13 ms 23824 KB Output is correct
4 Correct 14 ms 23796 KB Output is correct
5 Correct 16 ms 23800 KB Output is correct
6 Correct 13 ms 23800 KB Output is correct
7 Correct 12 ms 23860 KB Output is correct
8 Correct 14 ms 23872 KB Output is correct
9 Correct 13 ms 23796 KB Output is correct
10 Correct 12 ms 23796 KB Output is correct
11 Correct 12 ms 23800 KB Output is correct
12 Correct 13 ms 23892 KB Output is correct
13 Incorrect 13 ms 23884 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23892 KB Output is correct
2 Correct 13 ms 23800 KB Output is correct
3 Correct 13 ms 23824 KB Output is correct
4 Correct 14 ms 23796 KB Output is correct
5 Correct 16 ms 23800 KB Output is correct
6 Correct 13 ms 23800 KB Output is correct
7 Correct 12 ms 23860 KB Output is correct
8 Correct 14 ms 23872 KB Output is correct
9 Correct 13 ms 23796 KB Output is correct
10 Correct 12 ms 23796 KB Output is correct
11 Correct 12 ms 23800 KB Output is correct
12 Correct 13 ms 23892 KB Output is correct
13 Incorrect 13 ms 23884 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 3650 ms 305656 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 3650 ms 305656 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -