akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<stdlib.h>
#define N 2000000
#define Ai 10000
int main(){
  int *A,*B;
  int i,k=0,n,j;
  int C[Ai+1];
  scanf("%d",&n);
  A=malloc(sizeof(int)*n+1);
  B=malloc(sizeof(int)*n+1);
  for (i = 1;i<=n;i++){
    scanf("%d",&A[i]);
    if(A[i]>k) k=A[i];
  }
  for(i=0;i<=k;i++){
    C[i]=0;
  }
  for(j=1;j<=n;j++){
    C[A[j]]++;
  }
  for(i=1;i<=k;i++){
    C[i] += C[i-1];
  }
  for(j = n; j>0;j--){
    B[C[A[j]]] = A[j];
    C[A[j]]--;
  }
  for(i=1;i<=n;i++){
    if (i>1) printf(" ");
    printf("%d",B[i]);
  }
  printf("\n");
  return 0;
}

Measured memory_bytes: 16276
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
using P = pair<string,int>;
const double PI = acos(-1);
int main() {
 int n;
 cin >> n;
 vector<int> s(n);
 rep(i,n) cin >> s.at(i);

 int ans = 0;
 rep(i,n) ans += s.at(i);
 if(ans%10 == 0){
   sort(s.begin(),s.end());
   rep(i,n)if(s.at(i)%10 != 0){
     ans -= s.at(i);
     break;
   }
   if(ans%10 == 0) ans = 0;
 } 
 cout << ans << endl; 
} 

Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,i,e,f,g,n,m,k,l,x;
int main() {
           cin>>a>>b>>n;
           x=min(n,b-1);
           cout<<((a*x)/b)-a*(x/b);
}

Measured memory_bytes: 3592
#include <iostream>
#include <string>

int main()
{
	int x, y;
	std::cin >> x >> y;
	
	if (x == 2 || y == 2)
	{
		std::cout << "No";
		return 0;
	}
	
	if ((x == 4 || x == 6 || x == 9 || x == 1) && (y == 4 || y == 6 || y == 9 || y == 1))
	{
		std::cout << "Yes";
		return 0;
	}
	
	if ((x == 1 || x == 3 || x == 5 || x == 7 || x == 8 || x == 10 || x == 12) && (y == 1 || y == 3 || y == 5 || y == 7 || y == 8 || y == 10 || y == 12))
	{
		std::cout << "Yes";
		return 0;
	}
	
	std::cout << "No";
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <queue>
using namespace std;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define REP(i,n) for(ll i=0;i<n;i++)
#define REPR(i,n) for(ll i=n-1;i>=0;i--)

typedef long long ll;
#define INF 1e18

int main(){
	ll a; cin>>a;
	ll b; cin>>b;
	FOR(i,1,10000){
		if((ll)(i*0.08)==a){
			if((ll)(i*0.10)==b){
				cout<<i<<endl;
				return 0;
			}
		}
	}
	cout<<-1<<endl;
	return 0;
}


Measured memory_bytes: 256
'use strict'

const main = (input) => {
    input = input.split('\n')
    const N = parseInt(input[0].split(' ')[0])
    const K = parseInt(input[0].split(' ')[1])
    const h = input.slice(1, N + 1).map(v => parseInt(v)).sort((a, b) => a - b)
    
    let max = Number.MAX_SAFE_INTEGER
    for(let i = 0; i <= h.length - K; i++){
        let diff = h[i + K - 1] - h[i]
        if(diff < max){
            max = diff
        }
    }
    console.log(max)
}

main(require('fs').readFileSync('/dev/stdin', 'utf-8'))

Measured memory_bytes: 28740
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>

using namespace std;

const int MAXN = 100000 + 10;

int N, M;
int x[MAXN], y[MAXN];
int A[MAXN * 10], B[MAXN * 10], C[MAXN * 10];
int Order[MAXN * 10];
int Fa[MAXN];

bool Cmpx(const int& a, const int& b)
{
	return x[a] < x[b];
}

bool Cmpy(const int& a, const int& b)
{
	return y[a] < y[b];
}

bool Cmpz(const int& a, const int& b)
{
	return C[a] < C[b];
}

int GetRoot(int i)
{
	return (Fa[i] == i) ? i : (Fa[i] = GetRoot(Fa[i]));
}

void Insert(int a, int b)
{
	A[M] = a;
	B[M] = b;
	C[M] = min(abs(x[a] - x[b]), abs(y[a] - y[b]));
	M ++;
}

void Work()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i ++)
	{
		scanf("%d%d", &x[i], &y[i]);
		Fa[i] = i;
	}
	
	int t = 5;

	for (int i = 0; i < N; i ++)
		Order[i] = i;
	sort(Order, Order + N, Cmpx);
	for (int i = 0; i < N; i ++)
		for (int j = 1; j < t && i + j < N; j ++)
			Insert(Order[i], Order[i + j]);
	sort(Order, Order + N, Cmpy);
	for (int i = 0; i < N; i ++)
		for (int j = 1; j < t && i + j < N; j ++)
			Insert(Order[i], Order[i + j]);
	

	for (int i = 0; i < M; i ++)
		Order[i] = i;
	sort(Order, Order + M, Cmpz);
	long long Ans = 0;
	for (int i = 0; i < M; i ++)
	{
		int a = GetRoot(A[Order[i]]);
		int b = GetRoot(B[Order[i]]);
		if (a != b)
		{
			Ans += (long long) C[Order[i]];
			Fa[GetRoot(A[Order[i]])] = GetRoot(B[Order[i]]);
		}
	}
	printf("%lld\n", Ans);
}

int main()
{
	Work();
	return 0;
}

Measured memory_bytes: 16896
import java.io.IOException;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws IOException {
		Scanner cin = new Scanner(System.in);
		String line;
		for (; cin.hasNext();) {
			line = cin.nextLine();

			String[] strArray = line.split("");
			int resultNum1 = -1;
			int resultNum2 = -1;

			for(int i =0; i < strArray.length; i++){

				if(i + 1 <= strArray.length - 1 && strArray[i].equals(strArray[i + 1])){
					resultNum1 = i + 1;
					resultNum2 = i + 2;
					break;
				}


				if(i + 2 <= strArray.length - 1 && strArray[i].equals(strArray[i + 2])){
					resultNum1 = i + 1;
					resultNum2 = i + 3;
					break;
				}
			}


			System.out.println(resultNum1 + " " + resultNum2);
		}
	}
}

Measured memory_bytes: 25272
from math import *

n, m = map(int, input().split())
a = []
for i in range(n):
    a.append([1 if j == '.' else 0 for j in input()])
dp = []
for i in range(n):
    dp.append([n*m] * m)

dp[0][0] = 1 - a[0][0]

for i in range(n):
    for j in range(m):
        #print(i, j)
        if i == j == 0:
            continue
        if a[i][j]:
            if i > 0:
                dp[i][j] = min(dp[i][j], dp[i-1][j])
            if j > 0:
                dp[i][j] = min(dp[i][j], dp[i][j-1])
        else:
            if i > 0 and not a[i-1][j]:
                dp[i][j] = min(dp[i][j], dp[i-1][j])
            elif i > 0:
                dp[i][j] = min(dp[i][j], dp[i-1][j] + 1)
                
            if j > 0 and not a[i][j-1]:
                dp[i][j] = min(dp[i][j], dp[i][j-1])
            elif j > 0:
                dp[i][j] = min(dp[i][j], dp[i][j-1] + 1)

print(dp[n-1][m-1])


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

int main() {
int N,M;
  cin >> N >> M;
  vector<int> ss(M);
  vector<int> cc(M);
  for(int i = 0; i < M; i++){
  	cin >> ss[i] >> cc[i];
  }
  int count = 0;
  if(N == 1){
    for(int i = 0; i < 10; i++){
      count = 0;
      for(int j = 0; j < M; j++){
        if(i != cc[j]){
        	count++;
        }
      }
      if(count == 0){
      	cout << i << endl;
        break;
      }
      if(i == 9){
      	cout << -1 << endl;
      }
    }
  }

  if(N == 2){
  	for(int i = 10; i < 100; i++){
    	count = 0;
      for(int j = 0; j < M; j++){
      	if(ss[j] == 1){
        	if(i/10 != cc[j]){
            	count++;
            }
        }
        if(ss[j] == 2){
          if(i%10 != cc[j]){
          	count++;
          }
        }
        
        
      }
      if(count == 0){
        	cout << i << endl;
          break;
        }
      if(i == 99){
        	cout << -1 << endl;
        }
    }
  }
  
  if(N == 3){
    for(int i = 100; i < 1000; i++){
      count = 0;
    	for(int j = 0; j < M; j++){
        	if(ss[j] == 1){
            	if(i/100 != cc[j]){
                	count++;
                }
            }
            if(ss[j] == 2){
            	if(i%100/10 != cc[j]){
                	count++;
                }
            }
          	if(ss[j] == 3){
            	if(i%10 != cc[j]){
                	count++;
                }
            }
        }
      if(count == 0){
       	cout << i << endl;
        break;
      }
      if(i == 999){
       	cout << -1 << endl;
      }
    }
  }

}

Measured memory_bytes: 3640
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cctype>
#include <cassert>
#include <climits>
#include <string>
#include <bitset>
#include <cfloat>
#include <unordered_set>
#pragma GCC optimize("Ofast")
using namespace std;
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<string> > vvs;
typedef vector<vector<ll> > vvll;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define irep(it, stl) for(auto it = stl.begin(); it != stl.end(); it++)
#define drep(i,n) for(int i = (n) - 1; i >= 0; --i)
#define fin(ans) cout << (ans) << '\n'
#define STI(s) atoi(s.c_str())
#define mp(p,q) make_pair(p, q)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define Sort(a) sort(a.begin(), a.end())
#define Rort(a) sort(a.rbegin(), a.rend())
#define MATHPI acos(-1)
#define itn int;
int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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;}
struct io{io(){ios::sync_with_stdio(false);cin.tie(0);}};
const int INF = INT_MAX;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;
const double EPS = 1e-9;



int main(void) {

    int n,m;
    cin>>n>>m;
    vi v(n,-1);
    rep(i,m){
        int s,c;
        cin>>s>>c;
        s--;
        if(v[s]==-1||v[s]==c){
            v[s]=c;
        } else {
            fin(-1);
            return 0;
        }
    }
    if(v[0]==-1&&n>1){
        v[0]=1;
    }
    rep(i,n){
        if(v[i]==-1)v[i]=0;
    }
    if(n>1&&v[0]==0){
        fin(-1);
        return 0;
    }
    rep(i,n)cout<<v[i];
    cout<<endl;
}

Measured memory_bytes: 256
//#include<bits/stdc++.h>	// 全てのヘッダーファイルをinclude
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<utility>	// 値入れ替えの関数 wrap
#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++)
const int MOD{ int(1e9 + 7) };	// int 1000000007
const int inf{ int(1e9) };	// inf = 1000000000 // 1e9 はdouble型
using namespace std;
typedef long long ll;

// 最大公約数（ユークリッドの互除法）
int GCD(int x, int y) {
	if (x > y) {
		swap(x, y);
	}
	int r = y % x;
	while (r != 0) {
		y = x;
		x = r;
		r = y % x;
	}
	return x;
}

// 最小公倍数
int LCM(int x, int y) {
	ll gcd = GCD(x, y);
	return x * y / gcd;
}

// 素数判定(素数ならtrue,合成数ならfalse)
bool IsPrime(int num) {
	if (num < 2) return false; // 0,1
	else if (num == 2) return true;	// 2
	else if (num % 2 == 0) return false; // 偶数

	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2) {
		if (num % i == 0) return false; // 割り切れたら素数ではない
	}
	return true; // 全部通ったら素数
}

int main(void) {

	int n, p[25];
	cin >> n;
	REP(i, n) cin >> p[i];

	int cnt = 0;
	for (int i = 2; i < n; i++) {
		if (p[i - 2] < p[i - 1] && p[i - 1] < p[i]) 
			cnt++;
		else if (p[i - 2] > p[i - 1] && p[i - 1] > p[i])
			cnt++;
	}

	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 256
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

K, T = getNM()
A = getList()
A.sort(reverse = True)

if len(A) == 1:
    print(A[0] - 1)
else:
    print(max((A[0] - 1) - sum(A[1:]), 0))

Measured memory_bytes: 10932
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <queue>
#include <set>
#include <map>

using namespace std;
typedef long long ll;
int H, N;
int A[1000], B[1000];
int INF = 1000000000;
int dp[20001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(10) << fixed;
    cin >> H >> N;
    for(int i = 0; i < N; i++){
        cin >> A[i] >> B[i];
    }
    dp[0] = 0;
    for(int i = 1; i <= 20000; i++) dp[i] = INF;
    for(int i = 1; i <= 20000; i++){
        for(int j = 0; j < N; j++){
            if(i-A[j] >= 0){
                dp[i] = min(dp[i], dp[i-A[j]]+B[j]);
            }
        }
    }
    int ans = INF;
    for(int i = H; i <= 20000; i++) ans = min(ans, dp[i]);
    cout << ans << endl;
}

Measured memory_bytes: 384
while 1:
    n, m, p = map(int, raw_input().split())
    if not n:
        break
    x = [0] * n
    sum = 0
    for i in range(n):
        x[i] = input()
        sum += x[i]
    if not x[m - 1]:
        print 0
    else:
        print sum * (100 - p) / x[m - 1]

Measured memory_bytes: 4208
#include<iostream>
main(){for(int i,j,x,y,z,a;std::cin>>z,z=z*z*z;printf("%d\n",z-a))for(i=a=1;(x=i*i*i++)<z;)for(j=1;(x+(y=j*j*j++))<z;)a=std::max(a,x+y);}

Measured memory_bytes: 868
#include<stdio.h>

int main()
{
	
char a[13];

scanf("%s",a);  

for(int i=0;i<=3;i++)
{
	printf("%c",a[i]); 
}

printf(" ");

for(int i=4;i<=11;i++)
{
	printf("%c",a[i]);
}

printf("\n");

return 0;
}


Measured memory_bytes: 128
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<ll,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 1e7 + 5;
const int mod = 998244353;
int n;
int r[maxn] , fac[maxn] , rfac[maxn];
int P[maxn];

int nCk(int n , int k){
    return (ll)fac[n] * rfac[n - k] % mod * rfac[k] % mod;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n;
    r[1] = 1;
    for(int i = 2; i <= n ; ++i){
        r[i] = (mod - (ll)(mod / i) * r[mod % i] % mod);
    }
    P[0] = fac[0] = rfac[0] = 1;
    int res = 1;
    for(int i = 1 ; i <= n ; ++i){
        P[i] = P[i - 1] * 2 % mod;
        fac[i] = (ll)fac[i - 1] * i % mod;
        rfac[i] = (ll)rfac[i - 1] * r[i] % mod;
        res = (ll)res * 3 % mod;
    }
    for(int i = n / 2 + 1 ; i <= n ; ++i){
        res -= 2ll * nCk(n , i) * P[n - i] % mod;
        if(res < 0)res += mod;
    }
    cout << res;
}


Measured memory_bytes: 156544
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm> 
using namespace std;
int main(){
	string s;
	cin>>s;
	for(int i=0;i<s.size()-1;i++){
		if(s[i]=='A' && s[i+1]=='C'){
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <bitset>
using namespace std;

int main()
{
    int a[4], b[4];
    int c[4][4];

    for (int i = 1; i <= 3; i++)
    {
        for (int j = 1; j <= 3; j++)
        {
            cin >> c[i][j];
        }
    }

    b[1] = c[1][1];
    b[2] = c[1][2];
    b[3] = c[1][3];

    a[1] = 0;
    a[2] = c[2][1] - b[1];
    a[3] = c[3][1] - b[1];

    for (int i = 1; i <= 3; i++)
    {
        for (int j = 1; j <= 3; j++)
        {
            if (c[i][j] != a[i] + b[j])
            {
                cout << "No";
                return 0;
            }
        }
    }

    cout << "Yes";
    return 0;
}

Measured memory_bytes: 256
# D

N = int(input())
a_list = list(map(int, input().split()))

def search(c):
    bar = N
    r = 0
    res_nega = 0
    dp_arr = [0]*(2*N+1)
    
    for i in range(N):
        dp_arr[bar] += 1
        if a_list[i] < c:
            r += dp_arr[bar]
            bar += 1
        else:
            r -= (dp_arr[bar-1])
            bar -= 1
        
        res_nega += r
    return res_nega

# binary search
a_sorted = sorted(a_list)

left = 0
right = N
mid = N // 2
C = N*(N+1) // 2

while True:
    if search(a_sorted[mid]) <= C // 2:
        if mid == N-1:
            break
        elif search(a_sorted[mid+1]) > C // 2:
            break
        else:
            left = mid
            mid = (mid + right) // 2
    else:
        right = mid + 1
        mid = (mid + left) // 2
        
print(a_sorted[mid])


Measured memory_bytes: 14396
// / #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
 
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <cassert>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <map>
#include <queue>
#include <random>
#include <bitset>
#include <time.h>
#include <stack>
#include <sstream>
#include <regex>
 
#define prev asasddlsa
#define rank aljds
 
using namespace std;
 
typedef long long ll;
typedef long double dbl;

// mt19937 mrand(random_device{} ());
// int rnd(int x = INT_MAX) {
//     return mrand() % x;
// }

template<typename T>
void print(const vector<T>& s){
    for (auto x : s)
        cout << x << ' ';
    cout << endl;
}
 
template<class T>
void print(const T* s, int n){
    for (int i = 0; i < n; i++){
        cout << s[i] + 1 << ' ';
    }
    cout << endl;
}
 
template<class T>
void print(vector<vector<T>> s){
    for (int i = 0; i < s.size(); i++)
        print(s[i]);
}

int main(){
    srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    vector<pair<string, int>> s(n);
    for (int i = 0; i < n; i++)
        cin >> s[i].first >> s[i].second;
    string x;
    cin >> x;
    for (int i = 0; i < n; i++){
        if (s[i].first == x){
            ll res = 0;
            for (int j = i + 1; j < n; j++){
                res += s[j].second;
            }
            cout << res << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const ll INF = 1e18;
const double pi = 3.14159265358979323846;

int main(){
    int n;cin>>n;
    vector<int> s(n),p(n),q(n);
    for(int i=0;i<n;i++) s[i]=i+1;
    for(int i=0;i<n;i++) cin>>p[i];
    for(int i=0;i<n;i++) cin>>q[i];
    int cnt=0,a,b;
    do{
        if(s==p) a=cnt;
        if(s==q) b=cnt;
        cnt++;
    } while(next_permutation(s.begin(),s.end()));
    cout<<abs(a-b)<<endl;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define SORT(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define EQ(a,b) (abs((a)-(b))<EPS)
int X1[1005],X2[1005],Y1[1005],Y2[1005];
int f[3030][3030];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int W,H,N;
int ans=0;
int compress(int* x1,int* x2,int t)
{
	vector<int> xs;
	for(int i=0;i<N;i++)
	{
		for(int d=-1;d<=1;d++)
		{
			int tx1=x1[i]+d,tx2=x2[i]+d;
			if(1<=tx1&&tx1<t)xs.pb(tx1);
			if(1<=tx2&&tx2<t)xs.pb(tx2);
		}
	}
	xs.pb(0);xs.pb(t);
	SORT(xs);
	xs.erase(unique(all(xs)),xs.end());
	for(int i=0;i<N;i++)
	{
		x1[i]=find(all(xs),x1[i])-xs.begin();
		x2[i]=find(all(xs),x2[i])-xs.begin();
	}
	return xs.size()-1;
}
int main()
{
	while(1)
	{
		memset(f,0,sizeof(f));
		ans=0;
		cin >> W >> H;
		if(W==0&&H==0)return 0;
		cin >> N;
		for(int i=0;i<N;i++)
		{
			cin >> X1[i] >> Y1[i] >> X2[i] >> Y2[i];
		}
		W=compress(X1,X2,W);
		H=compress(Y1,Y2,H);
		for(int i=0;i<N;i++)
		{
			f[Y1[i]][X1[i]]++;
			f[Y2[i]][X2[i]]++;
			f[Y1[i]][X2[i]]--;
			f[Y2[i]][X1[i]]--;
		}
		for(int i=0;i<H;i++)
		{
			for(int j=1;j<W;j++)
			{
				f[i][j]+=f[i][j-1];
			}
		}
		for(int i=1;i<H;i++)
		{
			for(int j=0;j<W;j++)
			{
				f[i][j]+=f[i-1][j];
			}
		}
		for(int i=0;i<H;i++)
		{
			for(int j=0;j<W;j++)
			{
				if(f[i][j])continue;
				ans++;
				queue<P> q;
				q.push(mp(j,i));
				while(!q.empty())
				{
					int tx=q.front().fi,ty=q.front().sec;
					q.pop();
					for(int k=0;k<4;k++)
					{
						int ttx=tx+dx[k],tty=ty+dy[k];
						if(ttx<0||ttx>W||tty<0||tty>H||f[tty][ttx]>0)continue;
						q.push(mp(ttx,tty));
						f[tty][ttx]=1;
					}
				}
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 37116
#include<cstdio>
#include<cstring>
#include<cassert>
#include<iostream>
#include<algorithm>

using namespace std;

#define Whats(x) cout<<#x<<" is "<<(x)<<endl
#define Divhim() cout<<">>>>>>>>>>>>>>>"<<endl
#define Divher() cout<<"<<<<<<<<<<<<<<<"<<endl
#define Oops() cout<<"!!!!!!!!!!!!!!!"<<endl

template<typename T> bool GetMin(T &a,T b)
{
	return ((a<=b)?false:(a=b,true));
}

template<typename T> bool GetMax(T &a,T b)
{
	return ((a>=b)?false:(a=b,true));
}

/*
	 -<Unlimited Blade Works>-
 */

#define Bitcnt __builtin_popcount

const int N=21;
const int MS=(1<<21)+10;
const int MOD=1e9+7;

void SU(int &x,int y)
{
	((x+=y)>=MOD)&&(x-=MOD);
}

int n,dp[MS],S,g[N];

int main()
{
	dp[0]=1;
	scanf("%d",&n);
	S=(1<<n)-1;
	for(int i=0;i<n;++i)
	{
		for(int j=0;j<n;++j)
			scanf("%d",g+j);
		for(int k=0;k<=S;++k)if(dp[k]&&Bitcnt(k)==i)
		{
			for(int j=0;j<n;++j)if(g[j])
				SU(dp[k^(1<<j)],dp[k]);
		}
	}
	printf("%d",dp[S]);
	return 0;
}

Measured memory_bytes: 8448
//Java8(OpenJDK 1.8.0)
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Solve s= new Solve();
		s.solve();
	}

}
class Solve{
	 Scanner sc = new Scanner(System.in) ;
	 void solve() {
		 int S =sc.nextInt();
		 int s_1 = S/100;		//先頭2文字
		 int s_2 = S%100;		//後ろ2文字

		 if(s_1>0 && s_1<13) {
			 if(s_2>0 && s_2<13) {
				 System.out.println("AMBIGUOUS");
			 }else {
				 System.out.println("MMYY");
			 }
		 }else {
			 if(s_2>0 && s_2<13) {
				 System.out.println("YYMM");
			 }else {
				 System.out.println("NA");
			 }
		 }
	 }
}

Measured memory_bytes: 21844
#include <iostream>
#include <string>
#include <vector>
#include <iomanip>
#include <algorithm>
using namespace std;

vector<pair<int,int> > v[110001];
int N, M;

int main() {
  cin >> N >> M;
  for (int i = 0; i < M; ++i) {
    int P, Y;
    cin >> P >> Y;
    pair<int,int> p;
    p.first = Y;
    p.second = i;
    v[P].push_back(p);
  }

  pair<int,int> ans[110001];

  for (int i = 1; i <= N; ++i) {
    sort(v[i].begin(), v[i].end());
    for (int j = 0; j < v[i].size(); ++j) {
      ans[v[i][j].second].first = i;
      ans[v[i][j].second].second = j;
    }
  }

  for (int i = 0; i < M; ++i) {
    cout << setw(6) << setfill('0') << ans[i].first;
    cout << setw(6) << setfill('0') << ans[i].second + 1 << endl;
  }
  return 0;
}


Measured memory_bytes: 8064
#include <bits/stdc++.h>
#include <iomanip>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

const int mod = 1'000'000'007;
struct mint {
  ll x;
  mint(ll x=0):x(x%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
  
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

mint dp[100][100001];

int main() {
  int n, k;
  cin >> n >> k;
  int a;
  cin >> a;
  rep(i, k+1) if (i < a+1) dp[0][i] = 1; else dp[0][i] = 0;
  for (int i=1; i<n; i++) {
    cin >> a;
    rep(j, k+1) {
      if (j == 0) dp[i][0] = 1;
      else if (j < a+1) dp[i][j] = dp[i][j-1] + dp[i-1][j];
      else dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-a-1];
    }
  }
  cout << dp[n-1][k].x << endl;
}


Measured memory_bytes: 78464
#include <bits/stdc++.h>
using namespace std;
#define INF 100000000
#define ll long long
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,m,n) for(int i=m;i<n;i++)

int main() {
  int N,M;
  cin >> N >> M;
  vector<int> X(M);
  REP(i,M) cin >> X[i];
  sort(X.begin(),X.end());//小さい順

  int sum = X[M-1] - X[0];
  vector<int> P;
  for(int i = 0; i < M-1; i++){
    P.push_back(X[i+1]-X[i]);
  }

  sort(P.begin(), P.end());
  reverse(P.begin(), P.end());
  
  for(int i = 0; i < N-1; i++){
    if(i >= P.size()) break;
    sum -= P[i];
  }
  cout << sum << endl;
}

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

int main(){
  int animal;
  int leg;
  cin >> animal >> leg;
  
  string ans = "No";
  for(int C=0;C<=animal;C++){
    if(leg == 2*C+4*(animal-C)){
      ans = "Yes";
      break;
    }
  }
  cout << ans << endl;

  return 0;
}

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

int main() {
  int A,a,b,c;
  cin >> A >> a;

  vector<int> vec(100010,0);

	for(int i=0;i<a;i++){
		// cout << 34343 << endl;
		cin >> b >> c;
		vec.at(b-1) += 1;
		vec.at(c) -=1;
	}
	int ans = 0;
	int tmp =0;

	for(int i=0;i<100002;i++){
		tmp += vec.at(i);
		// cout << vec.at(i) << endl;
		if (tmp == a)ans +=1;
	}
	cout << ans << endl;
}


Measured memory_bytes: 3764
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
typedef long long ll;

int main(){
  string div[4]={"erase","eraser","dream","dreamer"};
  bool dp[100005]={false};
  string s;
  cin>>s;
  dp[0]=true;
  rep(i,s.size()){
    if(!dp[i]) continue; //一致しない箇所はとばす
    for(string a:div){ //divの要素をaに代入してループ (a=div[j],j=0~3)
      if(s.substr(i,a.size())==a){ //i文字目からdiv[j].size()文字目でdiv[j]の要素と一致すれば
        dp[i+a.size()]=true; //一致した箇所をtrueにする
      }
    }
  }
  // s.size()文字目でtrueならyesになる
  if (dp[s.size()]==true) cout<<"YES"<<endl;
  else cout<<"NO"<<endl;
}
  

Measured memory_bytes: 640
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
//#include <regex>

/* g++ -g -std=c++0x */
/* g++ -g -std=c++11 */

using namespace std;

// std::ios::sync_with_stdio(false);

// freopen("input.txt", "rt", stdin);
// freopen("output.txt", "wt", stdout);

#define ALL(c)          (c).begin(), (c).end()
#define ALLR(c)         (c).rbegin(), (c).rend()
#define FOR(i,a,b)      for (int i=(a); i < (b); ++i)
#define FORR(i,a,b)     for (int i=(a); i > (b); --i)
#define FOR_ALL(i,c)    for (__typeof((c).begin()) i=(c).begin();   \
                             i != (c).end(); ++i)
#define FOR_ALLR(i,c)   for (__typeof((c).rbegin()) i=(c).rbegin(); \
                             i != (c).rend(); ++i)
#define SZ(array)       (sizeof(array)/sizeof(array[0]))
#define lc(x)           (x<<1)     /* 2*x */
#define rc(x)           (x<<1 | 1) /* 2*x+1 */
#define lowbit(x)       (x & (-x)) /* 0b10100 -> 0b100 */

typedef long long       LL;
typedef map<int,int>    MII;
typedef pair<int,int>   PII;
typedef set<int>        SI;
typedef vector<bool>    VB;
typedef vector<double>  VD;
typedef vector<int>     VI;
typedef vector<string>  VS;

/* check if a key is in container C */
template <class C>
inline bool in_(const typename C::key_type& k, const C& A)
{ return A.find(k) != A.end(); }
inline bool in_(const string& s, const string& S)
{ return S.find(s) != string::npos; }

const int maxn = 1e3+3;
int dp[maxn][maxn];
int N,M,K;

int dfs(const int i, const int j)
{
    if (i == 1 && j == 3)
        int blah = 100;
    const int cnt = i*M + j*N - 2*i*j;
    if (cnt == K)
        return 1;
    int& ans = dp[i][j];
    if (ans == -1) {
        ans = 0;
        if (i+1 <= N)
            ans |= dfs(i+1,j);
        if (j+1 <= M)
            ans |= dfs(i,j+1);
    }
    return ans;
}

int main()
{
/* #ifndef ONLINE_JUDGE */
/*     freopen("foo", "rt", stdin); */
/* #endif */
    while (cin >> N >> M >> K) {
        memset(dp,-1,sizeof(dp));
        const string ans = dfs(0,0) ? "Yes" : "No";
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 4224
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i, x, n) for(int i = x; i < (int)n; ++i)

int fr[100001], x[100000];

int main(){
	int n, d = 0;
	scanf("%d", &n);
	f(i, 0, n){
		scanf("%d", x + i);
		if (++fr[x[i]] > 1)++d;
	}
	int an = d;
	if (d & 1)++an;
	an = n - an;
	printf("%d\n", an);
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define rep2(i,s,n) for (int i = s; i < n; ++i)
#define all(a) a.begin(),a.end()
#define tmax(a,b,c) max(a,max(b,c))
#define tmin(a,b,c) min(a,min(b,c))
#define pb push_back
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmin(T& a,T b) {if(a > b){a = b; return true;} return false;}
template<class T> inline bool chmax(T& a,T b) {if(a < b){a = b; return true;} return false;}
const int inf = 1001001001;
const ll linf = 1001001001001001001;

int main() {
    int n;
    string s;
    cin >> n >> s;
    int now = 0;
    int ans = 0;
    for(char c : s) {
        if(c == 'I') now++;
        else now--;
        chmax(ans,now);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

int main() {

	int X, Y, A, B, C;
	cin>>X>>Y>>A>>B>>C;
	vector<ll> p(A);
	vector<ll> q(B);
	vector<ll> r(C);

	for (auto& x : p) {
		cin>>x;
	}

	for (auto& x : q) {
		cin>>x;
	}

	for (auto& x : r) {
		cin>>x;
	}

	sort(p.begin(), p.end(), greater<ll>());
	sort(q.begin(), q.end(), greater<ll>());
	sort(r.begin(), r.end(), greater<ll>());

	vector<ll> a;

	for (int i = 0;i < X;++i) {
		a.push_back(p[i]);
	}

	for (int i = 0;i < Y;++i) {
		a.push_back(q[i]);
	}

	for (int i = 0;i < r.size();++i) {
		a.push_back(r[i]);
	}
	/*
	a.insert(a.end(), p.begin(), p.begin() + X);
	a.insert(a.end(), q.begin(), q.begin() + Y);
	a.insert(a.end(), r.begin(), r.end());
	*/
	sort(a.begin(), a.end(), greater<ll>());
	ll sum = 0;
	for (int i = 0;i < X + Y;++i) {
		sum += a[i];
	}

	/*cout<<accumulate(a.begin(), a.begin() + X + Y, 0)<<endl;*/
	cout<<sum<<endl;

	return 0;
}


Measured memory_bytes: 8432
#include<cstdio>
#include<iostream>
#include<vector>
#include<tuple>
#include<queue>
#include<algorithm>
#include<string.h>
#include<math.h>

using namespace std;

int main(int argc, char* argv[]){
  int n,k;
  scanf("%d%d",&n,&k);
int ans;
int p = n%k;

if(p==0)ans=0;
else ans=1;


  printf("%d\n",ans);
  return 0;
}

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

int main() {
  int n;
  long a = 100000;
  cin >> n;
  
  for(int i = 0; i < n; i++){
    a *= 1.05;
    if(a % 1000 > 0) a = a + 1000 - a % 1000;
  }
  cout << a << endl;
}


Measured memory_bytes: 2980
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Math.max;

public class Main {

    final int nax = ((int) 1e5) + 5;
    List<Integer>[] edges = new List[nax];
    int[] in_degree = new int[nax]; // the number of edges going to 'b'
    int[] dist = new int[nax];
    boolean[] visited = new boolean[nax];

    void go() {
        Scanner sc = new Scanner(new InputStreamReader(System.in));
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] x = new int[m];
        int[] y = new int[m];
        for (int i = 0; i <= n; i++) {
            edges[i] = new ArrayList<>();
        }
        for (int i = 0; i < m; i++) {
            int a, b;
            a = sc.nextInt();
            b = sc.nextInt();

            if (edges[a] == null) {
                edges[a] = new ArrayList<>();
            }
            edges[a].add(b);
            in_degree[b]++;
        }
        for (int i = 1; i <= n; ++i) {
            if (!visited[i] && in_degree[i] == 0) {
                dfs(i);
            }
        }
        int answer = 0;
        for (int i = 1; i <= n; ++i) {
            answer = max(answer, dist[i]);
        }
        System.out.printf("%d\n", answer);
    }

    void dfs(int a) {
        assert (!visited[a]);
        visited[a] = true;
        for (int b : edges[a]) {
            dist[b] = max(dist[b], dist[a] + 1);
            --in_degree[b];
            if (in_degree[b] == 0) dfs(b);
        }
    }

    public static void main(String[] args) {
        Main main = new Main();
        main.go();
    }
/*
4 5
1 2
1 3
3 2
2 4
3 4
 */

}


Measured memory_bytes: 109204
listS=[1]*100005
listS[0]=0
listS[1]=0
for i in range(2,100003):
    if listS[i]==1:
        for j in range(2*i,100000,i):
            listS[j]=0
list2017=[0]
for k in range(1,100001):
    if listS[k]==1 and listS[int((k+1)/2)]==1:
        list2017.append(list2017[k-1]+1)
    else:
        list2017.append(list2017[k-1])

N=int(input())
for x in range(N):
    l,m=map(int,input().split())
    print(list2017[m]-list2017[l-1])
            

Measured memory_bytes: 5140
#include <bits/stdc++.h>

using namespace std;

const int maxn = 300100;

typedef long long ll;

int a[maxn];

int main() {
	int n; scanf("%d", &n);
	for(int i = 0; i < 3 * n; i++) scanf("%d", &a[i]);
	sort(a, a + 3 * n);
	ll ans = 0;
	for(int i = 0; i < n; i++) ans += a[n + 2 * i];

	printf("%lld\n", ans);

	return 0;
}

Measured memory_bytes: 1408
#include <stdio.h>
#include <memory.h>
#include <math.h>
#include <vector>

using namespace std;

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

//FILE *in = freopen("input.txt", "r", stdin);

int n, m, k;
vector<int> cnt;

void back(int lev, int sum) {
	if (lev == n) {
		cnt[sum]++;
		return;
	}
	rep(i, m) {
		back(lev+1, sum+i+1);
	}
}

void process() {
	long long sum = 0;
	long double q = pow((long double)m, n);
	cnt.clear();
	cnt.assign(m*n+1,0);
	back(0, 0);
	for(int i = m*n; i > 0; i--) {
		int bills = i - k;
		if(bills < 1) bills = 1;
		sum += bills * cnt[i];
	}

	long double res = sum / q;
	printf("%.10Lf\n", res);
}

int main() {
	while(true) {
		scanf("%d%d%d", &n, &m, &k);
		if (!n) break;
		process();
	}
	return 0;
}

Measured memory_bytes: 1148
import java.util.Scanner;

public class Main{
	public static void main(String [] args){
		Scanner sc = new Scanner(System.in);
		int W,H,x,y,r;
		W = sc.nextInt();
		H = sc.nextInt();
		x = sc.nextInt();
		y = sc.nextInt();
		r = sc.nextInt();
		
		if((x - r >= 0 && x + r <= W) && (y - r >= 0 && y + r <= H)){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
	}
}

Measured memory_bytes: 26336
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from functools import reduce, lru_cache
import collections, heapq, itertools, bisect
import math, fractions
import sys, copy

sys.setrecursionlimit(1000000)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline().rstrip())
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]

dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

def divisors(N):
    divs = set([1, N])
    i = 2
    while i ** 2 <= N:
        if N % i == 0:
            divs.add(i)
            divs.add(N//i)
        i += 1
    return sorted(list(divs))

def is_ok(N, K):
    if K <= 1:
        return False
    while N % K == 0:
        N //= K
    return N % K == 1

def main():
    N = I()
    ans = 0

    for divisor in divisors(N-1):
        if is_ok(N, divisor):
            ans += 1

    for divisor in divisors(N):
        if is_ok(N, divisor):
            ans += 1

    print(ans)



if __name__ == '__main__':
    main()

Measured memory_bytes: 77232
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rrep(i,n) for(int (i)=((n)-1);(i)>=0;(i)--)
#define itn int
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
const long long INF = 1LL << 60;
const int MOD = 1000000007;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
#define MAX_V 200000
using P = pair<int,int>;
struct edge{
    int to;
    int cost;
};
vector <edge> G[MAX_V]; //グラフ
vector <int> d(MAX_V, INF);// 距離

void dijkstra(int s){
    priority_queue<P, vector<P>, greater<P> > que;
    d[s] = 0;
    que.push(P(0,s)); // 今までのコストと現在地
    
    while(!que.empty()){
        P p = que.top(); que.pop();
        int v = p.second;
        if(d[v]< p.first) continue;
        
        for(int i=0;i<G[v].size();i++){
            edge e = G[v][i];
            if(d[e.to] > d[v] + e.cost){
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
}


signed main(void){
    int n, m; cin>>n>>m;
    
    vector <int> a(n, INF);
    a[0] = 0;
    
    vector <tuple <int,int,int>> data(m);
    rep(i,m){
        int a,b,c; cin>>a>>b>>c;
        a--; b--;
        data[i] = make_tuple(a, b, c);
        struct edge e = {b,c};
        G[a].push_back(e);
    }
    rrep(i,n){
        if(i == 0) break;
        G[i].push_back({i-1, 0});
    }
    dijkstra(0);
    if(d[n-1] == INF) d[n-1] = -1;
    cout<<d[n-1]<<endl;
}


Measured memory_bytes: 15608
#include <iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<set>
#include<stack>
#include<deque>
#include<queue>
#include<math.h>
using namespace std;
typedef long long ll;
#define int long long
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef priority_queue<int> PQ;
#define fore(i,a) for(auto &i:a)
#define REP(i,n) for(int i=0;i<n;i++)
#define eREP(i,n) for(int i=0;i<=n;i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define eFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define SORT(c) sort((c).begin(),(c).end())
#define rSORT(c) sort((c).rbegin(),(c).rend())
#define LB(x,a) lower_bound((x).begin(),(x).end(),(a))
#define UB(x,a) upper_bound((x).begin(),(x).end(),(a))
#define INF 1000000000
#define LLINF 9223372036854775807
#define mod 1000000007
//vector<vector<int> > dp;
//vector<vector<vector<int> > > vvvi;
//dp=vector<vector<int> >(N, vector<int>(M,0));
//vector<pair<int,int> > v;
//v.push_back(make_pair(x,y));
//priority_queue<int,vector<int>, greater<int> > q2;



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

	int N;
	cin >> N;
	VI A(N);
	REP(i, N)cin >> A[i];

	deque<int> d;
	REP(i, N) {
		//int p = LB(d, A[i] - d.begin());
		int p = lower_bound(d.begin(), d.end(), A[i]) - d.begin();

		if (p == 0) {
			d.push_front(A[i]);
		}
		else {
			d[p - 1] = A[i];
		}
	}
	int ans = d.size();
	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 1920
import java.util.*;
public class Main {
	Scanner sc = new Scanner(System.in);
	StringBuilder output = new StringBuilder();
	
	//並び替える対象の配列の要素数：0...n-1
	int n;
	//対象の配列の中の最大値
	//int k=0;
	//ソート対象の配列A, 登場数を記録する配列B
	int[] A,B;
	int[] C = new int[10001];

	public void input() {
		n = sc.nextInt();
		A = new int[n];
		B = new int[n];
		for(int i=0; i<n; i++) {
			A[i] = sc.nextInt();
			C[ A[i] ]++;
		}
	}
	
	public void solve() {
		for(int i=1; i<10001; i++) C[i] += C[i-1];
		for(int i=n-1; i>=0; i--){
            B[ C[ A[i] ]-1 ] = A[i];
            C[ A[i] ]--;
        }
		for(int i=0; i<n-1; i++) output.append(B[i]+" ");
        System.out.println(output.toString()+B[n-1]);
	}
	
	public static void main(String[] args) {
		Main obj = new Main();
		obj.input();
		obj.solve();
	}
}



Measured memory_bytes: 588216
#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;

const int ranks = 13;

int main() {
  int n;
  cin >> n;
  vector<bool> s(ranks), h(ranks), c(ranks), d(ranks);

  rep(i, n) {
    char a;
    int r;
    cin >> a >> r;
    --r;
    if (a == 'S')
      s[r] = 1;
    if (a == 'H')
      h[r] = true;
    if (a == 'C')
      c[r] = true;
    if (a == 'D')
      d[r] = true;
  }

  rep(i, ranks) if (!s[i]) cout << "S " << i + 1 << endl;
  rep(i, ranks) if (!h[i]) cout << "H " << i + 1 << endl;
  rep(i, ranks) if (!c[i]) cout << "C " << i + 1 << endl;
  rep(i, ranks) if (!d[i]) cout << "D " << i + 1 << endl;
}


Measured memory_bytes: 3092
import collections

n,k = map(int,input().split())
lst = list(map(int,input().split()))
lst_com = collections.Counter(lst).most_common()
if len(lst_com)<=k:
    print(0)
    exit()
ans=n
for i in range(k):
    ans -= lst_com[i][1]
print(ans)

Measured memory_bytes: 39344
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <sstream>
#include <stack>
#include <map>
#include <set>
#include <ios>
#include <cctype>
#include <cstdio>
#include <functional>
#include <cassert>

#define REP(i,a) for(int i = 0;i < (a);++i)
#define FOR(i,a,b) for(int i = (a);i < (b); ++i)
#define FORR(i,a,b) for(int i = (a) - 1;i >=(b);--i)
#define ALL(obj) (obj).begin(),(obj).end()
#define SIZE(obj) (int)(obj).sizeT()
#define YESNO(cond,yes,no){cout <<((cond)?(yes):(no))<<endl; }
#define SORT(list) sort(ALL((list)));
#define RSORT(list) sort((list).rbegin(),(list).rend())
#define ASSERT(cond,mes) assert(cond && mes)

using namespace std;
using ll = long long;

constexpr int mod = 1'000'000'007;
constexpr int INF = 1'050'000'000;

template<typename T>
T round_up(const T& a, const T& b) {
    return (a + (b - 1)) / b;
}

template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
    is >> p.first >> p.second;
    return is;
}

template <typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2>& p) {
    os << p.first << p.second;
    return os;
}

template <typename T>
istream& operator>>(istream& is, vector<T>& v) {
    REP(i, (int)v.size())is >> v[i];
    return is;
}

template <typename T>
ostream& operator<<(ostream& os, vector<T>& v) {
    REP(i, (int)v.size())os << v[i] << endl;
    return os;
}

template <typename T>
T clamp(T& n, T a, T b) {
    if (n < a)n = a;
    if (n > b)n = b;
    return n;
}

template <typename T>
static T GCD(T u, T v) {
    T r;
    while (v != 0) {
        r = u % v;
        u = v;
        v = r;
    }
    return u;
}

template <typename T>
static T LCM(T u, T v) {
    return u * v / gcd(u, v);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::cout << fixed << setprecision(20);

    int N, M;
    cin >> N >> M;

    vector<vector<int>> graph(N, vector<int>(N, -1));
    REP(i, M) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a][b] = 1;
        graph[b][a] = 1;
    }

    auto dfs = [&](int s) {
        vector<bool> reach(N, false);
        reach[s] = true;
        queue<int> q;
        q.push(s);
        //探索する頂点がなくなるまで探索
        while (!q.empty()) {
            int c = q.front();
            q.pop();
            REP(i, N) {
                if (graph[c][i] == -1)continue;
                //すでに到達済み
                if (reach[i])continue;
                //到達済みにする
                reach[i] = true;
                q.push(i);
            }
        }

        //未到達の頂点があれば連結でない
        int cnt = count(ALL(reach), false);
        return cnt == 0;
    };

    int ans = 0;
    REP(i, N) {
        REP(j, N) {
            if (graph[i][j] == -1)continue;
            graph[i][j] = -1;
            graph[j][i] = -1;

            if (!dfs(i))ans++;
            graph[i][j] = 1;
            graph[j][i] = 1;
        }
    }
    cout << ans / 2 << endl;
    return 0;
}

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

int main()
{
    int n,i;
    cin >> n;
    vector<int> a(n);
    for(i = 0;i < n;++i){
        cin >> a.at(i);
    }
    int ans = 0;
    for(i = 0;i < n;++i){
        while(a.at(i) % 2 == 0){
            a.at(i) /= 2;
            ++ans;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using Graph=vector<vector<int>>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
typedef long long ll;

int main(){
    int N;cin>>N;
    ll count=0;
    vector<vector<ll>>C(10,vector<ll>(10));
    for(ll i=1;i<=N;i++){
        string S=to_string(i);
        int a=S.at(0)-'0';
        int b=S.at(S.size()-1)-'0';
        C[a][b]++;
    }
    ll ans=0;
    rep(i,10){
        rep(j,10){
            ans=ans+C[i][j]*C[j][i];
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>

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

using namespace std;

using int64 = int64_t;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<vector<int>> s(m);
  rep(i, m) {
    int k;
    cin >> k;
    while (k--) {
      int a;
      cin >> a;
      --a;
      s[i].emplace_back(a);
    }
  }
  vector<int> p(m);
  rep(i, m) {
    cin >> p[i];
  }
  int ans = 0;
  rep(bit, 1 << n) {
    vector<bool> on(n, false);
    rep(i, n) {
      if (bit & (1 << i)) on[i] = true;
    }
    bool ok = true;
    rep(i, m) {
      int cnt = 0;
      for (auto&& e : s[i]) {
        if (on[e]) ++cnt;
      }
      if (cnt % 2 != p[i] % 2) {
        ok = false;
        break;
      }
    }
    if (ok) ++ans;
  }
  cout << ans;
  return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

ll mod = 1e9 + 7;

ll factorial(int n) {
  int i;
  ll ans = 1;
  for (i = 0; i < n; i++) {
    ans = (ans * (n - i)) % mod;
  }
  return ans;
}

int main() {
  int n, m, N, M;
  ll ans;
  cin >> n >> m;
  N = max(n, m);
  M = min(n, m);
  if (N - M > 1) {
    ans = 0;
  } else if (N == M) {
    ans = (2 * ((factorial(N) % mod * factorial(M) % mod) % mod)) % mod;
  } else {
    ans = (factorial(N) % mod * factorial(M) % mod) % mod;
  }
  cout << ans << "\n";
  return 0;
}

Measured memory_bytes: 256