結果
問題 |
No.165 四角で囲え!
|
ユーザー |
|
提出日時 | 2022-08-18 20:30:22 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 160 ms / 5,000 ms |
コード長 | 1,349 bytes |
コンパイル時間 | 4,666 ms |
コンパイル使用メモリ | 266,640 KB |
最終ジャッジ日時 | 2025-01-30 23:56:21 |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 19 |
ソースコード
#include<bits/stdc++.h> using namespace std; #include<atcoder/all> using namespace atcoder; using ll = long long; int n,b; vector<int> x,y,p; void solve(){ { set<int> st; for(int i = 0;i<n;i++){ st.insert(x[i]); } int idx = 0; map<int,int> mp; for(auto &i:st){ mp[i] = idx++; } for(int i = 0;i<n;i++){ x[i] = mp[x[i]]; } } { set<int> st; for(int i = 0;i<n;i++){ st.insert(y[i]); } int idx = 0; map<int,int> mp; for(auto &i:st){ mp[i] = idx++; } for(int i = 0;i<n;i++){ y[i] = mp[y[i]]; } } vector<vector<pair<int,int>>> binp(400); for(int i = 0;i<n;i++){ //cerr<<x[i]<<' '<<y[i]<<' '<<p[i]<<endl; binp[x[i]].push_back(pair<int,int>(y[i],p[i])); } int ans = 0; for(int _ = 0;_<400;_++){ vector<int> sump(400),sumc(400); for(int x =_;x<400;x++){ for(auto &[y,p]:binp[x]){ sump[y] += p; sumc[y] += 1; } queue<int> Q; int curSum=0; int cur = 0; for(int i = 0;i<400;i++){ Q.push(i); cur += sumc[i]; curSum += sump[i]; while(curSum>b){ int idx = Q.front(); cur -= sumc[idx]; curSum -= sump[idx]; Q.pop(); } ans = max(ans,cur); } } } cout<<ans<<endl; } signed main(){ cin.tie(nullptr); ios::sync_with_stdio(false); cin >> n >> b; x = y = p = vector<int>(n); for(int i = 0;i<n;i++)cin >> x[i] >> y[i] >> p[i]; solve(); }