akhauriyash/Code-Regression huggingface dataset:
# abc135_a.py
# https://atcoder.jp/contests/abc135/tasks/abc135_a

# A - Harmony /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 100点

# 問題文
# 相違なる整数 A, Bがあります。
# |A−K|=|B−K|となるような整数 Kを出力してください。
# そのような整数が存在しなければ、代わりに IMPOSSIBLE を出力してください。

# 制約
#     入力は全て整数である。
#     0≤A, B≤109
#     Aと Bは相違なる。

# 入力
# 入力は以下の形式で標準入力から与えられる。
# A B

# 出力
# 条件を満たす整数 Kを出力せよ。
# そのような整数が存在しなければ、代わりに IMPOSSIBLE を出力せよ。

# 入力例 1
# 2 16

# 出力例 1
# 9

# |2−9|=7, |16−9|=7 であるため、9は条件を満たす整数です。

# 入力例 2
# 0 3

# 出力例 2
# IMPOSSIBLE

# 条件を満たす整数は存在しません。

# 入力例 3
# 998244353 99824435

# 出力例 3
# 549034394


global FLAG_LOG
FLAG_LOG = False


def log(value):
    # FLAG_LOG = True
    # FLAG_LOG = False
    if FLAG_LOG:
        print(str(value))


def calculation(lines):
    # S = lines[0]
    # N = int(lines[0])
    A, B = list(map(int, lines[0].split()))
    # values = list(map(int, lines[1].split()))
    # values = list(map(int, lines[2].split()))
    # values = list()
    # for i in range(6):
    #     values.append(int(lines[i]))
    # valueses = list()
    # for i in range(M):
    #     valueses.append(list(map(int, lines[i+1].split())))

    ab = A+B
    if ab % 2 == 0:
        result = int(ab/2)
    else:
        result = 'IMPOSSIBLE'

    return [result]


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['2 16']
        lines_export = [9]
    if pattern == 2:
        lines_input = ['0 3']
        lines_export = ['IMPOSSIBLE']
    if pattern == 3:
        lines_input = ['998244353 99824435']
        lines_export = [549034394]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    global FLAG_LOG
    if len(args) == 1:
        mode = 0
        FLAG_LOG = False
    else:
        mode = int(args[1])
        FLAG_LOG = True
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(1)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()


Measured memory_bytes: 9136
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using int64 = int64_t;

constexpr int64 MOD = 1000000007;

int N, M, Q;
string grid[2000];

int s[2017][2017];
int sx[2017][2017];
int sy[2017][2017];

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N >> M >> Q;
    for (int j = 0; j < N; ++j) {
        cin >> grid[j];
    }

    for (int j = 0; j <= N; ++j) fill(s[j], s[j]+M+1, 0);
    for (int j = 0; j < N; ++j) {
        for (int k = 0; k < M; ++k) {
            if (grid[j][k] == '1' && (j ==0 || grid[j-1][k] == '0') && (k == 0 || grid[j][k-1] == '0')) {
                s[j+1][k+1] = s[j][k+1] + s[j+1][k] - s[j][k] + 1;
            } else if (grid[j][k] == '1' && (j > 0 && grid[j-1][k] == '1') && (k > 0 && grid[j][k-1] == '1')) {
                s[j+1][k+1] = s[j][k+1] + s[j+1][k] - s[j][k] - 1;
            } else {
                s[j+1][k+1] = s[j][k+1] + s[j+1][k] - s[j][k];
            }
        }
    }

    for (int j = 0; j < N; ++j) {
        for (int k = 0; k < M; ++k) {
            if (k > 0) {
                int inc = (grid[j][k-1] == '1' && grid[j][k] == '1') ? 1 : 0;
                sx[j+1][k+1] = inc + (j > 0 ? sx[j][k+1] : 0);
            }
            if (j > 0) {
                int inc = (grid[j-1][k] == '1' && grid[j][k] == '1') ? 1 : 0;
                sy[j+1][k+1] = inc + (k > 0 ? sy[j+1][k] : 0);
            }
        }
    }

    for (int q = 0; q < Q; ++q) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        int ans = s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1];
        int i1 = y1 > 1 ? sx[x2][y1] - (x1 > 1 ? sx[x1-1][y1] : 0) : 0;
        int i2 = x1 > 1 ? sy[x1][y2] - (y1 > 1 ? sy[x1][y1-1] : 0) : 0;
        cout << ans+i1+i2 << endl;
    }
    return 0;
}


Measured memory_bytes: 53632
#include <bits/stdc++.h>
using namespace std;
const int maxn=100005;
const int mod=1000*1000*1000+7;
int n,m,x[maxn],y[maxn],t[maxn];
inline void up(int&x,int y){
  if(x+=y,x>=mod)x-=mod;
}
void add(int x,int y){
  for(x++;x<maxn;x+=x&-x)up(t[x],y);
}
int ask(int x){
  int y=0;
  for(x++;x>0;x-=x&-x)up(y,t[x]);
  return y;
}
int main(){
  //freopen("aa.in","r",stdin);
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++)scanf("%d",x+i);
  for(int i=1;i<=m;i++)scanf("%d",y+i);
  int p=1;
  vector< pair< int,int > >a;
  vector< int >b;
  for(int i=1;i<=n;i++)if(x[i]>=y[1]&&x[i]<=y[m]){
    for(;y[p]<x[i];p++);
    a.push_back(make_pair(x[i]-y[p-1],x[i]-y[p]));
    b.push_back(y[p]-x[i]);
  }
  sort(a.begin(),a.end());
  a.resize(unique(a.begin(),a.end())-a.begin());
  sort(b.begin(),b.end());
  int ans=1;
  for(int i=0;i<a.size();i++){
    int pos=lower_bound(b.begin(),b.end(),-a[i].second)-b.begin();
    int sum=ask(pos-1)+1;
    up(ans,sum);
    add(pos,sum);
  }
  printf("%d\n",ans);
  return 0;
}

Measured memory_bytes: 3060
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let s = read::<String>();
    if s.len() < 26 {
        let used = s.chars().collect::<HashSet<_>>();
        for ch in b'a'..b'z' + 1 {
            let ch = ch as char;
            if !used.contains(&ch) {
                println!("{}{}", s, ch);
                return;
            }
        }
    }
    let chs = s.chars().collect::<Vec<_>>();
    let mut used = vec![];
    for (i, &ch) in chs.iter().enumerate().rev() {
        let mut mch = (b'z' + 1) as char;
        for &u_char in &used {
            if u_char > ch {
                // debug!(u_char);
                mch = min(mch, u_char);
            }
        }
        if mch != (b'z' + 1) as char {
            let ans = s.chars().take(i).collect::<String>();
            println!("{}{}", ans, mch);
            return;
        }
        used.push(ch);
    }
    println!("-1");
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}


Measured memory_bytes: 2164
require 'set'

class Hash
  def push(key, value)
    self[key] = [] if self[key] == nil
    self[key].push(value)
  end
end

class Array
  def lower_bound(value)
    left = -1;
    right = self.length;
    while left + 1 < right
      mid = left + (right - left) / 2;
      if self[mid] >= value
        right = mid
      else
        left = mid
      end
    end
    right
  end

  def unique
    res = [self.first]
    each_cons(2) do |a, b|
      if a != b
        res.push(b)
      end
    end
    res
  end
end

def get_ints
  gets.split.map(&:to_i)
end

def get_ints_minus_one
  get_ints.map { |x| x - 1 }
end

def get_int
  gets.chomp.to_i
end

K = get_int
A, B = get_ints

test = 0
success = false
while test <= B
  test += K
  if test >= A && test <= B
    success = true
    break
  end
end

puts success ? 'OK' : 'NG'



Measured memory_bytes: 14384
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using static System.Console;
using static System.Math;

namespace AtCoder
{
    class AtCoderrr
    {
        static long N,K;
        static long[] A, F;
        static void Main(string[] args)
        {
            long[] nk = ReadLine().Split(' ').Select(long.Parse).ToArray();
            N = nk[0];
            K = nk[1];
            A = ReadLine().Split(' ').Select(long.Parse).ToArray();
            F = ReadLine().Split(' ').Select(long.Parse).ToArray();
            Array.Sort(A);
            Array.Reverse(A);
            Array.Sort(F);
            if (is_possible(0))
            {
                WriteLine(0);
                return;
            }

            long left = 0, right = (long)1e18;
            while (right-left > 1)
            {
                var mid = (left + right) / 2;
                if (!is_possible(mid))
                {
                    left = mid;
                }
                else
                {
                    right = mid;
                }
            }
            WriteLine(right);
        }


        /// <summary>
        /// 二部探索を行う関数
        /// 計算量はO(logn)
        /// </summary>
        /// <param name="a">ソート済みの配列</param>
        /// <param name="target">探索対象</param>
        /// <returns></returns>
        static bool is_possible(long target)
        {
            long ex = 0;
            for (int i = 0; i < N; i++)
            {
                long need = target / F[i];
                if (need < A[i])
                {
                    ex += A[i] - need;
                }
            }
            return ex <= K;
        }
    }
}


Measured memory_bytes: 44736
#include<algorithm>
#include<vector>
#include<list>
#include<iostream>
#include<utility>
#include<string>
#include<set>
#include<queue>
#include<stack>
#include<iterator>
#include<map>
#include<limits>
#include<iomanip>

const int INF=2147483647;

using namespace std;



int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    
    vector<long long> vl;
    for(int i=0; i<3*n; i++){
        long long num;
        cin>>num;
        vl.push_back(num);
    }
    sort(vl.begin(),vl.end());
    long long ans=0;
    for(int i=3*n-2, count=0; i>=0 && count<n; i-=2, count++){
        ans+=vl[i];
    }
    cout<<ans;
    
    
    
    
    return 0;
}

Measured memory_bytes: 6256
#include <bits/stdc++.h>
#define INF (1<<30)
#define MOD 1000000007
#define l_ength size
using ll = long long;
using namespace std;

int main(){
	int l;
	cin >> l;
	int cnt = 0; 
	int k;
	for( k = 0; (1<<k) <= l; k++ ){
		if( (1<<k) & l ){
			++cnt;
		}
	}
	cout << k << " " << 2*(k-1)+cnt-1 << endl;
	for( int i = 0; i < k-1; ++i ){
		cout << i+1 << " " << i+2 << " " << (1<<i) << endl;
		cout << i+1 << " " << i+2 << " " << 0 << endl;
	}
	int herum = l;
	for( int i = 0; i < k-1; ++i ){
		if( (1<<i) & l ){
			herum -= (1<<i);
			cout << i+1 << " " << k << " " << herum << endl; 
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int flag[N],w[N];
int main()
{
	int n,m;
	cin>>n>>m;
	string s;
	int ac=0,wa=0,X;
	for(int i=0;i<m;i++)
	{
		cin>>X;
		cin>>s;
		if(flag[X]==0)//û��AC��
		{
			if(s=="AC")
		{
			flag[X]=1;
			ac++;
			wa+=w[X];
		}
			else w[X]++;
		}
	}
	cout<<ac<<" "<<wa<<endl;
    return 0;
}


Measured memory_bytes: 1024
/*
Date: 2017/02/25 19:33:12 Saturday
*/
#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define rep(i,a,n) for(int i=(a);i<=(n);++i)
#define dep(i,a,n) for(int i=(a);i>=(n);--i)
#define eps 1e-8
#define pi 3.1415926535897
#define sqr(x) ((x)*(x))
#define MAX(a,b) a=max(a,b)
#define MIN(a,b) a=min(a,b)
#define SZ(x) ((int)(x).size())
#define CPY(a,b) memcpy(a,b,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define POSIN(x,y) (1<=(x)&&(x)<=n&&1<=(y)&&(y)<=m)
#define all(x) (x).begin(),(x).end()
#define COUT(S,x) cout<<fixed<<setprecision(x)<<S<<endl
#define buli(x) (__builtin_popcountll(x))
#define bur0(x) (__builtin_ctzll(x))
#define bul2(x) (63-__builtin_clzll(x))
#define pw(x) ((ll(1))<<(x))
#define upmo(a,b) (((a)=((a)+(b))%mo)<0?(a)+=mo:(a))
#define mmo(a,b) (((a)=1ll*(a)*(b)%mo)<0?(a)+=mo:(a))
#define y0 y0z
#define y1 y1z
#define yn ynz
#define j0 j0z
#define j1 j1z
#define jn jnz
#define tm tmz
#ifdef LOCAL
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...) 
#endif
typedef long long ll;
typedef double lf;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<lf,lf> pff;
typedef complex<double> CD;
const int inf=0x3f3f3f3f;
const int mo=1000000007;
inline void gn(long long&x){
	int sg=1;char c;while(((c=getchar())<'0'||c>'9')&&c!='-');c=='-'?(sg=-1,x=0):(x=c-'0');
	while((c=getchar())>='0'&&c<='9')x=x*10+c-'0';x*=sg;
}
inline void gn(int&x){long long t;gn(t);x=t;}
inline void gn(unsigned long long&x){long long t;gn(t);x=t;}
inline void gn(double&x){double t;scanf("%lf",&t);x=t;}
inline void gn(long double&x){double t;scanf("%lf",&t);x=t;}
template<class T1,class T2>inline void gn(T1&r,T2&s){gn(r),gn(s);}
template<class T1,class T2,class T3>inline void gn(T1&r,T2&s,T3&t){gn(r),gn(s),gn(t);}
template<class T1,class T2,class T3,class T4>inline void gn(T1&r,T2&s,T3&t,T4&u){gn(r),gn(s),gn(t),gn(u);}
inline void gs(char *s){scanf("%s",s);}
inline void gc(char &c){while((c=getchar())>126 || c<33);}
inline void pc(char c){putchar(c);}
const int DX[]={1,0,-1,0},DY[]={0,1,0,-1};
ll powmod(ll a,ll b) {ll res=1;a%=mo;for(;b;b>>=1){if(b&1)res=res*a%mo;a=a*a%mo;}return res;}
ll powmod(ll a,ll b,ll mo) {ll res=1;a%=mo;for(;b;b>>=1){if(b&1)res=res*a%mo;a=a*a%mo;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
//*******************************************

const int N=511111,M=111111;
int l,m,n,t,C;
char s[N];
int dp[N][27],a[N][22];
int get(int x,int y){
	dep(i,20,0)if(a[x][i]&&a[x][i]<=y)x=a[x][i];
	return x==y;
}
int main(){
#ifdef LOCAL
	freopen("C.in","r",stdin);//freopen("C.out","w",stdout);
#endif
	scanf("%s",s+1);n=strlen(s+1);
	dep(i,n,1){
		dp[i][s[i]-'a']=i;
		rep(j,s[i]-'a'+1,26)dp[i][j]=dp[dp[i][j-1]+1][j-1];
		a[i][0]=dp[i][26]==0?n+10:dp[i][26];
		rep(j,0,s[i]-'a'-1)dp[i][j]=dp[a[i][0]+1][j];
		//printf("%d %d\n",i,a[i][0]);
	}
	rep(i,1,n)a[i][0]++;
	rep(j,1,20)rep(i,1,n)a[i][j]=a[a[i][j-1]][j-1];
	scanf("%d",&m);rep(_,1,m){
		int x,y;
		scanf("%d%d",&x,&y);
		puts(get(x,y+1)?"Yes":"No");
	}
	return 0;
}

Measured memory_bytes: 99072
#include <iostream>
#include <iomanip>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cstdio>
#include <utility>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <numeric>

using namespace std;

typedef uint64_t u64;
typedef int64_t s64;
typedef uint32_t u32;
typedef int32_t s32;
typedef vector<s32> vs32;
typedef vector<u32> vu32;
typedef vector<s64> vs64;
typedef vector<u64> vu64;

const double PI=3.14159265358979323846;

#define MAX(x, y) ((x) < (y) ? (y) : (x))
#define MIN(x, y) ((x) > (y) ? (y) : (x))

#define rep(i, N) for(int i = 0; i < N; ++i)

#define CEIL(x, y) (((x) + (y) - 1) / (y))
#define MOD 1000000007ULL

#define IN(l, r, x) ((l) <= (x) && (x) < (r))


int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n;
    cin >> n;

    vs32 a(n);
    rep (i, n) cin >> a[i];

    s64 ans = 0;
    s64 M = 0;
    rep (i, n)
    {
        if (M < a[i]) M = a[i];
        ans += M - a[i];
    }

    cout << ans << "\n";
    return 0;
}



Measured memory_bytes: 3972
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

typedef long long ll;

int main(){
  ll N,M; cin >> N >> M;
  vector<pair<ll,ll>> Cards(N + M);
  
  for(ll i = 0; i < N; i++){
    Cards[i].second = 1; cin >> Cards[i].first;}
  for(ll j = 0; j < M; j++){
   cin >>  Cards[j + N].second >> Cards[j + N].first;}
  sort(Cards.begin(),Cards.end());
  reverse(Cards.begin(),Cards.end());
  
  ll cnt = 0; ll i = 0; ll sum = 0;
  while( cnt <= N){
    sum += Cards[i].first * Cards[i].second;cnt += Cards[i].second; i++;}
  if( cnt > N){
  sum -= Cards[i-1].first * ( cnt - N);}
  cout <<sum << endl; return 0;}
    
  

Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;

int main(){
  int N;
  cin >> N;
  int ans=0;
  for(int i=1;i<=N;i++){
    string t = to_string(i);
    if(t.length()%2==0){
      continue;
    }else{
      ans +=1;
    }
  }
      cout << ans << endl;
}

Measured memory_bytes: 3736
#include <bits/stdc++.h>
using namespace std;
int main()
  {int N, M; cin >> N >> M;
  vector<int> H(N), cs(N, 1); for (auto &h : H) cin >> h;
  while (M--) {int A, B; cin >> A >> B; --A; --B; cs[A] &= H[A] > H[B]; cs[B] &= H[B] > H[A];}
  cout << accumulate(cs.begin(), cs.end(), 0) << endl;}

Measured memory_bytes: 4024
import sys
A1,A2,A3 = map(int,input().split())
array_A = [A1,A2,A3]

if not (1 <= A1 <= 100 and 1 <= A2 <= 100 and 1 <= A3 <= 100):
    sys.exit()

print(max(array_A) - min(array_A))

Measured memory_bytes: 9180
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF=1001001001;
vector<pair<int64_t,int64_t>>prime_factorize(int64_t x){
  vector<pair<int64_t,int64_t>>p;
  for(int64_t i=2;i*i<=x;i++){
    int cnt=0;
    if(x%i==0){
    while(x%i==0){cnt++;x/=i;}
    p.push_back(make_pair(i,cnt));
    }
  }
  if(x!=1){p.push_back(make_pair(x,1));}
  return p; 
}
int64_t func(int64_t n,int64_t x){
  if(n==0){return 1;}
  int64_t b=pow((int64_t)2,n+1)-3;
  int64_t p=pow((int64_t)2,n)-1;//ひとつ前のものを利用
  if(x==1){return 0;}
  else if(x<=b+1){return func(n-1,x-1);}
  else if(x==b+2){return 1+p;}
  else if(x<2*b+2){return 1+p+func(n-1,x-2-b);}
  else {return 2*p+1;}
}
int main() {
  int64_t N,X;
  cin>>N>>X;
  cout<<func(N,X)<<endl;
  return 0;
}

Measured memory_bytes: 4024
#include <bits/stdc++.h>
#define ll long long int
using namespace std;


int main(){ 
    ll t,i,j,k,l,n,m;
    cin>>n>>m>>k;
    for (i=min(n,m);i>=1;--i){
        if(n%i==0&&m%i==0){
            k--;
        }
        if(k==0){
            cout<<i;
            break;
        }
    }

    return 0;
}

Measured memory_bytes: 384
# ABC158 B - Count Balls

M,A,B = map(int,input().split())
import math
C = math.floor(M/(A+B))
N = M%(A+B)
E = C*A
A_A = 0
B_B = 0
for i in range(N):
    if N >= A:
        A_A +=A
        N -=A
    else:
        A_A +=N
        break
    if N >= B:
        B_B +=B
        N -=B
    else:
        B_B +=N
        break
print(A_A+E)
    


Measured memory_bytes: 62184
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		int N;
		int[] A = new int[100] ;

		Scanner stdIn = new Scanner(System.in);

		N = stdIn.nextInt();
		for(int i = 0; i < N; i++){
			A[i] = stdIn.nextInt();
		}

		trace(A, N);
		insertionSort(A, N);
	}

	public static void insertionSort(int[] A, int N){
		int i, j , v;
		for(i = 1; i < N; i++){
			v = A[i];
			j = i - 1;
			while (j >= 0 && v < A[j]){
				A[j + 1] = A[j];
				j--;
			}
			A[j + 1] = v;
			trace(A, N);
		}
	}
	public static void trace(int[] A, int N){
		for(int i= 0; i < N; i++){
			if( i > 0)	System.out.print(" ");
		System.out.print(A[i]);
		}
		System.out.println();
	}
}

Measured memory_bytes: 34028
import java.util.Scanner;
public class Main {
	public static boolean isSyntropy(double x1,double y1,double x2,double y2,double x3,double y3,double xp,double yp) {
		if(((y3-y1)*(x3-x2)-(x3-x1)*(y3-y2))*((yp-y1)*(xp-x2)-(xp-x1)*(yp-y2))>=0)
			return true;
		return false;
	}
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		double x1,y1,x2,y2,x3,y3,xp,yp;    //三角形的三个顶点坐标 进行判断的点
		while(in.hasNext()) {
			x1 = in.nextDouble();
			y1 = in.nextDouble();
			x2 = in.nextDouble();
			y2 = in.nextDouble();
			x3 = in.nextDouble();
			y3 = in.nextDouble();
			xp = in.nextDouble();
			yp = in.nextDouble();
			if(isSyntropy(x1,y1,x2,y2,x3,y3,xp,yp)&&isSyntropy(x1,y1,x3,y3,x2,y2,xp,yp)&&isSyntropy(x2,y2,x3,y3,x1,y1,xp,yp))
				System.out.println("YES");
			else
				System.out.println("NO");
		}
		in.close();
	}
}


Measured memory_bytes: 31364
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
constexpr int INF = 1000000000LL;
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename T> std::istream &operator>>(std::istream &is, std::vector<T> &v) { for (T &x : v) is >> x; return is; }
template<typename Head, typename Value> auto vectors(const Head &head, const Value &v) { return std::vector<Value>(head, v); }
template<typename Head, typename... Tail> auto vectors(Head x, Tail... tail) { auto inner = vectors(tail...); return std::vector<decltype(inner)>(x, inner); }
template<typename T = int, typename... Args> T in(Args &&... args) { T x(args...); std::cin >> x; return x; }
using namespace std;
// clang-format on

signed main() {
  while (true) {
    int n = in();
    if (n == 0) break;
    auto h = in<vector<int>>(n);
    int m = in();
    int maxH = *max_element(all(h));
    auto dp = vectors(2, maxH + 1, INF);
    dp[0][0] = dp[1][0] = 0;
    rep(_, m) {
      auto name = in<string>();
      int p = in();
      auto t = in<string>();
      int d = in();
      if (d == 0) continue;
      rep(i, maxH + 1) cmin(dp[t[0] == 'A'][min(i + d, maxH)], dp[t[0] == 'A'][i] + p);
    }
    for (int i = maxH - 1; i >= 0; i--) cmin(dp[0][i], dp[0][i + 1]);
    int ans = INF;
    rep(i, maxH + 1) {
      if (dp[1][i] == INF) continue;
      int s = dp[1][i];
      rep(j, n) s += dp[0][max(0LL, h[j] - i)];
      cmin(ans, s);
    }
    cout << ans << endl;
  }
}



Measured memory_bytes: 5292
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	static Scanner in;
	static PrintWriter out;
	static String INPUT = "";
	
	static boolean get(int a, int b)
	{
		out.println("? " + a + " " + b);
		out.flush();
		return in.next().charAt(0) == 'Y';
	}
	
	static void solve()
	{
		int A = ni(), B = ni();
		if(A <= B){
			out.println("Impossible");
			return;
		}
		int n = A+B;
		int[] stack = new int[n];
		int sp = 0;
		for(int i = 0;i < n;i++){
			stack[sp++] = i;
			if(sp >= 2){
				if(!get(stack[sp-2], stack[sp-1])){
					sp -= 2;
				}
			}
		}
		assert sp-1 >= 0;
		int honest = stack[sp-1];
		StringBuilder sb = new StringBuilder();
		for(int i = 0;i < n;i++){
			if(get(honest, i)){
				sb.append(1);
			}else{
				sb.append(0);
			}
		}
		out.print("! ");
		out.print(sb);
		out.println();
		out.flush();
	}
	
	public static void main(String[] args) throws Exception
	{
		in = INPUT.isEmpty() ? new Scanner(System.in) : new Scanner(INPUT);
		out = new PrintWriter(System.out);
		
		solve();
		out.flush();
	}
	
	static int ni() { return Integer.parseInt(in.next()); }
	static long nl() { return Long.parseLong(in.next()); }
	static double nd() { return Double.parseDouble(in.next()); }
	static void tr(Object... o) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}


Measured memory_bytes: 40600
# -*- coding: utf-8 -*-
import sys
import math
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import itertools
from decimal import *

input = sys.stdin.readline

def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
def inputStr(): return input()[:-1]

inf = float('inf')
mod = 1000000007

#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-

def main():
	N = inputInt()
	A = inputList()
	Q = inputInt()

	kanninngu = {}
	goukei = sum(A)
	for i,val in enumerate(A):
		if val in kanninngu:
			kanninngu[val] += 1
		else:
			kanninngu[val] = 1

	for i in range(Q):
		B,C = inputMap()

		if B in kanninngu:
			pass
		else:
			print(goukei)
			continue
			
		tmp = kanninngu[B]
		tmp_sum = B * tmp

		moto = 0
		if C in kanninngu:
			moto = kanninngu[C]

		kanninngu[B] = 0
		kanninngu[C] = tmp + moto
		c_sum = C * tmp

		goukei = goukei + (c_sum - tmp_sum)
		print(goukei)



#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
#-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
if __name__ == "__main__":
	main()


Measured memory_bytes: 89768
#include <stdio.h>

int main(void)
{
	int a,b,c,x,s=0,i,j,k;
	scanf("%d%d%d%d",&a,&b,&c,&x);
	for(i=0;i<=a;i++)for(j=0;j<=b;j++)for(k=0;k<=c;k++)if(500*i+100*j+50*k==x)s++;
	printf("%d",s);
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;

int main(void){
    string s;
    int n;
    cin >> n;
    int sum = 0;
    s = to_string(n);
    for(int i = 0;i < n;i++){
        string t = to_string(n-i);
        if(t.size() % 2 == 1)sum++;
    }
    cout << sum;
}

Measured memory_bytes: 256
// https://atcoder.jp/contests/abc174/tasks/abc174_a
#include<bits/stdc++.h>
using namespace std;

int main(int argc, char* argv[]) {
	int x;
	cin >> x;
	if (x >= 30) cout << "Yes\n";
	else cout << "No\n";
	
	return 0;
}


Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define db(...) " [" << #__VA_ARGS__ << ": " << __VA_ARGS__ << "] "
using ii=long long;
int main()
{
    int n;
    string s;
    cin >> n >> s;
    char p = '*';
    int r = 0;
    for (char c : s) {
        if (c != p) {
            p = c;
            r++;
        }
    }
    cout << r << "\n";
}


Measured memory_bytes: 512
#include<iostream>
using namespace std;

int main(){
    int a,b,ob;
    while(1){
    cin>>a>>b;
    if(a==0&&b==0) break;
        if(a>b){
            ob=b;
            b=a;
            a=ob;
        }
        cout<<a<<" "<<b<<endl;
    }
}


Measured memory_bytes: 3032
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<stdio.h>
#include<vector>
using namespace std;
#define rep(s,i,n) for(int i=s;i<n;i++)
#define c(n) cout<<n<<endl;
#define ic(n) int n;cin>>n;
#define sc(s) string s;cin>>s;
int a[114514],b[114514];
signed main(){
	ic(n)
	rep(0,i,n)cin>>a[i];
	b[1]=abs(a[1]-a[0]);
	b[2]=min(abs(a[2]-a[0]),b[1]+abs(a[2]-a[0]));
	rep(2,i,n){
		if(i>=3){
			b[i]=min(b[i-2]+abs(a[i]-a[i-2]),b[i-1]+abs(a[i]-a[i-1]));
		}	
	}	
	c(b[n-1])
}	


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;

#define pb push_back
#define mp make_pair
#define st first
#define nd second
typedef pair < int , int > pp;
const int mod = 1e9 + 7;
const int N   = 1e2 + 2;

set < pp > S;
set < pp > :: iterator it; 
int A[11][11],M[N][N],m,n,i,j,k,l,kk,ll,x,mn;

signed main(){
    cin >> m >> n;
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++){
            cin >> x;
            A[i][j] = x;
            for(k=0;k<N;k++)
                for(l=0;l<N;l++)
                    M[k][l] = max(M[k][l] , x - i*k - j*l);
        }
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++){
            mn = mod;
            for(k=0;k<N;k++)
                for(l=0;l<N;l++)
                    if(mn > (x = i*k + j*l + M[k][l])){
                        mn = x;
                        kk = k;
                        ll = l;
                    }
        
            if(mn != A[i][j]){
                puts("Impossible");
                return 0;
            }
            S.insert(mp(kk,ll));
        }
        
    puts("Possible");
    printf("%d %d\n", N+N, N+N-2+(int)S.size());
    for(i=1;i<N;i++) printf("%d %d X\n", i, i+1);
    for(i++;i<N+N;i++) printf("%d %d Y\n", i, i+1);
    
    for(it=S.begin();it!=S.end();it++)
        printf("%d %d %d\n", it->st + 1, N+N - it->nd, M[it->st][it->nd]);
    
    printf("1 %d\n",N+N);
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<set>
#include <vector>
#include<algorithm>
using namespace std;
#define loop(i,n) for(int i = 0; i < (n); i++)
#define loops(i,f,n) for(int i = (f); i < (n); i++)
#define INF 1e9
typedef long long int ll;
ll n,a,b,h[100010];
 
bool c(ll t){
	
	ll count=0;
	loop(i,n)if(h[i]>b*t) count+=(h[i]-b*t)/(a-b)+!!((h[i]-b*t)%(a-b));
	
	return (count<=t?1:0);
}
 
int binary_search(){
	int ok=INF, ng=0;
	
	while(abs(ok-ng)>1){
		int mid=(ok+ng)/2;
		if(c(mid)) ok=mid;
		else ng=mid;
	}
	
	return ok;
}
 
int main(){
	cin >> n >> a >> b;
	loop(i,n) cin >> h[i];
	
	cout << binary_search() << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define FI first
#define SE second
#define PB push_back
#define ll long long
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define ROF(i,a,b) for(int i=b-1;i>=a;i--)
#define YES(i) cout<<(i?"YES":"NO")<<endl
#define Yes(i) cout<<(i?"Yes":"No")<<endl
#define co(i) cout<<(i)<<endl
#define fcout cout<<fixed<<setprecision(10)
#define uni(i) i.erase(unique(i.begin(), i.end()), i.end());
#define all(i) i.begin(),i.end()
#define pint pair<int, int>
#define vint vector<int>
using namespace std;

const int INF=1e9+7;
const int MOD=1e9+7;
//const int MOD=998244353;

int main(){
	int h,w,n; cin>>h>>w>>n;
	vector<pint> v;
	FOR(i,0,n){
		int x,y; cin>>x>>y;
		x--; y--;
		v.PB(pint(x,y));
	}
	int k[200001];
	FOR(i,0,h){
		k[i]=min(w,h-i);
	}
	FOR(i,0,n){
		int x=v[i].first,y=v[i].second;
		if(x-y>=0){
			k[x-y]=min(k[x-y],y);
		}
	}
	int ans=h;
	FOR(i,0,n){
		int x=v[i].first,y=v[i].second;
		x--;
		if(x-y>=0){
			if(y<k[x-y])ans=min(ans,x+1);
		}
	}
	co(ans);
}


Measured memory_bytes: 2672
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
G = [[] for _ in [0]*N]
for _ in [0]*M:
    a, b = map(int, input().split())
    a -= 1; b -= 1
    G[a].append(b)
    G[b].append(a)

for v in G[0]:
    if N-1 in G[v]:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

Measured memory_bytes: 39932
N,A,B = map(int,input().split())

N_sum = 0

for i in range(N+1):
    j = i
    if i >= 10:
        j = 0
        i_list = list(str(i))
        for k in i_list:
            j += int(k)
    if j >= A and j <= B:
        N_sum += i
        
print(N_sum)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;
typedef pair<double, int> P;
int n;
double adj[1010][1010];
bool used[1010];
double dist[1010];
double INF = 1e15;
void init()
{
    rep(i, 1010)
    {
        dist[i] = INF;
    }
    rep(i, 1010)
    {
        rep(j, 1010)
        {
            adj[i][j] = INF;
        }
    }
}

int main()
{
    init();
    vector<double> x;
    vector<double> y;
    vector<double> r;
    double a, b, c;
    cin >> a >> b;
    x.push_back(a);
    y.push_back(b);
    r.push_back(0);
    cin >> a >> b;
    x.push_back(a);
    y.push_back(b);
    r.push_back(0);
    cin >> n;
    rep(i, n)
    {
        cin >> a >> b >> c;
        x.push_back(a);
        y.push_back(b);
        r.push_back(c);
    }
    rep(i, n + 2)
    {
        rep(j, n + 2)
        {
            adj[i][j] = max(0.0, sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])) - r[i] - r[j]);
        }
    }
    dist[0] = 0;
    int now = 0;
    rep(i, n + 2)
    {
        int next = 1009;
        used[now] = true;
        rep(j, n + 2)
        {
            dist[j] = min(dist[j], dist[now] + adj[now][j]);
            if (dist[j] < dist[next] && !used[j])
            {
                next = j;
            }
        }
        now = next;
    }
    printf("%.10f\n", dist[1]);
}

Measured memory_bytes: 8192
#include <bits/stdc++.h>
using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define pii make_pair
int ceil(int a, int b) { if(a%b==0) return a/b; else return a/b+1; }
bool checkbit(int pos, int mask) { return mask&(1<<pos); }
int turnon(int pos, int mask) { return mask|(1<<pos); }

vector<int>num;
int dp[105][4][2];
int k;

int fun(int pos, int cnt, int fl)
{
    if(pos==num.size()) {
        if(cnt==k) return 1;
        else return 0;
    }
    if(dp[pos][cnt][fl]!=-1) {
        //cout<<"SDF";
        return dp[pos][cnt][fl];
    }
    int ans=0, lim;
    if(!fl) lim=num[pos];
    else lim=9;
    for(int i=0; i<=lim; i++) {
        int nf=fl, nc=cnt;
        if(!fl && i<lim) nf=1;
        if(i!=0) nc++;
        if(nc<=k) ans+=fun(pos+1, nc, nf);
    }
    return dp[pos][cnt][fl]=ans;
}

int solve(string a)
{
    memset(dp, -1, sizeof(dp));
    for(int i=0; i<a.size(); i++) {
        num.push_back(a[i]-'0');
    }
    int ans=fun(0, 0, 0);
    return ans;
}

main()
{
    string n;
    cin>>n>>k;
    cout<<solve(n);
}


Measured memory_bytes: 3632
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner n=new Scanner(System.in);
		
		int w = n.nextInt();
		int h = n.nextInt();
		int x = n.nextInt();
		int y = n.nextInt();
		int r = n.nextInt();
		if ((x + r) > w || (y + r) > h || (x - r) < 0 || (y - r) < 0){
			System.out.println("No");
		}else{
		System.out.println("Yes");
		}
		
	}

}

Measured memory_bytes: 17360
# include <bits/stdc++.h>
 
using namespace std;

int main() {
	int n;
	cin >> n;

	set < int > st;

	for ( int i = 0; i < n; i++ ) {
		int x;
		cin >> x;

		st.insert(x);
	} 
	if ( (int)st.size() != n ) {
		cout << "NO";
	} 
	else {
		cout << "YES";
	}
}


Measured memory_bytes: 9600
N,M=map(int,input().split())
Drinks=sorted([list(map(int,input().split())) for i in range(N)])
Need=0
for i in Drinks:
    if M <= i[1]:
        Need+=i[0]*M
        break
    if M > i[1]:
        Need+=i[0]*i[1]
        M-=i[1]
print(Need)

Measured memory_bytes: 28652
using System;
using System.Collections.Generic;
using System.Linq;

namespace Algo
{
    class Program
    {
        static long GCD(long a, long b)
        {
            return b == 0 ? a : GCD(b, a % b);
        }
        
        static long LCM(long a, long b)
        {
            return a / GCD(a, b) * b;
        }
        static void Main()
        {
            var n = long.Parse(Console.ReadLine()!);
            var t = new List<long>();
            for (var i = 0; i < n; i++)
            {
                var ti = long.Parse(Console.ReadLine()!);
                t.Add(ti);
            }
            Console.WriteLine(t.Aggregate(LCM));
        }
    }
}


Measured memory_bytes: 28088
#include<bits/stdc++.h>
using namespace std;

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());


void c_p_c()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
}

int32_t main()
{
 // c_p_c();
  int a,b;
  cin >> a >> b;
  cout<<(a*b)<<endl;
  return 0;
}



Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;

#define INF (1<<30)

int main(){
	int n;	cin>>n;
	int a[n];	for(int i=0;i<n;i++)cin>>a[i];


	int ans=0;
	for(int i=0;i<n;i++){
		int min=a[i];
		int minPos=0;
		for(int j=i+1;j<n;j++){
			if(min>a[j]){
				min=a[j];
				minPos=j;
			}
		}
		if(min!= a[i]){
			ans++;

			swap(a[i],a[minPos]);
			//for(int k=0;k<n;k++)cout<<a[k]<<endl;
		}

	}
	if(ans>1)cout<<"NO"<<endl;
	else cout<<"YES"<<endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 2e5 + 4;
const int inf = 1e9;
vector<int> g[N];
int dis[N], n;

int bfs(int s)
{
    int i, u;
    for (i = 1; i <= n; i++)
        dis[i] = inf;

    dis[s] = 0;
    queue<int> q;
    q.push(s);

    while (!q.empty())
    {
        u = q.front();
        s = u;
        q.pop();
        for (int v : g[u])
        {
            if (dis[v] == inf)
                dis[v] = 1 + dis[u], q.push(v);
        }
    }

    return s;
}

int main()
{
    int i, u, v;
    cin >> n;
    for (i = 0; i < n - 1; i++)
    {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    u = bfs(1);
    v = bfs(u);

    if (dis[v] % 3 == 1)
        cout << "Second";
    else
        cout << "First";

    return 0;
}

Measured memory_bytes: 13556
X,K,D=map(int,input().split())
X=abs(X)
if K<=X//D:
  print(X-K*D)
else:
  Z=X-D*(X//D)
  K-=X//D
  if K%2==0:
    print(abs(Z))
  else:
    print(abs(Z-D))

Measured memory_bytes: 9172
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <fstream>
#define mem(i,a) memset(i,a,sizeof(i))
#define PI acos(-1.0)
#define DMAX 100005
#define MOD 20190823
#define eps 1e-8
#define bl bool
#define INF 1e+9
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
template<class T> inline void read(T &f){
	f=0;
    T x=1;
    char ch=getchar();
    while(ch<48 || ch>57) {
        if(ch=='-') {
            x=-1;
        }
        ch=getchar();
    }
    while(ch<=57 && ch>=48) {
        f=f*10+ch-'0';
        ch=getchar();
    }
    f*=x;
}
int main(){
	string s;
	cin>>s;
	if(s=="Sunny"){
		cout<<"Cloudy"<<endl;
	}
	if(s=="Cloudy"){
		cout<<"Rainy"<<endl; 
	}
	if(s=="Rainy"){
		cout<<"Sunny"<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
using namespace std;
const long long mod=998244353;
const long long inf=mod*mod;
const long long d2=500000004;
const double EPS=1e-6;
const double PI=acos(-1.0);
typedef unsigned long long wolf;
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
int A[110000];
int B[110000];
int C[110000];
long long t[110000];
int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d",A+i);
	for(int i=0;i<a;i++)scanf("%d",B+i);
	for(int i=0;i<a;i++)scanf("%d",C+i);
	std::sort(A,A+a);
	std::sort(B,B+a);
	std::sort(C,C+a);
	long long ret=0;
	for(int i=0;i<a;i++){
		t[i+1]=t[i]+lower_bound(A,A+a,B[i])-A;
	}
	for(int i=0;i<a;i++){
		ret+=t[lower_bound(B,B+a,C[i])-B];
	}
	printf("%lld\n",ret);
}

Measured memory_bytes: 2176
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod2 = 998244353;
const int INF = 1000000005;
const int MAX = 10005;

int n, c[MAX];

void CountingSort(vector<int>& a, vector<int>& b, int k) {
  rep(i, k+1) c[i] = 0;
  rep(i, n) c[a[i]]++;
  
  rep(i, k) c[i+1] += c[i];
  repr(i, n-1) {
    b[c[a[i]]-1] = a[i];
    c[a[i]]--;
  }
}

int main() {
  cin >> n;
  vector<int> a(n), b(n);
  int k = 0;
  rep(i, n) {
    cin >> a[i];
    k = max(k, a[i]);
  }

  CountingSort(a, b, k);

  rep(i, n) {
    if (i) cout << " ";
    cout << b[i];
  }
  cout << endl;

  
  return 0;
}



Measured memory_bytes: 18284
# __name__宣言が無いと300msほど？遅くなってTLEになるらしい。今後気をつけよう。。。

import itertools

def main():
  n, m, r = map(int, input().split())
  list_r = [one_r-1 for one_r in map(int, input().split())]

  dist = [[float("inf")] * n for _ in range(n)]
  for i in range(n):
    dist[i][i] = 0
  for i in range(m):
    a, b, c = map(int, input().split())
    dist[a-1][b-1] = c
    dist[b-1][a-1] = c
  for k in range(n):
    for i in range(n):
      for j in range(n):
        if dist[i][j] > dist[i][k] + dist[k][j]:
          dist[i][j] = dist[i][k] + dist[k][j]

  result = float("inf")
  for one_cand in itertools.permutations(list_r):
    temp = 0
    for i in range(r-1):
      temp += dist[one_cand[i]][one_cand[i+1]]
    if temp < result:
      result = temp
  print(result)
  

if __name__ == "__main__":
  main()

Measured memory_bytes: 4748
import bisect

N, C, K = map(int, input().split())
T = sorted([int(input()) for i in range(N)])

ans = 0
while T:
    stop = bisect.bisect_right(T, T[0]+K)
    if stop > C:
        del T[:C]
        ans += 1
    else:
        del T[:stop]
        ans += 1

print(ans)


Measured memory_bytes: 8284
n = int(input())
plist = list(map(int, input().split(" ")))
ans = 0

for i in range(n-2):
    if plist[i] < plist[i+1] and plist[i+1] <= plist[i+2]:
        ans += 1
    elif plist[i] >= plist[i+1] and plist[i+1] > plist[i+2]:
        ans += 1

print(ans)

Measured memory_bytes: 3064
# -*- coding: utf-8 -*-
import itertools
import sys
import math
from functools import lru_cache

# 1整数
# n = int(input())

# 空白区切り2変数
from queue import Queue
from operator import mul
from functools import reduce
from queue import Queue
from operator import mul
from functools import reduce
from functools import lru_cache

input = sys.stdin.readline

# N個整数
# a, b, c = list(map(int, input().split()))

# 1整数
n = int(input())

ret = 0

for i in range(n):

    j = i + 1
    if 0 < j < 10:
        ret = ret + 1
    if 99 < j < 1000:
        ret = ret + 1
    if 9999 < j < 100000:
        ret = ret + 1

print(ret)


Measured memory_bytes: 4188
//g++ -std=c++17 -Wshadow -Wall -fsanitize=address -fsanitize=undefined -D_GLIBCXX_DEBUG -g PROGRAM -o OUTPUT -DLOCAL -lasan -lubsan
#include <bits/stdc++.h>
#include <ext/pb_ds/detail/standard_policies.hpp>

#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define alli(a, n, k) (a + k), (a + n + k)
#define FP(i, a, b, k) for (__typeof(a) i = a; i < b; i += k)
#define FS(i, a, b, k) for (__typeof(a) i = a; i > b; i -= k)
#define IT(it, a) for (__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define eps 1e-6
#define pi 3.141592653589793
using namespace std;
using namespace __gnu_pbds;

template <class T>
inline T gcd(T x, T y)
{
    if (!y)
        return x;
    return gcd(y, x % y);
}
typedef vector<int> VII;
typedef vector<ll> VLL;
typedef pair<int, int> PII;
typedef vector<pair<int, int>> VPII;
typedef vector<pair<int, PII>> VPPI;
const int MOD = 1e9 + 7;
const int INF = 1e9;


inline ll modulo(ll a, ll m)
{
    return (a % m + m) % m;
}

inline ll modInverse(ll a, ll m)
{
    assert(__gcd(a, m) == 1);
    ll m0 = m;
    ll y = 0, x = 1;

    if (m == 1)
        return 0;

    while (a > 1)
    {
        ll q = a / m;
        ll t = m;

        m = a % m, a = t;
        t = y;

        y = x - q * y;
        x = t;
    }

    if (x < 0)
        x += m0;

    return x;
}

inline ll modPow(ll x, ll y, ll m)
{ //x^y % m
    if (y == 0)
        return 1LL;
    else if (y == 1)
        return x;
    else
    {
        ll ans = modPow(x, y / 2, m) % m;
        if (y & 1)
        {
            return (((ans * ans) % m) * x) % m;
        }
        else
        {
            return (ans * ans) % m;
        }
    }
}

vector<string> split(char d,string s)
{
    stringstream ss(s);
    string t;
    vector<string> words;
    while(getline(ss,t,d))
    {
        words.pb(t);
    }

    return words;
}
int check(string s,string& t)
{
    int ans=0;
    for (int i = 0; i < s.size();++i)
        ans += s[i] != t[i];

    return ans;
}
int main(int argc, char *argv[])
{
#ifdef LOCAL
    auto start = chrono::high_resolution_clock::now();
#endif
    
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string s, t;
    cin >> s >> t;

    int v = t.size();
    int ans = INT_MAX;
    for (int i = 0;i<s.size()-v+1;++i)
    {
        //cout << s.substr(i, v) << endl;
        ans = min(ans, check(s.substr(i, v), t));
    }

    cout << ans;

#ifdef LOCAL
    auto end = chrono::high_resolution_clock::now();
    double time_taken =
        chrono::duration_cast<chrono::nanoseconds>(end - start).count();

    time_taken *= 1e-9;

    cerr << "\nTime taken by program is : " << fixed
         << time_taken << setprecision(9);
    cerr << " sec" << endl;
#endif
    return 0;
}


Measured memory_bytes: 3660
#include<iostream>
#include<cstdio>
#define ll long long

using namespace std;

const ll INF = ((1ll) << 32);
const int maxn = 100 + 10;

ll dis[maxn][maxn];

int n , m;

bool floyd()
{
    for (int k = 0 ; k < n ; k ++){
        for (int i = 0 ; i < n ; i ++){
                if (dis[i][k] == INF)
                    continue;
            for (int j = 0 ; j < n ; j ++){
                if (dis[k][j] == INF)
                    continue;
                dis[i][j] = min(dis[i][j] , dis[i][k] + dis[k][j]);
            }

        }
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 0 ; i < n ; i ++){
        for (int j = 0 ; j < n ; j ++){
            if (i == j)
                dis[i][j] = 0;
            else
                dis[i][j] = INF;
        }
    }
    ll s , t , w;
    for (int i = 1 ; i <= m ; i ++){
        scanf("%lld %lld %lld",&s,&t,&w);
            dis[s][t] = w;
    }
    floyd();
    bool flag = false;
    for (int i = 0 ; i < n ; i ++){
        if (dis[i][i] < 0){
            flag = true;
            break;
        }
    }
    if (flag)
        printf("NEGATIVE CYCLE\n");
    else {
        for (int i = 0 ; i < n ; i ++){
            for (int j = 0 ; j < n ; j ++){
                if (dis[i][j] == INF)
                    printf("INF");
                else
                    printf("%lld",dis[i][j]);
                if (j != n - 1)
                    printf(" ");
            }
            printf("\n");
        }
    }
    return 0;

}



Measured memory_bytes: 3300
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int L[] = new int[N];

		for (int i = 0; i < N; i++) {
				L[i] = sc.nextInt();
		}

		Arrays.sort(L);

		int answer = 0;
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				for (int k = j + 1; k < N; k++) {
					if (L[i] < L[j] + L[k] && L[j] < L[k] + L[i]  && L[k] < L[i] + L[j]) {
						answer++;
					} else {
						break;
					}
				}
			}
		}

		System.out.println(answer);

	}
}

Measured memory_bytes: 26712