結果
問題 |
No.165 四角で囲え!
|
ユーザー |
|
提出日時 | 2017-08-02 16:58:34 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 219 ms / 5,000 ms |
コード長 | 2,173 bytes |
コンパイル時間 | 1,929 ms |
コンパイル使用メモリ | 177,516 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-26 03:39:36 |
合計ジャッジ時間 | 4,570 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 19 |
ソースコード
#include <bits/stdc++.h> #define ll long long #define INF 1000000005 #define MOD 1000000007 #define EPS 1e-10 #define rep(i,n) for(int i=0;i<(int)n;++i) #define each(a, b) for(auto (a): (b)) #define all(v) (v).begin(),(v).end() #define fi first #define se second #define pb push_back #define show(x) cout <<#x<<" = "<<(x)<<endl #define spair(p) cout <<#p<<": "<<p.fi<<" "<<p.se<<endl #define svec(v) cout<<#v<<":";rep(kbrni,v.size())cout<<" "<<v[kbrni];cout<<endl #define sset(s) cout<<#s<<":";each(kbrni,s)cout <<" "<<kbrni;cout<<endl using namespace std; typedef pair<int,int>P; typedef pair<P,int>PP; const int MAX_N = 100005; vector<P> vec[400]; int main() { cin.tie(0); ios::sync_with_stdio(false); int n,B; cin >> n >> B; vector<int> p(n); vector<int> x(n),y(n); vector<PP> pos(n); rep(i,n){ cin >> x[i] >> y[i] >> p[i];; pos[i] = PP(P(y[i],x[i]),i); } sort(all(pos)); sort(all(x)); sort(all(y)); x.erase(unique(all(x)),x.end()); x.pb(INF); y.erase(unique(all(y)),y.end()); int sz = (int)y.size(); rep(i,n){ P a = pos[i].fi; int b = pos[i].se; int id = lower_bound(all(y),a.fi) - y.begin(); vec[id].pb(P(a.se,b)); } int ans = 0; rep(i,x.size()){ for(int j=i+1;j<(int)x.size();j++){ deque<P> deq; int sm = 0; int cnt = 0; rep(k,sz){ int pl = 0; int num = 0; rep(l,vec[k].size()){ P a = vec[k][l]; if(x[i] <= a.fi && a.fi < x[j]){ pl += p[a.se]; num++; } } sm += pl; cnt += num; deq.pb(P(pl,num)); if(sm <= B){ ans = max(ans,cnt); }else{ while(sm > B){ sm -= deq[0].fi; cnt -= deq[0].se; deq.pop_front(); } } } } } cout << ans << endl; return 0; }