Contest Duration: - (local time) (100 minutes) Back to Home

Submission #6819021

Source Code Expand

Copy
```/*Author: Satyajeet Singh, Delhi Technological University*/
import java.io.*;
import java.util.*;
import java.text.*;
import java.lang.*;
import java.math.*;

public class Main{
/*********************************************Constants******************************************/
static PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static long mod=(long)1e9+7;
static long mod1=998244353;
static boolean sieve[];
static ArrayList<Integer> primes;
static ArrayList<Long> factorial;
static HashSet<Pair> graph[];
static boolean oj = System.getProperty("ONLINE_JUDGE") != null;
/****************************************Solutions Begins***************************************/
public static void main (String[] args) throws Exception {
String st[]=nl();
int n=pi(st[0]);
int m=pi(st[1]);
Pair input[]=new Pair[n];
for(int i=0;i<n;i++){
st=nl();
int a=pi(st[0]);
int b=pi(st[1]);
input[i]=new Pair(a,b);
}
Arrays.sort(input,new PairComp());
// debug(input);
TreeSet<Integer> set=new TreeSet<>();
for(int i=0;i<m;i++){
set.add(i);
}

long ans=0;
for(int i=0;i<n;i++){
if(set.size()==0){
break;
}
Integer ss=set.floor(m-input[i].u);
if(ss!=null){
set.remove(ss);
ans+=input[i].v;
}
}
out.println(ans);
/****************************************Solutions Ends**************************************************/
out.flush();
out.close();
}
/****************************************Template Begins************************************************/
static String[] nl() throws Exception{
return br.readLine().split(" ");
}
static String[] nls() throws Exception{
return br.readLine().split("");
}
static int pi(String str) {
return Integer.parseInt(str);
}
static long pl(String str){
return Long.parseLong(str);
}
static double pd(String str){
return Double.parseDouble(str);
}
/***************************************Precision Printing**********************************************/
static void printPrecision(double d){
DecimalFormat ft = new DecimalFormat("0.00000000000000000");
out.println(ft.format(d));
}
/**************************************Bit Manipulation**************************************************/
static void printMask(int mask){
System.out.println(Integer.toBinaryString(mask));
}
/******************************************Graph*********************************************************/
static void Makegraph(int n){
graph=new HashSet[n];
for(int i=0;i<n;i++){
graph[i]=new HashSet<>();
}
}
static void addEdge(int a,int b,int c){
graph[a].add(new Pair(b,c));
}
/*********************************************PAIR********************************************************/
static class PairComp implements Comparator<Pair>{
public int compare(Pair p1,Pair p2){
if(p1.v!=p2.v){
return p2.v-p1.v;
}
else{
return p1.u-p2.u;
}
}
}
static class Pair implements Comparable<Pair> {
int u;
int v;
int index=-1;
public Pair(int u, int v) {
this.u = u;
this.v = v;
}

public int hashCode() {
int hu = (int) (u ^ (u >>> 32));
int hv = (int) (v ^ (v >>> 32));
return 31 * hu + hv;
}

public boolean equals(Object o) {
Pair other = (Pair) o;
return u == other.u && v == other.v;
}

public int compareTo(Pair other) {
if(index!=other.index)
return Long.compare(index, other.index);
return Long.compare(v, other.v)!=0?Long.compare(v, other.v):Long.compare(u, other.u);
}

public String toString() {
return "[u=" + u + ", v=" + v + "]";
}
}
/******************************************Long Pair*************************************************/
static class PairCompL implements Comparator<Pairl>{
public int compare(Pairl p1,Pairl p2){
long aa=p2.v-p1.v;
if(aa<0){
return -1;
}
else if(aa>0){
return 1;
}
else{
return 0;
}
}
}
static class Pairl implements Comparable<Pairl> {
long u;
long v;
int index=-1;
public Pairl(long u, long v) {
this.u = u;
this.v = v;
}

public int hashCode() {
int hu = (int) (u ^ (u >>> 32));
int hv = (int) (v ^ (v >>> 32));
return 31 * hu + hv;
}

public boolean equals(Object o) {
Pair other = (Pair) o;
return u == other.u && v == other.v;
}

public int compareTo(Pairl other) {
if(index!=other.index)
return Long.compare(index, other.index);
return Long.compare(v, other.v)!=0?Long.compare(v, other.v):Long.compare(u, other.u);
}

public String toString() {
return "[u=" + u + ", v=" + v + "]";
}
}
/*****************************************DEBUG***********************************************************/
public static void debug(Object... o) {
if(!oj)
System.out.println(Arrays.deepToString(o));
}
/************************************MODULAR EXPONENTIATION***********************************************/
static long modulo(long a,long b,long c) {
long x=1;
long y=a;
while(b > 0){
if(b%2 == 1){
x=(x*y)%c;
}
y = (y*y)%c; // squaring the base
b /= 2;
}
return  x%c;
}
/********************************************GCD**********************************************************/
static long gcd(long x, long y)
{
if(x==0)
return y;
if(y==0)
return x;
long r=0, a, b;
a = (x > y) ? x : y; // a is greater number
b = (x < y) ? x : y; // b is smaller number
r = b;
while(a % b != 0)
{
r = a % b;
a = b;
b = r;
}
return r;
}
/******************************************SIEVE**********************************************************/
static void sieveMake(int n){
sieve=new boolean[n];
Arrays.fill(sieve,true);
sieve[0]=false;
sieve[1]=false;
for(int i=2;i*i<n;i++){
if(sieve[i]){
for(int j=i*i;j<n;j+=i){
sieve[j]=false;
}
}
}
primes=new ArrayList<Integer>();
for(int i=0;i<n;i++){
if(sieve[i]){
primes.add(i);
}
}
}
/********************************************End***********************************************************/
}```

#### Submission Info

Submission Time 2019-08-10 21:44:42+0900 D - Summer Vacation satya26 Java8 (OpenJDK 1.8.0) 400 7815 Byte AC 560 ms 50424 KB

#### Compile Error

```Note: ./Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
```

#### 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 75 ms 20948 KB
sample_02 AC 73 ms 20948 KB
sample_03 AC 72 ms 21204 KB
testcase_01 AC 229 ms 32080 KB
testcase_02 AC 170 ms 23008 KB
testcase_03 AC 408 ms 44176 KB
testcase_04 AC 541 ms 46616 KB
testcase_05 AC 560 ms 50372 KB
testcase_06 AC 456 ms 46120 KB
testcase_07 AC 508 ms 46724 KB
testcase_08 AC 274 ms 36744 KB
testcase_09 AC 360 ms 41604 KB
testcase_10 AC 480 ms 47276 KB
testcase_11 AC 466 ms 48324 KB
testcase_12 AC 240 ms 33080 KB
testcase_13 AC 487 ms 47012 KB
testcase_14 AC 484 ms 50424 KB
testcase_15 AC 170 ms 26208 KB
testcase_16 AC 466 ms 47756 KB
testcase_17 AC 206 ms 28352 KB
testcase_18 AC 526 ms 45084 KB