제출 #1089401

#제출 시각아이디문제언어결과실행 시간메모리
1089401MagnusCarlsen321Knapsack (NOI18_knapsack)C++17
100 / 100
54 ms8068 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...