Submission #6830717


Source Code Expand

Copy
  //shan61916
#include <bits/stdc++.h>
  using namespace std;
typedef   long long ll;
typedef   unsigned long long ull ;
typedef   double dll ;

#define   mp make_pair
#define   pb push_back
#define   ff first 
#define   ss second
#define   IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define   endl "\n" 
#define   pll pair<ll, ll>
#define   all(x) x.begin(), x.end()
#define   vll vector<ll> 
unordered_map<ll, ll> parent ;
void makeset(ll x) {
	parent[x] = x;
}
ll findset(ll x) {
	if(x == parent[x]) return x;
	return parent[x] = findset(parent[x]) ;
}
void unioset(ll x, ll y) {

	if(x > y) swap(x, y);
	parent[y] = x;
} 
int main(){
 IOS
#ifdef SHAN
    freopen("input.txt" , "r" , stdin);  
#endif
  ll n, m;
  cin >> n >> m;
  vector<pll> vc ;
  for(ll i = 0; i < n; i++) {
  	ll x, y;
  	cin >> x >> y;
  	if(x <= m) {
  		vc.pb(mp(y, x));
  	}
  }
  for(ll i = 0; i <= m; i++) makeset(i) ;
  sort(all(vc), greater<pll>());
  // vector<ll> visited(m+1, false);
  ll sum = 0;
  for(auto it: vc) {
      ll x = it.first, y = it.second ;
      y = m - y;
      ll tt = findset(y+1) ;
      tt-- ;
      if(tt >=0) {
      	sum+=x;
      	unioset(tt, tt+1) ;
      }
  }
  cout << sum << endl;
  return 0;
} //good night.

Submission Info

Submission Time
Task D - Summer Vacation
User shan61916
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1304 Byte
Status AC
Exec Time 52 ms
Memory 6000 KB

Judge Result

Set Name All Sample
Score / Max Score 400 / 400 0 / 0
Status
AC × 21
AC × 3
Set Name Test Cases
All sample_01, sample_02, sample_03, testcase_01, testcase_02, testcase_03, testcase_04, testcase_05, testcase_06, testcase_07, testcase_08, testcase_09, testcase_10, testcase_11, testcase_12, testcase_13, testcase_14, testcase_15, testcase_16, testcase_17, testcase_18
Sample sample_01, sample_02, sample_03
Case Name Status Exec Time Memory
sample_01 AC 1 ms 256 KB
sample_02 AC 1 ms 256 KB
sample_03 AC 1 ms 256 KB
testcase_01 AC 10 ms 2824 KB
testcase_02 AC 5 ms 1932 KB
testcase_03 AC 20 ms 1784 KB
testcase_04 AC 49 ms 6000 KB
testcase_05 AC 49 ms 6000 KB
testcase_06 AC 19 ms 1932 KB
testcase_07 AC 43 ms 5872 KB
testcase_08 AC 16 ms 1912 KB
testcase_09 AC 36 ms 4720 KB
testcase_10 AC 52 ms 6000 KB
testcase_11 AC 42 ms 5488 KB
testcase_12 AC 12 ms 1656 KB
testcase_13 AC 45 ms 6000 KB
testcase_14 AC 36 ms 5616 KB
testcase_15 AC 4 ms 768 KB
testcase_16 AC 40 ms 5872 KB
testcase_17 AC 9 ms 1148 KB
testcase_18 AC 52 ms 6000 KB