oj.uz

Submission #591263

# Submission time Handle Problem Language Result Execution time Memory
591263 2022-07-07T07:37:40 Z 조영욱(#8419) Two Dishes (JOI19_dishes) C++17
0 / 100
 3470 ms 292140 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]);
        }
        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:93: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]
   93 |         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 3470 ms 292140 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 15 ms 23892 KB Output is correct
2 Correct 12 ms 23856 KB Output is correct
3 Correct 12 ms 23888 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 13 ms 23916 KB Output is correct
6 Correct 15 ms 23756 KB Output is correct
7 Correct 12 ms 23912 KB Output is correct
8 Correct 13 ms 23892 KB Output is correct
9 Correct 14 ms 23920 KB Output is correct
10 Correct 13 ms 23892 KB Output is correct
11 Correct 12 ms 23892 KB Output is correct
12 Correct 16 ms 23856 KB Output is correct
13 Incorrect 12 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 15 ms 23892 KB Output is correct
2 Correct 12 ms 23856 KB Output is correct
3 Correct 12 ms 23888 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 13 ms 23916 KB Output is correct
6 Correct 15 ms 23756 KB Output is correct
7 Correct 12 ms 23912 KB Output is correct
8 Correct 13 ms 23892 KB Output is correct
9 Correct 14 ms 23920 KB Output is correct
10 Correct 13 ms 23892 KB Output is correct
11 Correct 12 ms 23892 KB Output is correct
12 Correct 16 ms 23856 KB Output is correct
13 Incorrect 12 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 15 ms 23892 KB Output is correct
2 Correct 12 ms 23856 KB Output is correct
3 Correct 12 ms 23888 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 13 ms 23916 KB Output is correct
6 Correct 15 ms 23756 KB Output is correct
7 Correct 12 ms 23912 KB Output is correct
8 Correct 13 ms 23892 KB Output is correct
9 Correct 14 ms 23920 KB Output is correct
10 Correct 13 ms 23892 KB Output is correct
11 Correct 12 ms 23892 KB Output is correct
12 Correct 16 ms 23856 KB Output is correct
13 Incorrect 12 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 15 ms 23892 KB Output is correct
2 Correct 12 ms 23856 KB Output is correct
3 Correct 12 ms 23888 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 13 ms 23916 KB Output is correct
6 Correct 15 ms 23756 KB Output is correct
7 Correct 12 ms 23912 KB Output is correct
8 Correct 13 ms 23892 KB Output is correct
9 Correct 14 ms 23920 KB Output is correct
10 Correct 13 ms 23892 KB Output is correct
11 Correct 12 ms 23892 KB Output is correct
12 Correct 16 ms 23856 KB Output is correct
13 Incorrect 12 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 15 ms 23892 KB Output is correct
2 Correct 12 ms 23856 KB Output is correct
3 Correct 12 ms 23888 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 13 ms 23916 KB Output is correct
6 Correct 15 ms 23756 KB Output is correct
7 Correct 12 ms 23912 KB Output is correct
8 Correct 13 ms 23892 KB Output is correct
9 Correct 14 ms 23920 KB Output is correct
10 Correct 13 ms 23892 KB Output is correct
11 Correct 12 ms 23892 KB Output is correct
12 Correct 16 ms 23856 KB Output is correct
13 Incorrect 12 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 3470 ms 292140 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 3470 ms 292140 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -