Sqrt Decomposition |  C++ Both 100% | 108ms/72.8MB | explanation
\nclass Solution {\npublic:\n    int findMaximizedCapital(int k, int w, vector<int>& p, vector<int>& c) {\n        int n=p.size(),ans=0,it=0,nn=0,ma=0,mb=0,sz=0
```\nclass Solution {\npublic:\n    int findMaximizedCapital(int k, int w, vector<int>& p, vector<int>& c) {\n        int n=p.size(),ans=0,it=0,nn=0,ma=0,mb=0,sz=0,sq[101][101]={};\n        for(int i=0;i<n;++i)\n            if(c[i]<=w){\n                sq[p[i]/100][p[i]%100]++;\n                sq[p[i]/100][100]++;\n                ma=max(ma,p[i]);\n                sz++;\n            }\n        mb=ma/100;\n        pair <int,int> a[max(n-sz,1)];\n        for(int i=0;i<n;++i)\n            if(c[i]>w)\n                a[nn++]={c[i],p[i]};\n        for(sort(a,a+nn);k--&&sz;){\n            if(sq[mb][ma%100]==0){\n                while(sq[mb][100]==0)--mb;\n                ma=99;\n                while(sq[mb][ma]==0)--ma;\n                ma+=mb*100;\n            }\n            w+=ma;\n            sq[mb][ma%100]--;\n            sq[mb][100]--;\n            sz--;\n            for(;it<nn;++it){\n                if(a[it].first>w)break;\n                sq[a[it].second/100][a[it].second%100]++;\n                sq[a[it].second/100][100]++;\n                sz++;\n                if(a[it].second>=ma){\n                    ma=a[it].second;\n                    mb=ma/100;\n                }\n            }\n        }\n        return w;\n    }\n};\n```\n1.The best choice in each round is to pick the largest value from all c<=w.\n2.After the selection, the value of w will be the reference point for the next round.\n3.Using this strategy, w after k rounds is the answer.\n4.So we need a data structure that can do the three functions of "query the maximum value", "input a legal p value", and "delete the maximum value".\n5.If we sort by the value of c first, then we can use a fixed right pointer to gradually find a valid {c,p} (c<=w).\n6.Since the value of p is <= 10000, we can divide it into 100 blocks, each of which is responsible for managing 2 kinds of information: how many elements are in this block and counting the number of each element.\n7.You can use the lazy tag to record the last selected maximum value, and when the value you put in is larger than the lazy tag, you can update it by the way.
['C++']