oj.uz

Submission #434166

# Submission time Handle Problem Language Result Execution time Memory
434166 2021-06-20T16:33:45 Z TLP39 Jelly Flavours (IOI20_jelly) C++14
0 / 100
 76 ms 78660 KB 
#include "jelly.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int MAX_I=2000000000;
int n;
pii c[2000];
int ans;
int jelly_num[2001][10001];
map<int,int> mp;
int min_b[10001];
int qs,cou;
int find_maximum_unique(int x, int y, std::vector<int> a, std::vector<int> b) {
	n = a.size();
	for(int i=0;i<n;i++) c[i]={a[i],b[i]};
	sort(c,c+n);
	memset(jelly_num,0,sizeof jelly_num);
	for(int i=n-1;i>=0;i--)
	{
		mp[c[i].second]++;
		qs=0;cou=0;
		for(auto it=mp.begin();it!=mp.end();it++)
		{
			for(int j=0;j<(it->second);j++)
			{
				for(int ii=qs;ii<qs+(it->first) && ii<=y;ii++)
				{
					jelly_num[n-i][ii]=cou;
                }	
                qs+=(it->first); cou++;
                if(qs>y) break;
            }
            if(qs>y) break;
        }
        for(int j=qs;j<=y;j++) jelly_num[n-i][j]=cou;
    }
    for(int i=1;i<=x;i++) min_b[i]=MAX_I;
    min_b[0]=0;
    ans=jelly_num[n][y];
    for(int i=0;i<n;i++)
    {
        for(int j=x;j>=0;j--)
        {
            if(j>=c[i].first) min_b[j]=min(min_b[j-c[i].first],min_b[j]+c[i].second);
            else min_b[j]=min(MAX_I,min_b[j]+c[i].second);
            if(min_b[j]<=y)
            {
                ans=max(ans,jelly_num[n-1-i][y-min_b[j]]);
            }
        }
    }
    return ans;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 78556 KB 1st lines differ - on the 1st token, expected: '8', found: '4'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 78556 KB 1st lines differ - on the 1st token, expected: '8', found: '4'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 78620 KB 1st lines differ - on the 1st token, expected: '689', found: '642'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 78584 KB 1st lines differ - on the 1st token, expected: '62', found: '2'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 78660 KB 1st lines differ - on the 1st token, expected: '154', found: '49'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 78556 KB 1st lines differ - on the 1st token, expected: '8', found: '4'
2 Halted 0 ms 0 KB -