이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
using namespace std;
#pragma GCC optimize("Ofast")
#define all(x) x.begin(),x.end()
void YES()
{
cout<<"YES\n";
}
void NO()
{
cout<<"NO\n";
}
struct Line
{
ll slope,intercept;
Line(ll slope , ll intercept) : slope(slope),intercept(intercept){};
ll value(ll x)
{
return x*slope+intercept;
}
ll intersection(Line y)
{
return ((y.intercept - intercept + slope - y.slope - 1ll) / (slope-y.slope));
}
void print()
{
cout<<slope<<" "<<intercept<<" ";
}
};
struct CHT
{
deque<pair<Line,ll>> lines;
void insert(ll m,ll c)
{
Line line(m,c);
while (lines.size() > 1 && lines.back().second >= lines.back().first.intersection(line))
{
lines.pop_back();
}
if (lines.empty())
{
lines.emplace_back(line,0);
return;
}
lines.emplace_back(line,lines.back().first.intersection(line));
// for (auto i : lines)
// {
// i.first.print();
// cout<<i.second<<"\n";
// }
}
ll query(ll x)
{
while (lines.size() > 1)
{
if (lines[1].first.value(x) > lines[0].first.value(x)) lines.pop_front();
else break;
}
// lines.front().first.print();
return lines.front().first.value(x);
}
ll query2(ll x)
{
auto qry = *lower_bound(lines.rbegin(), lines.rend(),
make_pair(Line(0, 0), x),
[&](const pair<Line, int> &a, const pair<Line, int> &b) {
return a.second > b.second;
});
return qry.first.value(x);
}
};
const int ALPHABET_SIZE = 26;
struct TrieNode {
TrieNode* children[ALPHABET_SIZE];
bool isEndOfWord;
TrieNode() : isEndOfWord(false) {}
};
class Trie {
public:
TrieNode* root;
Trie() {
root = new TrieNode();
}
void insert(const string& word) {
TrieNode* current = root;
for (char ch : word) {
int index = ch - 'a';
if (current->children[index] == NULL) {
current->children[index] = new TrieNode();
}
current = current->children[index];
}
current->isEndOfWord = true;
}
void deleteWord(const string& word) {
deleteWordRecursive(root, word, 0);
}
bool deleteWordRecursive(TrieNode* node, const string& word, int depth) {
if (node == nullptr) {
return false;
}
if (depth == word.length()) {
if (!node->isEndOfWord) {
return false; // Word not present in the trie
}
node->isEndOfWord = false;
// If the node has no children, it can be safely removed
return nodeHasNoChildren(node);
}
int index = word[depth] - 'a';
if (deleteWordRecursive(node->children[index], word, depth + 1)) {
// Delete the child node if it can be deleted
delete node->children[index];
node->children[index] = nullptr;
// Check if the current node has no children and is not an end-of-word node
return nodeHasNoChildren(node);
}
return false;
}
bool nodeHasNoChildren(TrieNode* node) {
for (TrieNode* child : node->children) {
if (child != nullptr) {
return false;
}
}
return !node->isEndOfWord;
}
bool search(const string& word) {
TrieNode* node = searchNode(word);
return (node != NULL && node->isEndOfWord);
}
TrieNode* searchNode(const string& word) {
TrieNode* current = root;
for (char ch : word) {
int index = ch - 'a';
if (current->children[index] == NULL) {
return NULL; // Character not found in the trie
}
current = current->children[index];
}
return current;
}
void printAllWords() {
string currentWord;
printWordsRecursive(root, currentWord);
}
void printWordsRecursive(TrieNode* node, string& currentWord) {
if (node == NULL) {
return;
}
if (node->isEndOfWord) {
cout << currentWord << endl;
}
for (int i = 0; i < ALPHABET_SIZE; ++i) {
if (node->children[i] != NULL) {
currentWord.push_back('a' + i);
printWordsRecursive(node->children[i], currentWord);
currentWord.pop_back();
}
}
}
};
vector<vector<ll>> ST(vector<ll> & a)
{
ll n = a.size();
vector<vector<ll>> st(n);
for (ll e = 0;e<n;e++)
{
st[e].push_back(a[e]);
}
for (ll k = 1;k<=20;k++)
{
for (ll e = 0;e<n-(1<<k)+1;e++)
{
st[e].push_back(__gcd(st[e][k-1],st[e+(1<<(k-1))][k-1]));
}
}
return st;
}
vector<ll> twopows;
ll FINDST(vector<vector<ll>> & st,ll l,ll r)
{
if (l > r) return 0;
if (twopows.empty())
{
twopows = vector<ll>(200001);
for (ll e = 1,d = 0;e<=200000;e++)
{
if ((1 << (d+1)) == e) d++;
twopows[e] = d;
}
}
ll k = twopows[r-l+1];
return __gcd(st[l][k],st[r-(1 << k)+1][k]);
}
struct LCT // both queries and lines are sorted in increasing order
{
ll n;
vector<Line> tree;
vector<ll> Q;
LCT(vector<ll> q)
{
Q = q;
n = q.size()-1;
tree.assign(4*n+4,Line(0,(ll)-1e18));
}
void add(Line curr,ll v = 1,ll l = 1,ll r = -1)
{
// cout<<l<<" "<<r<<"\n";
if (r == -1) r = n;
if (l == r)
{
if (curr.value(Q[l]) > tree[v].value(Q[l])) swap(curr,tree[v]);
return;
}
ll mid = (l+r)/2;
if (curr.value(Q[mid]) <= tree[v].value(Q[mid]))
{
add(curr,v*2+1,mid+1,r);
}
else
{
swap(tree[v],curr);
add(curr,v*2,l,mid);
}
}
ll find(ll ind,ll v = 1,ll l = 1,ll r = -1)
{
// cout<<tree[v].slope<<" "<<tree[v].intercept<<"\n";
if (r == -1) r = n;
if (l == r) return tree[v].value(Q[ind]);
ll mid = (l+r)/2;
if (ind <= mid) return max(tree[v].value(Q[ind]),find(ind,v*2,l,mid));
else return max(tree[v].value(Q[ind]),find(ind,v*2+1,mid+1,r));
}
};
ll get(ll a,vector<ll> & pr)
{
return pr[a] = (pr[a] == a ? a : get(pr[a],pr));
}
bool merge(ll a,ll b,vector<ll> & pr,vector<ll> & siz)
{
a = get(a,pr),b = get(b,pr);
if (a == b) return 0;
if (siz[a] > siz[b])
{
pr[b] = a;
siz[a] += siz[b];
}
else
{
pr[a] = b;
siz[b] += siz[a];
}
return 1;
}
mt19937 mt1(time(0));
ld rnd()
{
ld ANS = mt1();
ANS /= mt1.max();
return ANS;
}
void read(vector<ll> & a)
{
for (ll & i : a) cin>>i;
}
void read(vector<vector<ll>> & a)
{
for (vector<ll> & i : a)
{
for (ll & j : i) cin>>j;
}
}
void print(vector<ll> & a)
{
for (ll & i : a) cout<<i<<" ";
cout<<"\n";
}
void print(vector<vector<ll>> & a)
{
for (vector<ll> & i : a)
{
for (ll & j : i) cout<<j<<" ";
cout<<"\n";
}
}
struct BIGINT
{
vector<ll> a;
ll len;
BIGINT(ll n)
{
len = n;
a.assign(n,0ll);
}
void add(BIGINT b)
{
for (ll e = len-1;e>0;e--)
{
a[e] += b.a[e];
if (a[e] >= 10)
{
a[e-1] += 1;
a[e] -= 10;
}
}
}
void print()
{
bool f = 0;
for (ll e = 0;e<len;e++)
{
if (a[e] > 0) f = 1;
if (f) cout<<a[e];
}
if (!f) cout<<0;
cout<<"\n";
}
};
ll mod = 1e9+7;
ll mult(vector<ll> a)
{
ll answer = 1;
for (ll i : a)
{
answer *= i;
answer %= mod;
}
return answer;
}
ll binpow(ll n,ll k = mod-2)
{
bitset<31> o(k);
ll curr = 1;
for (ll e = 30;e>-1;e--)
{
curr *= curr;
curr %= mod;
if (o[e])
{
curr *= n;
curr %= mod;
}
}
return curr;
}
vector<ll> fact,invfact;
ll bincoef(ll n,ll k)
{
if (fact.empty())
{
fact = invfact = vector<ll>(500001,1);
for (ll e = 1;e<=500000;e++)
{
fact[e] = (fact[e-1]*e)%mod;
}
invfact[500000] = binpow(fact[500000]);
for (ll e = 499999;e>=0;e--)
{
invfact[e] = (invfact[e+1]*(e+1))%mod;
}
}
return mult({fact[n],invfact[n-k],invfact[k]});
}
void ans()
{
ll n,s;cin>>s>>n;
vector<vector<ll>> opt(s+1);
vector<vector<ll>> I(n);
for (ll e = 0;e<n;e++)
{
ll v,w,k;cin>>v>>w>>k;
I[e] = {v,k,w};
}
sort(I.rbegin(),I.rend());
for (vector<ll> j : I)
{
for (ll i = 0;i<j[1] && opt[j[2]].size()*j[2] < s;i++)
{
opt[j[2]].push_back(j[0]);
}
}
vector<ll> dp(s+1);
for (ll w = 1;w<=s;w++)
{
for (ll v : opt[w])
{
for (ll i = s;i>=w;i--)
{
dp[i] = max(dp[i],dp[i-w]+v);
}
}
}
cout<<dp[s]<<"\n";
}
int main()
{
cin.tie(0);cout.tie(0);
ios_base::sync_with_stdio(0);
ll t = 1;
srand(time(0));
cout<<fixed<<setprecision(11);
for (ll e = 1;e<=t;e++)
{
ans();
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
knapsack.cpp: In member function 'bool Trie::deleteWordRecursive(TrieNode*, const string&, int)':
knapsack.cpp:109:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
109 | if (depth == word.length()) {
| ~~~~~~^~~~~~~~~~~~~~~~
knapsack.cpp: In function 'void ans()':
knapsack.cpp:403:49: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'long long int' [-Wsign-compare]
403 | for (ll i = 0;i<j[1] && opt[j[2]].size()*j[2] < s;i++)
| ~~~~~~~~~~~~~~~~~~~~~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |