fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. template <typename T> bool maximize(T &res, const T &val){if(res < val) return res = val, true; return false;}
  6. template <typename T> bool minimize(T &res, const T &val){if(res > val) return res = val, true; return false;}
  7.  
  8. #define ll long long
  9. #define fi first
  10. #define se second
  11. #define pb push_back
  12. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
  13. #define FORD(i, b, a) for(int i = (b), _a = (a); i >= _a; i--)
  14. #define REP(i, n) for(int i = 0, _n = (n); i < _n; i++)
  15. #define C make_pair
  16. #define MASK(i) (1LL << (i))
  17. #define TURN_ON(i, x) ((x) | MASK(i))
  18. #define TURN_OFF(i, x) ((x) & ~MASK(i))
  19. #define RE(i, x) ((x) ^ MASK(i))
  20.  
  21. const ll mod = 1e9 + 7;
  22. const ll INF = 1e15;
  23. const int maxn = 1e5 + 5;
  24. typedef pair<int, int> pi;
  25. typedef pair<int, pair<int,int>> pii;
  26. typedef pair<ll, ll> pl;
  27. typedef pair<ll, pair<ll,ll>>pll;
  28.  
  29. struct p{
  30.     int x, y, val;
  31.     p(int _x = 0, int _y = 0, int _val = 0){
  32.         x = _x;
  33.         y = _y;
  34.         val = _val;
  35.     }
  36. };
  37.  
  38. int NumGift;
  39. p arr[maxn];
  40.  
  41. void nhap(){
  42.     cin >> NumGift;
  43.     FOR(i, 1, NumGift){
  44.         cin >> arr[i].x >> arr[i].y >> arr[i].val;
  45.     }
  46. }
  47. namespace sub2{
  48.     bool check(){
  49.         return NumGift <= 1000;
  50.     }
  51.     int dp[2010][2010], val[2010][2010];
  52.     vector<int>Row, Col;
  53.     void prepare(){
  54.         FOR(i, 1, NumGift){
  55.             int x = arr[i].x, y = arr[i].y;
  56.             Row.pb(x);
  57.             Col.pb(y);
  58.         }
  59.         Row.pb(-1);
  60.         Col.pb(-1);
  61.         Row.pb((int)1e9);
  62.         Col.pb((int)1e9);
  63.         sort(Row.begin(), Row.end());
  64.         sort(Col.begin(), Col.end());
  65.         FOR(i, 1, NumGift){
  66.             int r = lower_bound(Row.begin(), Row.end(), arr[i].x) - Row.begin();
  67.             int c = lower_bound(Col.begin(), Col.end(), arr[i].y) - Col.begin();
  68.             val[r][c] += arr[i].val;
  69.         }
  70.     }
  71.     void solve(){
  72.         prepare();
  73.         int n = Row.size() - 1, m = Col.size() - 1;
  74.         FOR(i, 1, n) FOR(j, 1, m){
  75.             dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + val[i][j];
  76.         }
  77.         int ans1 = lower_bound(Row.begin(), Row.end(), (int)1e9) - Row.begin();
  78.         int ans2 = lower_bound(Col.begin(), Col.end(), (int)1e9) - Col.begin();
  79.         cout << dp[ans1][ans2];
  80.     }
  81. }
  82. namespace sub3{
  83. 	vector<int>Row, Col;
  84.     void prepare(){
  85.         FOR(i, 1, NumGift){
  86.             int x = arr[i].x, y = arr[i].y;
  87.             Row.pb(x);
  88.             Col.pb(y);
  89.         }
  90.         Row.pb(-1);
  91.         Col.pb(-1);
  92.         Row.pb((int)1e9);
  93.         Col.pb((int)1e9);
  94.         sort(Row.begin(), Row.end());
  95.         sort(Col.begin(), Col.end());
  96.         FOR(i, 1, NumGift){
  97.             int r = lower_bound(Row.begin(), Row.end(), arr[i].x) - Row.begin();
  98.             int c = lower_bound(Col.begin(), Col.end(), arr[i].y) - Col.begin();
  99.             arr[i].x = r, arr[i].y = c;
  100.         }
  101.     }
  102.     void solve(){
  103.     	FOR(i, 1, NumGift) cout << arr[i].x << " " << arr[i].y << " " << arr[i].val << '\n';
  104.     }
  105. }
  106. int main(){
  107.     ios_base::sync_with_stdio(0);
  108.     cin.tie(0); cout.tie(0);
  109.     nhap();
  110.     sub3::solve();
  111.     return 0;
  112. }
  113.  
Success #stdin #stdout 0.01s 6016KB
comments (?)
stdin
copy 
7 
1 1 9 
2 4 19 
3 4 3 
4 2 12 
5 2 13 
3 4 2 
5 2 4
stdout
copy 
1 1 9
2 4 19
3 4 3
4 2 12
5 2 13
3 4 2
5 2 4
https://ideone.com/oKDgvc
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!