oj.uz

Submission #591270

# Submission time Handle Problem Language Result Execution time Memory
591270 2022-07-07T07:59:22 Z 조영욱(#8419) Two Dishes (JOI19_dishes) C++17
10 / 100
 3435 ms 295072 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 3435 ms 292160 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 15 ms 23860 KB Output is correct
3 Correct 12 ms 23892 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 12 ms 23820 KB Output is correct
6 Correct 12 ms 23812 KB Output is correct
7 Correct 12 ms 23892 KB Output is correct
8 Correct 12 ms 23892 KB Output is correct
9 Correct 13 ms 23844 KB Output is correct
10 Correct 13 ms 23892 KB Output is correct
11 Correct 15 ms 23892 KB Output is correct
12 Correct 12 ms 23800 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Correct 13 ms 23892 KB Output is correct
15 Correct 13 ms 23808 KB Output is correct
16 Correct 13 ms 23856 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 15 ms 23860 KB Output is correct
3 Correct 12 ms 23892 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 12 ms 23820 KB Output is correct
6 Correct 12 ms 23812 KB Output is correct
7 Correct 12 ms 23892 KB Output is correct
8 Correct 12 ms 23892 KB Output is correct
9 Correct 13 ms 23844 KB Output is correct
10 Correct 13 ms 23892 KB Output is correct
11 Correct 15 ms 23892 KB Output is correct
12 Correct 12 ms 23800 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Correct 13 ms 23892 KB Output is correct
15 Correct 13 ms 23808 KB Output is correct
16 Correct 13 ms 23856 KB Output is correct
17 Correct 33 ms 55424 KB Output is correct
18 Correct 33 ms 55368 KB Output is correct
19 Correct 35 ms 55492 KB Output is correct
20 Correct 31 ms 55380 KB Output is correct
21 Correct 31 ms 54228 KB Output is correct
22 Correct 33 ms 55380 KB Output is correct
23 Correct 34 ms 55436 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 15 ms 23860 KB Output is correct
3 Correct 12 ms 23892 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 12 ms 23820 KB Output is correct
6 Correct 12 ms 23812 KB Output is correct
7 Correct 12 ms 23892 KB Output is correct
8 Correct 12 ms 23892 KB Output is correct
9 Correct 13 ms 23844 KB Output is correct
10 Correct 13 ms 23892 KB Output is correct
11 Correct 15 ms 23892 KB Output is correct
12 Correct 12 ms 23800 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Correct 13 ms 23892 KB Output is correct
15 Correct 13 ms 23808 KB Output is correct
16 Correct 13 ms 23856 KB Output is correct
17 Correct 33 ms 55424 KB Output is correct
18 Correct 33 ms 55368 KB Output is correct
19 Correct 35 ms 55492 KB Output is correct
20 Correct 31 ms 55380 KB Output is correct
21 Correct 31 ms 54228 KB Output is correct
22 Correct 33 ms 55380 KB Output is correct
23 Correct 34 ms 55436 KB Output is correct
24 Runtime error 3428 ms 295072 KB Execution killed with signal 11
25 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 15 ms 23860 KB Output is correct
3 Correct 12 ms 23892 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 12 ms 23820 KB Output is correct
6 Correct 12 ms 23812 KB Output is correct
7 Correct 12 ms 23892 KB Output is correct
8 Correct 12 ms 23892 KB Output is correct
9 Correct 13 ms 23844 KB Output is correct
10 Correct 13 ms 23892 KB Output is correct
11 Correct 15 ms 23892 KB Output is correct
12 Correct 12 ms 23800 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Correct 13 ms 23892 KB Output is correct
15 Correct 13 ms 23808 KB Output is correct
16 Correct 13 ms 23856 KB Output is correct
17 Correct 33 ms 55424 KB Output is correct
18 Correct 33 ms 55368 KB Output is correct
19 Correct 35 ms 55492 KB Output is correct
20 Correct 31 ms 55380 KB Output is correct
21 Correct 31 ms 54228 KB Output is correct
22 Correct 33 ms 55380 KB Output is correct
23 Correct 34 ms 55436 KB Output is correct
24 Runtime error 3428 ms 295072 KB Execution killed with signal 11
25 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 15 ms 23860 KB Output is correct
3 Correct 12 ms 23892 KB Output is correct
4 Correct 13 ms 23892 KB Output is correct
5 Correct 12 ms 23820 KB Output is correct
6 Correct 12 ms 23812 KB Output is correct
7 Correct 12 ms 23892 KB Output is correct
8 Correct 12 ms 23892 KB Output is correct
9 Correct 13 ms 23844 KB Output is correct
10 Correct 13 ms 23892 KB Output is correct
11 Correct 15 ms 23892 KB Output is correct
12 Correct 12 ms 23800 KB Output is correct
13 Correct 12 ms 23764 KB Output is correct
14 Correct 13 ms 23892 KB Output is correct
15 Correct 13 ms 23808 KB Output is correct
16 Correct 13 ms 23856 KB Output is correct
17 Correct 33 ms 55424 KB Output is correct
18 Correct 33 ms 55368 KB Output is correct
19 Correct 35 ms 55492 KB Output is correct
20 Correct 31 ms 55380 KB Output is correct
21 Correct 31 ms 54228 KB Output is correct
22 Correct 33 ms 55380 KB Output is correct
23 Correct 34 ms 55436 KB Output is correct
24 Runtime error 3428 ms 295072 KB Execution killed with signal 11
25 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 3435 ms 292160 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 3435 ms 292160 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -