oj.uz

Submission #591262

# Submission time Handle Problem Language Result Execution time Memory
591262 2022-07-07T07:32:37 Z 조영욱(#8419) Two Dishes (JOI19_dishes) C++17
0 / 100
 3532 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];
        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]);
        }
        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:90: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]
   90 |         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 3532 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 12 ms 23892 KB Output is correct
2 Correct 13 ms 23808 KB Output is correct
3 Correct 12 ms 23892 KB Output is correct
4 Correct 15 ms 23876 KB Output is correct
5 Correct 11 ms 23892 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23804 KB Output is correct
8 Correct 12 ms 23904 KB Output is correct
9 Correct 15 ms 23892 KB Output is correct
10 Correct 13 ms 24020 KB Output is correct
11 Correct 12 ms 23892 KB Output is correct
12 Correct 13 ms 23896 KB Output is correct
13 Incorrect 16 ms 23768 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 13 ms 23808 KB Output is correct
3 Correct 12 ms 23892 KB Output is correct
4 Correct 15 ms 23876 KB Output is correct
5 Correct 11 ms 23892 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23804 KB Output is correct
8 Correct 12 ms 23904 KB Output is correct
9 Correct 15 ms 23892 KB Output is correct
10 Correct 13 ms 24020 KB Output is correct
11 Correct 12 ms 23892 KB Output is correct
12 Correct 13 ms 23896 KB Output is correct
13 Incorrect 16 ms 23768 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 13 ms 23808 KB Output is correct
3 Correct 12 ms 23892 KB Output is correct
4 Correct 15 ms 23876 KB Output is correct
5 Correct 11 ms 23892 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23804 KB Output is correct
8 Correct 12 ms 23904 KB Output is correct
9 Correct 15 ms 23892 KB Output is correct
10 Correct 13 ms 24020 KB Output is correct
11 Correct 12 ms 23892 KB Output is correct
12 Correct 13 ms 23896 KB Output is correct
13 Incorrect 16 ms 23768 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 13 ms 23808 KB Output is correct
3 Correct 12 ms 23892 KB Output is correct
4 Correct 15 ms 23876 KB Output is correct
5 Correct 11 ms 23892 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23804 KB Output is correct
8 Correct 12 ms 23904 KB Output is correct
9 Correct 15 ms 23892 KB Output is correct
10 Correct 13 ms 24020 KB Output is correct
11 Correct 12 ms 23892 KB Output is correct
12 Correct 13 ms 23896 KB Output is correct
13 Incorrect 16 ms 23768 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 13 ms 23808 KB Output is correct
3 Correct 12 ms 23892 KB Output is correct
4 Correct 15 ms 23876 KB Output is correct
5 Correct 11 ms 23892 KB Output is correct
6 Correct 12 ms 23764 KB Output is correct
7 Correct 12 ms 23804 KB Output is correct
8 Correct 12 ms 23904 KB Output is correct
9 Correct 15 ms 23892 KB Output is correct
10 Correct 13 ms 24020 KB Output is correct
11 Correct 12 ms 23892 KB Output is correct
12 Correct 13 ms 23896 KB Output is correct
13 Incorrect 16 ms 23768 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 3532 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 3532 ms 292020 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -