結果
問題 | No.165 四角で囲え! |
ユーザー |
![]() |
提出日時 | 2014-12-21 21:00:46 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 184 ms / 5,000 ms |
コード長 | 1,936 bytes |
コンパイル時間 | 1,187 ms |
コンパイル使用メモリ | 104,660 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-26 03:11:37 |
合計ジャッジ時間 | 3,641 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 19 |
ソースコード
#include <algorithm> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <functional> #include <iostream> #include <map> #include <memory> #include <queue> #include <set> #include <sstream> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; #define sz size() #define pb push_back #define mp make_pair #define fi first #define se second #define all(c) (c).begin(), (c).end() #define rep(i,a,b) for(long long i=(a);i<(b);++i) #define clr(a, b) memset((a), (b) ,sizeof(a)) #define MOD 1000000007 int main(){ int n,B; cin>>n>>B; vector<pair<int,pair<int,int> > > p; rep(i,0,n){ int a,b,c; cin>>a>>b>>c; p.pb(mp(a*2,mp(b*2,c))); } sort(all(p)); set<int> se; rep(i,0,p.sz){ se.insert(p[i].se.fi-1); } se.insert(2000000001); vector<int> d(all(se)); int mx = 0; rep(i,0,d.sz){ rep(j,i+1,d.sz){ vector<pair<int,int> > m; rep(k,0,p.sz){ if(d[i]<p[k].se.fi&&d[j]>p[k].se.fi){ m.pb(mp(p[k].fi, p[k].se.se)); } } int index1 = 0; int index2 = 0; int c = 0; int e = 0; for(;;){ if(e<=B){ for(;;){ c++; e+=m[index1].se; index1++; if(index1==m.sz)break; if(m[index1-1].fi==m[index1].fi)continue; break; } } else{ for(;;){ c--; e-=m[index2].se; index2++; if(index2==m.sz)break; if(m[index2-1].fi==m[index2].fi)continue; break; } } if(e<=B){ mx = max(mx,c); if(index1==m.sz)break; } } } } cout << mx << endl; return 0; } /* Y軸方向はnC2で全探索してX軸方向はしゃくとり法やるだけな問題です。O(n^3)。 */