oj.uz

Submission #591268

# Submission time Handle Problem Language Result Execution time Memory
591268 2022-07-07T07:53:16 Z 조영욱(#8419) Two Dishes (JOI19_dishes) C++17
0 / 100
 3332 ms 292020 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];
        if (ind==n+1) {
            continue;
        }
        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 i=1;i<=m;i++) {
        dp[0][i]=-1e18;
    }
    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]);
        }
        for(int i=0;i<vec[x].size();i++) {
            for(int j=0;j<=vec[x][i].first;j++) {
                dp[x][j]+=vec[x][i].second;
            }
        }
    }
    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:92: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]
   92 |         for(int i=0;i<vec[x].size();i++) {
      |                     ~^~~~~~~~~~~~~~
dishes.cpp:86:19: warning: unused variable 'pl' [-Wunused-variable]
   86 |         long long pl=0;
      |                   ^~
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 3332 ms 292020 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 16 ms 23892 KB Output is correct
2 Correct 14 ms 23816 KB Output is correct
3 Correct 14 ms 23892 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 12 ms 23912 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23912 KB Output is correct
8 Correct 11 ms 23828 KB Output is correct
9 Correct 12 ms 23912 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 12 ms 23792 KB Output is correct
12 Correct 13 ms 23892 KB Output is correct
13 Incorrect 16 ms 23764 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23892 KB Output is correct
2 Correct 14 ms 23816 KB Output is correct
3 Correct 14 ms 23892 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 12 ms 23912 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23912 KB Output is correct
8 Correct 11 ms 23828 KB Output is correct
9 Correct 12 ms 23912 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 12 ms 23792 KB Output is correct
12 Correct 13 ms 23892 KB Output is correct
13 Incorrect 16 ms 23764 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23892 KB Output is correct
2 Correct 14 ms 23816 KB Output is correct
3 Correct 14 ms 23892 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 12 ms 23912 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23912 KB Output is correct
8 Correct 11 ms 23828 KB Output is correct
9 Correct 12 ms 23912 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 12 ms 23792 KB Output is correct
12 Correct 13 ms 23892 KB Output is correct
13 Incorrect 16 ms 23764 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23892 KB Output is correct
2 Correct 14 ms 23816 KB Output is correct
3 Correct 14 ms 23892 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 12 ms 23912 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23912 KB Output is correct
8 Correct 11 ms 23828 KB Output is correct
9 Correct 12 ms 23912 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 12 ms 23792 KB Output is correct
12 Correct 13 ms 23892 KB Output is correct
13 Incorrect 16 ms 23764 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23892 KB Output is correct
2 Correct 14 ms 23816 KB Output is correct
3 Correct 14 ms 23892 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 12 ms 23912 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23912 KB Output is correct
8 Correct 11 ms 23828 KB Output is correct
9 Correct 12 ms 23912 KB Output is correct
10 Correct 12 ms 23892 KB Output is correct
11 Correct 12 ms 23792 KB Output is correct
12 Correct 13 ms 23892 KB Output is correct
13 Incorrect 16 ms 23764 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 3332 ms 292020 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 3332 ms 292020 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -