akhauriyash/Code-Regression huggingface dataset:
N,M = map(int,input().split())
city_d = {}
ans_l = ["" for _ in range(M)]
for i in range(M):
    P,Y = map(int,input().split())
    city_d.setdefault(P,[])
    city_d[P].append([Y,i])

for p,y_orgnum in city_d.items():
    for j,sorted_y_orgnum in enumerate(sorted(y_orgnum,key=lambda x:x[0])):
        ans_l[sorted_y_orgnum[1]] = str(p).zfill(6) + str(j+1).zfill(6)

for ans in ans_l:
    print(ans)




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

typedef long long ll;

int main(){
  char b;
  cin >> b;
   if(b=='A'){
     cout << "T" << endl;
     return 0;
   }else if(b=='G'){
    cout << "C" << endl;
    return 0;
   }else if(b=='T'){
     cout << "A" << endl;
     return 0;
   }else if(b=='C'){
     cout << "G" << endl;
     return 0;
   }
}


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

using namespace std;

const int MAXN = 2E5 + 10;

char s[MAXN];

int main(){
	int n, K;
	scanf("%d%d", &n, &K);
	scanf("%s", s);
	int l = 0;
	for (; K && l < n; ++l, --K)
		if ((s[l] ^ l) & 1){
			s[l] ^= 3;
			if (!--K)
				break;
		}
	rotate(s, s + l % n, s + n);
	if (l & 1)
		transform(s, s + n, s, [](int x){return x ^ 3;});
	if (n & K & 1)
		s[0] ^= 3;
	puts(s);
	return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define endl '\n'

int mod = 1e9 + 7;

int pw(int a, int k) {
    if (k == 0) return 1;
    if (k % 2) return ((long long) pw(a, k - 1) * a) % mod;
    int t = pw(a, k / 2);
    return ((long long) t * t) % mod;
}

int rv(int a) {
    return pw(a, mod - 2);
}

int ml(int a, int b) {
    return ((long long)a * b) % mod;
}

int ml(int a, int b, int c) {
    return ml(ml(a, b), c);
}

int dv(int a, int b) {
    return ml(a, rv(b));
}

int sm(int a, int b) {
    return (a + b) % mod;
}

int df(int a, int b) {
    return ((long long)a + mod - b) % mod;
}

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

string yy = "Yes\n";
string nn = "No\n";
string imp = "IMPOSSIBLE\n";



int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1; // cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<int> a(n), b(n);
        for (int i =0 ; i < n; i++) {
            cin >> a[i] >> b[i];
        }
        bool fl = false;
        for (int i = 0; i + 2 < n; i++) {
            if (a[i] == b[i] && a[i + 1] == b[i + 1] && a[i + 2] == b[i + 2]) fl = true;
        }
        if (fl) cout << yy;
        else cout << nn;
    }
    return 0;
}


Measured memory_bytes: 3640
import java.util.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    public static void main(String[]$) {
        char[] x = scanner.next().toCharArray();
        int ans = 0, c = 0;
        for (int i = 0; i < x.length; i++) {
            if (x[i] == 'S') {
                c++;
            } else if (c == 0) {
                ans++;
            } else {
                c--;
            }
        }
        System.out.println(ans * 2);
    }
}

Measured memory_bytes: 27584
# B - Great Ocean View
# https://atcoder.jp/contests/abc124/tasks/abc124_b
n = int(input())
h = list(map(int, input().split()))
c = 1
H = h[0]
for i in h[1:]:
    if i >= H:
        c += 1
    if H < i:
        H = i
print(c)


Measured memory_bytes: 9100
#include<map>
#include<bitset>
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<stack>
#define REP(i,x,y) for(ll i=x;i<y;i++)
#define SIZE(a) ll(a.size())
#define vll vector<ll>
#define MEMSET(a, n, m) for(ll i=0;i<=n;i++) a[i] = m
#define BIT(n) (ll(1)<<n)
#define UNIQUE(v) v.erase(unique(v.begin(),v.end()),v.end())
#define UNIQUE_ARRAY(a,n) n = unique(a + 1, a + x + 1) - a - 1
#define SORT(a,n) sort(a+1,a+n+1)
#define SORT_O(a,n,order) sort(a+1,a+n+1,order)
#define PER(i,y,x) for(ll i=y;i>x;i--)
typedef long long ll;
using namespace std;

int main(){
    ll a,b;
    cin>>a>>b;
    if (a%2==1 & b%2==1){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}



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

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//????????????????????°?????\???
		int set = sc.nextInt();
		int[] num = new int[9];
		int[] color = new int[9];
		for (int setCount = 0; setCount < set; setCount++) {
			int RCount = 0;
			int GCount = 0;
			int[] used = new int[9];
			int trueSet = 0;
			//??\???
			for (int count = 0; count < 9; count++ ) {
				num[count] = sc.nextInt();
			}
			for (int count = 0; count < 9; count++) {
				String cl = sc.next();
				if (cl.equals("R") ) {
					color[count] = 0;
					RCount++;
				} else if (cl.equals("G") ) {
					color[count] = 1;
					GCount++;
				} else {
					color[count] = 2;
				}
			}
			//??????1
			if ((RCount == 0 && GCount == 0) || (RCount == 0 && GCount == 3) ||
				(RCount == 0 && GCount == 6) || (RCount == 3 && GCount == 0) ||
				(RCount == 3 && GCount == 3) || (RCount == 3 && GCount == 6) ||
				(RCount == 6 && GCount == 0) || (RCount == 6 && GCount == 3) ||
				(RCount == 9) || (GCount == 9)) {
				//?????????????????????????????????
				for (int i = 0; i < 8; i++) {
					for (int j = i+1; j < 9; j++) {
						if (num[i] > num[j]) {
							int numTaihi = num[i];
							num[i] = num[j];
							num[j] = numTaihi;
							int colorTaihi = color[i];
							color[i] = color[j];
							color[j] = colorTaihi;
						}
					}
				}
				//????????????????????????????????????
				for (int xMaime = 0; xMaime < 7; xMaime++) {
					if (used[xMaime] == 0) {
						for (int yMaime = xMaime + 1; yMaime < 8; yMaime++) {
							if (used[xMaime] == 1) {
								break;
							}
							if(used[yMaime] == 0) {
								for (int zMaime = yMaime + 1; zMaime < 9; zMaime++) {
									if (used[xMaime] == 1) {
										break;
									}
									if (used[zMaime] == 0) {
										if (color[xMaime] == color[yMaime] && color[xMaime] == color[zMaime]) {
											if (num[xMaime] == num[yMaime] && num[xMaime] == num[zMaime]) {
												trueSet++;
												used[xMaime]++;
												used[yMaime]++;
												used[zMaime]++;
											} else if (num[xMaime]+1 == num[yMaime] && num[yMaime]+1 == num[zMaime]) {
												trueSet++;
												used[xMaime]++;
												used[yMaime]++;
												used[zMaime]++;
											}
										}
									}
								}
							}
						}
					}
				}
				//??????
				if (trueSet == 3) {
					System.out.println(1);
				} else {
					System.out.println(0);
				}
			} else {
				System.out.println(0);
			}
		}
	}
}

Measured memory_bytes: 28380
n, k = map(int, input().split())
x = list(map(int, input().split()))

minus = [0]
plus = [0]
if 0 in x:
    k -= 1

for i in x:
    if i < 0:
        minus.append(abs(i))
    elif i > 0:
        plus.append(i)
minus.sort()
#print(minus)
#print(plus)
ans = float("inf")
for left in range(len(minus)):
    if 0 <= k-left < len(plus):
        right = k-left
        res = 2*minus[left] + plus[right]
        res = min(res, minus[left] + 2*plus[right])
        ans = min(ans, res)

print(ans)

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

constexpr int INF = (1<<30)-1;

bool solve() {
    int N;
    int dp[1<<16];
    int icost[16];
    int cost[16][16];
    cin >> N;
    if (N == 0) return (false);
    for (int i = 0; i < N; i++) {
        cin >> icost[i];
        for (int j = 0; j < N; j++) {
            cin >> cost[i][j];
        }
    }
    fill_n(dp, 1<<N, INF);
    dp[0] = 0;
    for (int bit = 0; bit < (1<<N); bit++) {
        if (dp[bit] == INF) continue;
        for (int i = 0; i < N; i++) {
            if ((bit>>i) & 1) continue;
            int minv = icost[i];
            for (int j = 0; j < N; j++) {
                if ((bit>>j) & 1) minv = min(minv, cost[i][j]);
            }
            dp[bit | (1<<i)] = min(dp[bit | (1<<i)], dp[bit] + minv);
        }
    }
    cout << dp[(1<<N)-1] << endl;
    return (true);
}
int main() {
    while (solve());
    return (0);
}


Measured memory_bytes: 3268
#include <stdio.h>
int main(){
 char in[3][100];
 int n,p=0;
 char a,b,c;
 scanf("%d%s%s%s",&n,in[0],in[1],in[2]);
 for(n--;n>=0;n--){
  a=in[0][n];
  b=in[1][n];
  c=in[2][n];
  if(a!=b) p++;
  if((a!=c)&(b!=c)) p++;
 }
 printf("%d\n",p);
 return 0;
}

Measured memory_bytes: 128
module Main (main) where

import qualified Data.ByteString.Char8 as C8
import Data.Bool
import Data.Maybe

main :: IO ()
main = do
  [t,x] <- readInts
  print . showAnswer $ solve (t,x)

type Input  = (Int, Int)
type Output = Double

solve :: Input -> Output
solve (t,x) = fromIntegral t / fromIntegral x

showAnswer :: Output -> Answer
showAnswer = String . show

-- utils
readInts :: IO [Int]
readInts = map (fst . fromJust . C8.readInt) . C8.words <$> C8.getLine

data Answer
  = YesNo Bool
  | YESNO Bool
  | AB Bool
  | Number Int
  | String String
  | Compare Ordering
  | Compare2 Ordering

instance Show Answer where
  show (YesNo b)    = bool "No" "Yes" b
  show (YESNO b)    = bool "NO" "YES" b
  show (AB b)       = bool "B"  "A" b
  show (Number i)   = show i
  show (String s)   = s
  show (Compare o)  = ordering "<" "=" ">" o
  show (Compare2 o) = ordering "Right" "Balanced" "Left" o

ordering :: a -> a -> a -> Ordering -> a
ordering lt eq gt o = case o of
  LT -> lt
  EQ -> eq
  GT -> gt

Measured memory_bytes: 508
// inputに入力データ全体が入る
function Main(input) {
	// 1行目がinput[0], 2行目がinput[1], …に入る
	input = input.split("\n");
	var N = Number(input[0])
	//文字列から10進数に変換するときはparseIntを使います
    var b = input[1].split(" ") 
	
    var a = 0
    
    for(var i=0; i<N; i++){
      
      if(i == 0){
      	a = a + Number(b[i])
      }else if(i == N -1){
      	a = a + Number(b[i - 1])
      }else{    
      a = a + Math.min(Number(b[i]),Number(b[i - 1]))
      }
    }
    
	//出力
	console.log(a);
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 7500
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() { 
  ios::sync_with_stdio(false); cin.tie(0);
  int n;
  cin >> n;
  int mi = 1 << 30;
  long long sum = 0;
  for (int i = 0; i < n; i++) {
    int a, b;
    cin >> a >> b;
    if (a > b) mi = min(mi, b);
    sum += a;
  }
  cout << (mi == 1 << 30 ? 0 : sum - mi) << '\n';
  return 0;
}

Measured memory_bytes: 256
import sys
N  = int(input())
S = input()
black = S.count("#")
white = N - black
if black == 0 or white == 0:
    print(0)
    sys.exit()
# 先頭とそれに続く白は除外できる→　黒の始まりからカウントする
# 最後とそれに続く黒は除外できる→　白の終わりは除外する
first = 0
for i in range(N):
    if S[i] == '#':
        first = i
        break
last = N - 1 
for i in reversed(range(N)):
    if S[i] == '.':
        last = i
        break
if first < last:
    S = S[first:last+1]
N = len(S)
# Sは先頭が黒、最後が白になっている
black = S.count("#")
white = N - black
ans = min(black , white)
# tempは黒→白に変えた数
temp = 0
for i in range(N-1):
    if S[i] == '#':
        # 黒を白に変えると仮定する
        black -= 1
        temp += 1
    else:
        # 白だったので、今後変える必要のある白が減る
        white -= 1
    ans = min(ans, temp + black , temp + white) 
print(ans)

Measured memory_bytes: 3500
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll MOD = 1000000007LL;

int main() {
	int N;
	string W;
	cin >> N;
	cin >> W;
	set<string> S;
	S.insert(W);
	char c = W.back();
	for (int i = 1; i < N; i++) {
		cin >> W;
		if (S.find(W) != S.end() || c != W[0]) {
			cout << "No" << endl;
			return 0;
		}
		c = W.back();
		S.insert(W);
	}
	cout << "Yes" << endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
    ll cnt=0,a,b,i,j,n,m;
    cin>>n>>m;
    while(n--)
    {
        cin>>a>>b;
        a=abs(a);
        b=abs(b);
        ll k=ceil(1.0*(sqrt((a*a)+(b*b))));
       // cout<<k<<endl;
        if(k<=m)
            cnt++;
    }
    cout<<cnt<<endl;
}


Measured memory_bytes: 3636
MOD = 10**9 + 7
N, K = gets.split(" ").map(&:to_i)

res = 0
dp = {}
K.downto(1) do |target|
  cnt = (K/target).pow(N, MOD)
  target.step(K, target) do |km|
    cnt -= dp[km] || 0
  end
  dp[target] = cnt
  res = (res + target*cnt) % MOD
end

puts res % MOD


Measured memory_bytes: 19132
from collections import defaultdict
MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))

cnt = defaultdict(int)
cnt[-1] = 3
ans = 1
for i in range(n):
    ans *= max(cnt[a[i] - 1] - cnt[a[i]], 0)
    ans %= MOD

    cnt[a[i]] += 1

print(ans)


Measured memory_bytes: 18648
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
using namespace std;
 
#define ff                  first
#define ss                  second
#define endl                "\n"
#define loop(i,s,e)         for(int i=s;i<e;i++)
#define int                 long long
#define vi                  vector<int> 
#define S(v)                sort(v.begin(),v.end())
#define RS(v)               sort(v.rbegin(),v.rend())
#define R(v)                reverse(v.begin(),v.end())
#define mxpq(T)             priority_queue <T>
#define mnpq(T)             priority_queue<T,vector<T>,greater<T>>
#define prv(v)              for(auto &x : v)cout << x << " ";
#define piirv(v)            for(auto &x : v)cout << x.ff << " " << x.ss << endl;
#define prvv(v)             for(auto &x : v)for(auto &y : x.ss)cout << y << " ";
#define mp                  make_pair
#define pii                 pair<int,int>
#define mset(a,f)           memset(a , f , sizeof(a))
#define pb                  push_back
#define inf                 INT_MAX
#define INF                 LLONG_MAX
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> oset;

const int N = 2e6 + 6;
int A[N];
int dp[N];
int n , k;


void solve()
{
    cin >> n >> k;

    loop(i,1,n+1)cin >> A[i];

    loop(i,0,n+1)dp[i] = inf;

    dp[0] = 0;
    dp[1] = 0;
    dp[2] = abs(A[2] - A[1]); 

    for(int i = 3; i <= n; i++)
    {
        loop(j,1,k+1)
        {
            if(i-j >= 1)
            {
                dp[i] = min(dp[i] , dp[i-j] + abs(A[i]-A[i-j]));
            }
        }
    }

    cout << dp[n];
}
 
int32_t main()
{
 
cout<<fixed<<setprecision(16);

ios_base:: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
     

     int t = 1;
     // cin >> t;
     while(t--)solve();
  
}

Measured memory_bytes: 5120
/* ex 9_1
   saitomo */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//スタックに格納するデータの最大数
#define SIZE 100

//スタックの定義
typedef struct stack{
    int size;
    int count;
    char data[SIZE];
    char *top;
} stack;

//スタックの初期化
void initialize_stack(stack *stk){
    stk->count = 0;
    stk->size = SIZE;
    stk->top = &(stk->data[SIZE]);
}

//データの追加
void push(stack *stk, char elem){
    if(stk->count >= stk->size){
        fprintf(stderr, "Error: stack overflow. (x=%c)\n", elem);
        exit(1);
    }
    else{
        stk->top--;
        *(stk->top) = elem;
        stk->count++;
    }
}

//データの取り出し
char pop(stack *stk){
    char latest;
    if(stk->count <= 0){
        fprintf(stdout, "Error: stack underflow.\n");
        exit(1);
    }
    else{
        latest = *(stk->top);
        stk->top++;
        stk->count--;
        return latest;
    }
}

int main(void){
    char str[SIZE];
    stack stk;
    //スタックを初期化
    initialize_stack(&stk);
    scanf("%s", str);//文字列を読み込む
    for (int i=0; i<strlen(str); i++){
        if (str[i]=='0' || str[i]=='1'){//問題文の通り
            push(&stk, str[i]);
        }else if (stk.count > 0){//1でも0でもないBが来たら先頭から一つ減らす
            pop(&stk);
        }
    }

    //出力
    for (int i=0; i<stk.count; i++){
        printf("%c", stk.data[SIZE-i-1]);//最後尾から出力していく
    }
    printf("\n");
    return 0;
}

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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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 ll INF = 1e9;
const ll MOD = 1e9+7;
const ll LINF = 1e18;



template<typename T>
struct BIT {
  int n;
  vector<T> d;
  BIT(int n=0):n(n),d(n+1) {}
  void add(int i, T x=1) {
    for (; i <= n; i += i&-i) {
      d[i] += x;
    }
  }
  T sum(int i) {
    T x = 0;
    for (; i; i -= i&-i) {
      x += d[i];
    }
    return x;
  }
  T sum(int l, int r) {
    return sum(r-1) - sum(l-1);
  }
};

ll n;
vll a;


ll isOk(ll mid){
  // 中央値がmidに成り得る => 過半数の区間が、mid以下の要素が過半数を占めている
  
  vll s(n+1); // 数列aにおいてmid以下である要素数の累積和
  rep(i,n){
    s[i+1]=s[i];
    if(a[i]<=mid) s[i+1]++;
    else s[i+1]--;
  }
  
  // midが中央値に成り得る区間の数を以下の方針で数え上げる
  // i<jかつs_j-s_i>=0なるi,jの組数を求める
  // jを固定して、s_j>=s_iなるiの個数の和を求める
  BIT<ll> bit(n*2+10);
  ll cnt=0;
  rep(i,n+1){
    // 累積和s_iは負の値を取る可能性があるのでオフセットを付ける必要がある
    // s_iは最小で-nとなるので、n+1のオフセットを付ける
    cnt+=bit.sum(1,s[i]+n+1);
    bit.add(s[i]+n+1);
  }
  
  // 区間数の過半数。このborder以上の数の区間が条件を満たすならmidは中央値である可能性がある
  return cnt>(n*(n+1)/2)/2;
}

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  cin>>n;
  a.resize(n);
  rep(i,n) cin>>a[i];
  
  ll ok=1e9, ng=0;
  while(abs(ok-ng)>1){
    ll mid=(ok+ng)/2;
    if(isOk(mid)) ok=mid;
    else ng=mid;
  }
  cout<<ok<<endl;
}

Measured memory_bytes: 3456
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int main() {
	long long n, m, k;
	cin >> n >> m >> k;
	vector<long long> mi(m + 1, 1000*1000*1000+1);
	vector<long long> ma(m + 1, 0);
	vector<long long> dp(n + 1, k*n);
	dp[0] = 0;
	for (long long i = 1; i <= n; i++) {
		long long a; cin >> a;
		for (long long j = min(m, i); j > 0; j--) {
			mi[j] = min(mi[j - 1], a);
			ma[j] = max(ma[j - 1], a);
			dp[i] = min(dp[i], dp[i - j] + k+j * (ma[j] - mi[j]));
		}
	}
	cout << dp[n] << endl;
	return 0;
}


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

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

int n,s;

int main(){
    while(cin>>n&&n){
	int sum=0,M=0,m=1000;
	rep(i,n){cin>>s;sum+=s;if(s>M)M=s;if(s<m)m=s;}
	cout<<(sum-M-m)/(n-2)<<endl;
    }
}

Measured memory_bytes: 0
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<climits>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<numeric>
#include<map>
#include<set>
#include<bitset>
#include<regex>
using namespace std;
#define REP(i,m,n) for(int i = m; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a)  (a).rbegin(),(a).rend()
#define dup(x,y) (((x)+(y)-1) / (y)); //整数型のまま切り上げ演算する
#define PI 3.14159265359
typedef long long LL;
template<class T> inline void chmax(T& a, T b) { if (a < b) { a = b; } }
template<class T> inline void chmin(T& a, T b) { if (a > b) { a = b; } }
template<class T> inline T gcd(T x, T y) { if (y == 0) { return x; } else if (x == 0) { return y; }return gcd(y, x % y); }
template<class T> inline T lcm(T x, T y) { return (x * y) / gcd(x, y); }
template<class T> inline vector<T> convert_to_binary_number(T x) { vector<T> binary_num; while (x != 1) { binary_num.push_back(x % 2); x /= 2; } binary_num.push_back(1); return binary_num; }
template<class T> inline void print_vector(vector<T> vec) { for (int i = 0; i < vec.size(); i++) { cout << vec[i] << " "; } cout << endl; }
const LL MOD = 1e9 + 7;
const LL INF = 1LL << 60;

bool is_ascending(vector<LL> vec) {
	bool res = true;
	for (LL i = 1; i < vec.size(); i++) {
		if (vec[i] < vec[i - 1]) {
			res = false;
			break;
		}
	}
	return res;
}

int main(void) {
	string S;
	cin >> S;

	/*
	RRRLLLLLL
	111111111
	012211110 1
	003311100 2
	003411000 3
	004410000 4
	004500000 5
	*/

	//偶数同市or奇数同市→同じ数字
	//偶奇異なる:
	//  長い方が偶数個：奇数で完結→長い方が大きい
	//  長い方が奇数個：偶数で完結→短い方が大きい
	//この考察がずれてた。偶数個はなれてるマスの人が集まってくると考えたら瞬殺だった
	LL size = S.size();
	vector<LL> r(size, 1), l(size, 1);

	for (LL i = 0; i < size - 1; i++) {
		if (S[i] == S[i+1] and S[i] == 'R') {
			r[i + 2] += r[i];
			r[i] = 0;
		}
	}

	for (LL i = size - 1; i >= 1; i--) {
		if (S[i] == S[i - 1] and S[i] == 'L') {
			l[i - 2] += l[i];
			l[i] = 0;
		}
	}
	
	for (LL i = 0; i < size; i++) {
		cout << r[i] + l[i] - 1 << " ";
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 2176
function Main(input) {
  var row_list = input.split('\n');
  var row0_sp = row_list[0].split(' ');
  var items = row_list[1].split(' ');
  var sum = 0;
  for(var i=0; i<items.length; i++) {
    items[i] = Number(items[i]);
    sum += items[i];
  }
  items.sort((a,b)=>b-a);
  var N = row0_sp[0]; var M = row0_sp[1];
  
  var border = sum / (4 * M);

  var canSelect = 'Yes';
  for(var i=0; i<M; i++) {
    if(items[i] < border) {
      canSelect = 'No';
      break;
    }
  }

  console.log(canSelect);
}

Main(require('fs').readFileSync('/dev/stdin', 'utf8'));


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

void solve(void) {
	int n, k, i, j;
	cin >> n >> k;
	vector<int> v(n, 0), dp(n, INT_MAX);
	for(auto&t: v) cin >> t;
	dp[0] = 0;
	dp[1] = abs(v[1]-v[0]);
	for(i = 2; i < n; ++i) {
		j = i-1;
		while(j >= max(0, i-k)) {
			dp[i] = min(dp[i], dp[j]+abs(v[i]-v[j]));
			j--;
		}
	}
	cout << dp[n-1] << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
	return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <set>
#include <algorithm>
#include <math.h>
using namespace std;
using i64 = int64_t;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep2(i, x, n) for(int i=x;i<n;++i)

int main()
{   
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i,n) cin >> a[i];

    auto itr_max = max_element(a.begin(),a.end());
    auto itr_min = min_element(a.begin(),a.end());

    cout << 2*n-1 << endl;
    if(abs(*itr_max)>=abs(*itr_min))
    {
        int max_idx = distance(a.begin(),itr_max) + 1;
        rep(i,n)
            cout << max_idx << " " << i+1 << endl;
        rep(i,n-1)
            cout << i+1 << " " << i+2 << endl;
    }
    else
    {
        int min_idx = distance(a.begin(),itr_min) + 1;        
        rep(i,n)
            cout << min_idx << " " << i+1 << endl;
        rep(i,n-1)
            cout << n-i << " " << n-i-1 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using mti = vector<vector<int>>;
using vl = vector<ll>;
using mtl = vector<vector<ll>>;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (int i = j; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define n_p(v) next_permutation(v.begin(),v.end())
#define print(a) cout<<(a)<<endl;
#define to_ll(b) stoll(b)
#define MOD 1000000007

int main(){
	int L,N; cin>>N>>L;
	vector<string> K(N);
	rep(i,0,N){
		string s; cin>>s;
		K[i]=s;
	}
	sort(all(K));
	rep(i,0,N){
		cout<<K[i];
	}
	cout<<endl;
	return 0;
	
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
  int a, b;
  cin >> a >> b;
  
  if (a == 2) {
    cout << "No\n";
    return 0;
  }
  
  if (b == 2) {
    cout << "No\n";
    return 0;
  }
  
  cout << "Yes\n";
  
  return 0;
}

Measured memory_bytes: 256
from itertools import accumulate

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

a = [0] + list(accumulate(a))
b = [0] + list(accumulate(b))

ans = 0
j = m
for i in range(n + 1):
    if a[i] > k:
        break
    while b[j] > k - a[i]:
        j -= 1
    ans = max(ans, i+j)

print(ans)

Measured memory_bytes: 41152
#include<iostream>
using namespace std;
int main() {
    int health, n, temp;
    cin >> health >> n;
    for(int i = 0;i < n; ++i ) {
        cin >> temp;
        health -= temp;
    }
    if(health <= 0) {
        cout << "Yes";
    }
    else{
        cout<<"No";
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string.h>
#include <algorithm>
#include <vector>
#include <map>
#include <queue>
#include <stack>

using namespace std;
int main(void){
    int N,K;
    cin>>N>>K;
    long h[N];
    for(int i=0;i<N;i++){
        cin>>h[i];
    }
    sort(h,h+N);
    long min=10000000000;
    for(int i=0;i<N-K+1;i++){
      long gap=h[i+K-1]-h[i];
      if(gap<min){min=gap;}
    }
    cout<<min;
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
#include <queue>
#include <string>
#include <tuple>
using namespace std;

int main(void){
  int N,W;
  cin >> N >> W;
  
  vector<vector<int>> dp(W+1);
  vector<int> Vs;
  vector<int> Ws;
  
  for(int i=0;i<=W;i++){
    for(int j=0;j<=N;j++){
      dp[i].push_back(0);
    }
  }
  
  Vs.push_back(0);
  Ws.push_back(0);

  for(int i=0;i<N;i++){
    int v,w;
    cin >> v >> w;
    Vs.push_back(v);
    Ws.push_back(w);
  }
  
  for(int w=1;w<=W;w++){
    for(int n=1;n<=N;n++){
      if(w-Ws[n]>=0){
        dp[w][n] = max(dp[w][n-1],dp[w-Ws[n]][n-1]+Vs[n]);
        dp[w][n] = max(dp[w][n],dp[w-Ws[n]][n]+Vs[n]);
      } else {
        dp[w][n] = dp[w][n-1];
      }
    }
  }
  
  /*
  for(int i=0;i<=W;i++){
    for(int j=0;j<=N;j++){
      cout << dp[i][j] << " ";
    }
    cout << endl;
  }
  */
  
  cout << dp[W][N] << endl;
}



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

int main()
{
  string s;
  cin >> s;
  vector<int> A(26, 0);
  for (int i = 0; i < 4; i++)
  {
    A.at((int)(s.at(i) - 'A'))++;
  }
  int cnt = 0;
  for (int i = 0; i < 26; i++)
  {
    if (A.at(i) == 2)
      cnt++;
  }
  cout << (cnt == 2 ? "Yes" : "No") << endl;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
int n,k,arr[109];
int dp[100009][3];
int bt(int sum,int x){
	int &ret = dp[sum][x];
	if(ret != -1) return ret;
	if(x == 1) ret = 0;
	else ret = 1;
	for(int i=0;i<n&&arr[i]<=sum;i++){
		if(x == 1) ret = max(ret,bt(sum-arr[i],2));
		else ret = min(ret,bt(sum-arr[i],1));
	}
	return ret;
}
int main(){
	memset(dp,-1,sizeof(dp));
	cin>>n>>k;
	for(int i=0;i<n;i++) cin>>arr[i];
	sort(arr,arr+n);
	int ans = bt(k,1);
	if(ans == 0) cout<<"Second"<<endl;
	else cout<<"First"<<endl;
}


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

int N, M, A, B;
char G[1010][1010];

void solve(int A, int B, int t) {
    for(int i = 0; i < N; i++) for(int j = 0; j < M; j++) G[i][j] = '.';

    if(t) {
        G[N - 3][M - 3] = '<';
        G[N - 3][M - 2] = '>';
        G[N - 2][M - 3] = '^';
        G[N - 1][M - 3] = 'v';
        G[N - 3][M - 1] = '^';
        G[N - 2][M - 1] = 'v';
        G[N - 1][M - 2] = '<';
        G[N - 1][M - 1] = '>';
        A -= 2;
        B -= 2;
    }

    if(N % 2) {
        for(int i = 0; i < M - 1; i += 2) {
            if(!A) break;
            if(G[N - 1][i] == '.' && G[N - 1][i + 1] == '.') {
                G[N - 1][i] = '<';
                G[N - 1][i + 1] = '>';
                A--;
            }
        }
    }
    if(M % 2) {
        for(int i = 0; i < N - 1; i += 2) {
            if(!B) break;
            if(G[i][M - 1] == '.' && G[i + 1][M - 1] == '.') {
                G[i][M - 1] = '^';
                G[i + 1][M - 1] = 'v';
                B--;
            }
        }
    }

    for(int i = 0; i < N; i += 2) {
        for(int j = 0; j < M; j += 2) {
            bool ok = true;
            for(int a = 0; a < 2; a++) for(int b = 0; b < 2; b++) if(G[i + a][j + b] != '.') {
                ok = false;
                break;
            }
            if(!ok) continue;

            if(A >= 2) {
                for(int k = 0; k < 2; k++) {
                    G[i + k][j] = '<';
                    G[i + k][j + 1] = '>';
                }
                A -= 2;
            }
            else if(A == 1) {
                G[i][j] = '<';
                G[i][j + 1] = '>';
                A--;
            }
            else if(B >= 2) {
                for(int k = 0; k < 2; k++) {
                    G[i][j + k] = '^';
                    G[i + 1][j + k] = 'v';
                }
                B -= 2;
            }
            else if(B == 1) {
                G[i][j] = '^';
                G[i + 1][j] = 'v';
                B--;
            }
        }
    }

    if(A || B) return;

    printf("YES\n");

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            printf("%c", G[i][j]);
        }
        printf("\n");
    }

    exit(0);
}

int main() {
    cin >> N >> M >> A >> B;

    if(2 * (A + B) > N * M) {
        printf("NO");
        return 0;
    }
    if(A > N * (M / 2)) {
        printf("NO");
        return 0;
    }
    if(B > M * (N / 2)) {
        printf("NO");
        return 0;
    }

    solve(A, B, 0);
    if(N * M % 2) solve(A, B, 1);

    printf("NO");
}


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

int ma[100010];
int a[100010];
vector <int> v;
int n,m;

int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++) scanf("%d",&a[i]);
	for(int i=n-1;i>=0;i--) ma[i]=max(ma[i+1],a[i]);
	for(int i=0;i<n;i++)
		v.push_back(ma[i]-a[i]);
	sort(v.begin(),v.end());
	reverse(v.begin(),v.end());
	int maxm=v[0];
	int ans=0;
	for(int i=0;i<v.size();i++)
		if(v[i]==maxm) ans++;
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 1660
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 1000000000; 

int main(){
  ll n,a,b;
  cin >> n >> a >> b;
  ll sum = a+b;
  if(sum == 0){
    cout << 0 << endl;
    return 0;
  }
  ll cnt = n/sum;
  if(n%sum <= a){
    cout << a*cnt + n%sum << endl;
  }
  else{
    cout << a*(cnt+1) << endl;
  }
}


Measured memory_bytes: 256
# E - Simple String Queries
from operator import or_


class SegmentTree:
    __slots__ = ["_default_value", "_seg_func", "_modifying_func", "_size", "_tree"]

    def __init__(self, initial_values: "Sequence", default_value: "Union[int, str]", seg_func: "Callable",
                 modifying_func: "Optional[Callable]" = None) -> None:
        self._default_value = default_value
        self._seg_func = seg_func
        self._modifying_func = modifying_func
        self._size = 1 << (len(initial_values) - 1).bit_length()
        self._tree = self._build(initial_values)

    def _build(self, initial_values: "Sequence") -> "List":
        """Build a segment tree with initial values."""
        tree = [self._default_value] * (2 * self._size)

        if self._modifying_func:
            initial_values = map(self._modifying_func, initial_values)

        for idx, val in enumerate(initial_values):  # set a tree
            tree[idx + self._size - 1] = val

        for idx in range(self._size - 2, -1, -1):  # build
            tree[idx] = self._seg_func(tree[2 * idx + 1], tree[2 * idx + 2])

        return tree

    def update(self, index: int, value: int) -> None:
        """Update index to value."""
        index += self._size - 1
        if self._modifying_func:
            value = self._modifying_func(value)
        self._tree[index] = value
        while index:
            index = (index - 1) // 2
            self._tree[index] = self._seg_func(self._tree[2 * index + 1], self._tree[2 * index + 2])

    def query(self, left: int, right: int) -> "Union[int, str]":
        """Respond to query in [left, right]."""
        left += self._size
        right += self._size
        result = self._default_value
        while left < right:
            if left & 1:
                result = self._seg_func(result, self._tree[left - 1])
                left += 1
            if right & 1:
                right -= 1
                result = self._seg_func(result, self._tree[right - 1])
            left >>= 1
            right >>= 1
        return result


def main():
    _, S, _, *queries = open(0).read().split()
    tree = SegmentTree(tuple(S), 0, or_, lambda c: 1 << (ord(c) - 97))
    ans = []
    popcount = lambda x: bin(x).count("1")
    for com, a, b in zip(*[iter(queries)] * 3):
        if com == "1":
            tree.update(int(a) - 1, b)
        else:
            ans.append(popcount(tree.query(int(a) - 1, int(b))))
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()


Measured memory_bytes: 49972
#include <bits/stdc++.h>
using namespace std;
int main(){
    vector<int> a(3);
    for (int i = 0;i < 3; i++){
        cin >> a[i];
    }
    sort(begin(a), end(a), greater<>());
    cout << (10*a[0])+a[1]+a[2] << endl;
    return 0;
}

Measured memory_bytes: 3604
import statistics
N = int(input())
A = list(map(int,input().split()))
s = 0
X = []

for i in range(N):
  A[i] -= i + 1

b = statistics.median(A)

for i in range(1,N+1):
  s += abs(A[i-1] - int(b))

print(s)



Measured memory_bytes: 27252
#include "bits/stdc++.h"
using namespace std;
 
int main(void) {
	string s;
	cin >> s;

	int a, z;

	for(int i=0;i<s.size();i++) {
		if(s.at(i) == 'A') {
			a = i;
			break;
		}
	}

	for(int i=s.size()-1;i>=0;i--) {
		if(s.at(i) == 'Z') {
			z = i;
			break;
		}
	}

	int ans;

	if(z-a < 0) ans = 0;
	else ans = z-a+1;

	cout << ans << endl;
}


Measured memory_bytes: 640
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;
#define MAX 120
int main(){
    long long int n,m;
    long long int l; //syou
    long long int a; //amari
    long long int ans;
    long long int sei,hu;
    cin >> n >> m;
    l = n / m;
    a = n % m;
    if(a == 0) ans = 0;
    else{
    sei = n - l*m; // sei no saisyouti
    hu = -1* (sei - m);
    ans = min(sei,hu);
    ans = min((long long int)ans,n);
    }
    cout << ans << endl;
    return 0;}


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

int dp[1010][10010];         //dp[n][w];
int N,W,v[110],weight[110];

int main(){
  cin>>N>>W;
  for(int t=0;t<N;t++){
    cin>>v[t]>>weight[t];
  }
  for(int t=0;t<N;t++){
    dp[0][t]=0;
  }

  for(int n=0;n<N;n++){
    for(int w=0;w<=W;w++){
      if(w<weight[n]){
        dp[n+1][w]=dp[n][w];
      }else{
        dp[n+1][w]=max(dp[n][w],dp[n][w-weight[n]]+v[n]);
      }
    }
  }

  cout<<dp[N][W]<<"\n";
  return 0;
}



Measured memory_bytes: 7000
#include<iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int main(){
  	int N;
  	cin >> N;
  	char ch[N];

  	for(int i=0;i<N;i++) cin >> ch[i];


  	int ans = 0;
 	for(int i=1;i<N-1;i++){
 		int cnt = 0;
 		for(char c='a';c<='z';c++){
 			bool left = false, right = false;
 			for(int j=0;j<=i;j++){
 				if(ch[j]==c) left = true;
 			}
 			for(int j=i+1;j<N;j++){
 				if(ch[j]==c) right = true;
 			}
 			if(left && right) cnt++;
 		}
 		ans = max(ans, cnt);
 	}

 	cout << ans <<endl;


  return 0;
}

Measured memory_bytes: 256
def myAnswer(N:int,A:list) -> int:
   ans = 0
   A.sort(reverse= True)
   for i in range(1,N*2,2):
      ans += A[i]
   return ans


def modelAnswer():
   tmp=1
def main():
   N = int(input())
   A = list(map(int,input().split()))
   print(myAnswer(N,A[:]))
if __name__ == '__main__':
   main()

Measured memory_bytes: 39492
#include<bits/stdc++.h>
using namespace std;
int n,k;
vector<int >h(100000,0);
vector<int >memo(100000,-1);
int calc(int n){
	if(n==0)return 0;
  	if(memo[n]!=-1)return memo[n];
  else{
    int mini = abs(h[n]-h[n-1])+calc(n-1);
    for(int i=2;i<=k;i++)
        if(n-i>=0)mini = min(mini,abs(h[n]-h[n-i])+calc(n-i));
    memo[n] = mini;
    return memo[n];
  }
}
int main(){
	cin>>n>>k;
  for(int i=0;i<n;i++){
  	cin>>h[i];
  }
  cout<<calc(n-1);
}

Measured memory_bytes: 11748
#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, B = y; i <= B; i ++)
#define ff(i, x, y) for(int i = x, B = y; i <  B; i ++)
#define fd(i, x, y) for(int i = x, B = y; i >= B; i --)
#define ll long long
#define pp printf
#define hh pp("\n")
using namespace std;

const int mo = 1e9 + 7;

const int N = 55;

int n;
ll f[N][N], c[N][N];

void add(ll &x, ll y) {
	(x += y) %= mo;
}

int main() {
	scanf("%d", &n);
	fo(i, 0, n) {
		c[i][0] = 1;
		fo(j, 1, i) c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mo;
	}
	f[1][0] = f[1][1] = n;
	fo(i, 1, n) {
		fo(j, 0, i) if(f[i][j]) {
			fo(k, max(1, j), n - i) if((k - j) % 2 == 0) {
				int x1 = (k - j) / 2 + j, x2 = (k - j) / 2;
				fo(u, 0, k) add(f[i + k][abs(x1 - u)], f[i][j] * c[n - i][k] % mo * c[k][u]);
			}
		}
	}
	pp("%lld\n", f[n][0]);
}

Measured memory_bytes: 256
from collections import deque

n, m = map(int, (input().split()))

t = [[] for i in range(n + 1)]
for i in range(m):
    a, b = map(int, (input().split()))
    t[a].append(b)
    t[b].append(a)

d = deque([1])
ans = [-1] * 2 + [0 for i in range(n - 1)]

while d:
    parent = d.popleft()
    for child in t[parent]:
        if ans[child] == 0:
            d.append(child)
            ans[child] = parent

print('Yes')
[print(v) for v in ans[2:]]

Measured memory_bytes: 35808
#include <malloc.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

//abc134A
int main(void) {
  int n, k, i, r, cou=0, tmp, len, m;
  long long mod=1000000007;
  scanf("%d", &r);
  printf("%d", 3 * r * r);
  return 0;
}


Measured memory_bytes: 128
#include<stdio.h>

int main(){
    int a, b;

    int d, r;
    double f;

    scanf("%d %d", &a, &b);
    d = a/b;
    r = a%b;
    f = (double)a/(double)b;
    printf("%d %d %.8lf\n", d, r, f);

    return 0;
}


Measured memory_bytes: 2100
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
//mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
//int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int maxx=1e5+10;
ll num[maxx];
ll sum=0,tsum;
int main() {
	int n;
	memset(num,0,sizeof(num));
	scanf("%d",&n);
	rep(i,0,n){
		int a;
		scanf("%d",&a);
		num[a]++;
		sum+=a;
	}
	tsum=sum;
	scanf("%d",&n);
	rep(i,0,n){
		int a,b;
		scanf("%d%d",&a,&b);
		ll t=num[a];
		num[a]=0;
		num[b]+=t;
		sum-=a*t;
		sum+=b*t;
		printf("%lld\n",sum);
	}
} 


Measured memory_bytes: 4548
#include<bits/stdc++.h>
using namespace std;
long int dp[100001];
long int arr[100001];
long int solve(long int i){
	if(i<=0)
	return INT_MAX-10001;
	if(dp[i]!=-1)
	return dp[i];
	dp[i]=min((solve(i-1))+abs(arr[i]-arr[i-1]),(solve(i-2))+abs(arr[i]-arr[i-2]));
	return dp[i];
}
int main(){
	long int n;
	cin>>n;
	//long int arr[n];
	for(long int i=1;i<=n;i++)
	cin>>arr[i];
	arr[0]=0;
	for(long int i=0;i<=n;i++)
	dp[i]=-1;
	dp[1]=0;
	long int ans=solve(n);
	//dp[n]=min(dp[n-1]+abs(arr[n]-arr[n-1]),dp[n-2]+abs(arr[n]-arr[n-2]));
	cout<<dp[n];
}

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

int main()
{
    ll n,d;
    cin>>n>>d;

    int ans= 0;

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

        if( x*x+y*y<=d*d )
            ans++;
    }

    cout<<ans<<endl;
}


Measured memory_bytes: 3588
#include <bits/stdc++.h>
#define debug(...) fprintf(stderr, __VA_ARGS__)

using namespace std;
const int N = 200005;

inline int input() {
	int x; char ch; while (!isdigit(ch = getchar()));
	for (x = ch ^ 48; isdigit(ch = getchar()); x = x * 10 + (ch ^ 48));
	return x;
}

inline void chkmin(int &x, int y) { x = x < y ? x : y; }

int n, m;
int a[N];

int main() {
#ifdef local
	freopen("in", "r", stdin);
	freopen("out", "w", stdout);
//	freopen("log", "w", stderr);
#endif
	ios::sync_with_stdio(false);

	cin >> n;
	for (int i = 0; i <= 30; ++i)
		if ((1 << i) == n) return puts("No"), 0;
	puts("Yes");

	if (n % 4 == 0) {
		for (int i = 1; i < n; ++i) a[i] = i;
		swap(a[(n & -n) - 1], a[n ^ (n & -n)]);
		printf("%d %d\n", n, n & -n);
		printf("%d %d\n", n + n, n ^ (n & -n));
		for (int i = 1; i < n - 1; ++i) {
			printf("%d %d\n", a[i], a[i + 1]);
			printf("%d %d\n", n + a[i], n + a[i + 1]);
		}
		printf("%d %d\n", a[n - 1], n + a[1]);
		return 0;
	}

	if (n % 4 == 1) {
		for (int i = 2; i < n; ++i) {
			printf("%d %d\n", i, i + 1);
			printf("%d %d\n", n + i, n + i + 1);
		}
		printf("%d %d\n", n, n + 2);
		printf("%d %d\n", 1, 2);
		printf("%d %d\n", n + 1, 3);
		return 0;
	}

	if (n % 4 == 2) {
		printf("%d %d\n", 3, 2);
		printf("%d %d\n", 2, 4);
		printf("%d %d\n", n + 3, n + 2);
		printf("%d %d\n", n + 2, n + 4);
		for (int i = 4; i < n - 1; ++i) {
			printf("%d %d\n", i, i + 1);
			printf("%d %d\n", n + i, n + i + 1);
		}
		printf("%d %d\n", n - 1, n + 3);
		printf("%d %d\n", 1, 2);
		printf("%d %d\n", n + 1, 3);
		printf("%d %d\n", n - 1, n);
		printf("%d %d\n", n + 3, n + n);
		return 0;
	}

	if (n % 4 == 3) {
		for (int i = 1; i < n << 1; ++i)
			printf("%d %d\n", i, i + 1);
		return 0;
	}
}

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

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

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

  int cnt = 0;

  for(int i = 0; i < n; i++){
    int minj = i;

    for(int j = i; j < n; j++){
      if(a[j] < a[minj]){
        minj = j;
      }
    }

    if(i != minj){
      int dummy;
      dummy = a[i];
      a[i] = a[minj];
      a[minj] = dummy;
      cnt++;
    }
  }

  for(int i = 0; i < n; i++){
    if(i) cout << " ";
    cout << a[i];
  }

  cout << endl;
  cout << cnt << endl;

  return 0;

}



Measured memory_bytes: 3116
import java.util.Scanner;

public class Main {

	static Scanner scanner;
	public static void main(String[] args) {
	    scanner = new Scanner(System.in);

	    int n=gi();
	    String s=gs();
	int x=0;
	int max=0;
	    for (int i=0; i<n;i++) {
		    char c=s.charAt(i);
		    if(c=='I') {
		    	x++;
		    	if (max<x) {
		    		max=x;
		    	}
		    }else {
		    	x--;
		    }
	    }

	    	System.out.println(max);
	    
        //System.out.println(e);
//        if (xo>w || yo>h) {
//        	System.out.print(0);
//        }else {
//        	System.out.print((h-yo)*(w-xo));
//        }


	}

	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}

	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}

	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}
	
	// doubleとして入力を取得
	public static double gd() {
		return Double.parseDouble(scanner.next());
	}
}

Measured memory_bytes: 35600
#!/usr/bin/env python3
import sys
from itertools import product
sys.setrecursionlimit(10**8)


INF = float("inf")


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


def compress(X, Y):
    dx = list(sorted(set(X)))
    dx_inv = {x: i for i, x in enumerate(dx)}
    dy = list(sorted(set(Y)))
    dy_inv = {y: i for i, y in enumerate(dy)}
    return (dx, dy), (dx_inv, dy_inv)


def main():
    N = int(input())
    X = [0]*N
    Y = [0]*N
    for i in range(N):
        X[i], Y[i] = map(int, input().split())

    (decx, decy), (encx, ency) = compress(X, Y)

    H = len(decx)
    uf = UnionFind(len(decx) + len(decy))

    for i in range(N):
        x, y = encx[X[i]], ency[Y[i]]+H
        # print(x, y)
        uf.union(x, y)

    dx = {}
    for i in range(len(decx)):
        key = uf.find(i)
        if key not in dx:
            dx[key] = 1
        else:
            dx[key] += 1
    dy = {}
    for i in range(H, H+len(decy)):
        key = uf.find(i)
        if key not in dy:
            dy[key] = 1
        else:
            dy[key] += 1
    # print(dx, dy)
    # print(uf.all_group_members())
    ans = 0
    for key in dx:
        if key in dy:
            ans += dy[key]*dx[key]
    print(ans-N)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 109360
#ifdef _DEBUG
#include "MyLib.h"
#else
#define main_D main
#include "bits/stdc++.h" 
#include <regex>
#define _USE_MATH_DEFINES
#include <math.h>
#define FOR(i,s,e) for (int i = int(s); i < int(e); ++i)
#define REP(i,e) FOR(i,0,e)
#define INF (INT_MAX/2)
#define EPS (1.0e-8)
#define LINF (LLONG_MAX/2)
const int MGN = 8;
const int ARY_SZ_MAX = 10000000;
using namespace std;
using ll = long long; using ull = unsigned long long;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vl = vector<ll>; using vvl = vector<vl>;
using vd = vector<double>; using vs = vector<string>;
using pii = pair<int, int>; using pll = pair<ll, ll>;
using psi = pair<string, int>;
// functions
bool second_smaller(const pll& left, const pll& right) {
    return left.second < right.second;
}
#endif


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

    int N, M; cin >> N >> M;
    vi A(M), B(M);
    REP(i, M) cin >> A[i] >> B[i];    

    vector<pii> c;
    REP(i, M) c.push_back(pii(A[i], B[i]));
    sort(c.begin(), c.end(), second_smaller);

    int pos = 0;
    int ans = 0;
    REP(i,M) {
        if (c[i].first <= pos) continue;
        pos = c[i].second - 1;
        ans++;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 2168
#include <stdlib.h>
#include <cmath>
#include <cstdio>
#include <cstdint>
#include <string>
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
using namespace std;
using ll = long long;

int main(){
  int A,B,H,M;
  cin >> A >> B >> H >> M;

  double ang_A,ang_B;
  ang_A=(H*30+(double)30/60*M)*M_PI/180;
  ang_B=(double)360/60*M*M_PI/180;

  double A_x,A_y,B_x,B_y;
  A_x=A*cos(ang_A);
  A_y=A*sin(ang_A);
  B_x=B*cos(ang_B);
  B_y=B*sin(ang_B);

  double C=pow(A_x-B_x,2)+pow(A_y-B_y,2);

  printf("%.20lf\n",sqrt(C));

  return 0;
}


Measured memory_bytes: 4048