akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    int n, k;
    cin >> n >> k;
    
    string s;
    cin >> s;
    
    s[k - 1] = tolower(s[k - 1]);
    
    cout << s;
    
    return 0;
}

Measured memory_bytes: 256
N, = map(int, input().split())
X = []
for _ in range(N):
    X.append(list(map(int, input().split())))
Y = []
for i in range(N):
    for j in range(i+1, N):
        Y.append((i, j, X[i][j]))
#Y.sort(key=lambda x:x[2])
r = 0
for i, j, x in Y:
    mn = 10**18
    for k in range(N):
        if k == i or k == j:
            continue
        mn = min(mn, X[i][k] + X[j][k])
    if mn < x:
        r = -1
        break
    if mn > x:
        r += x
print(r)


Measured memory_bytes: 48620
use std::cmp::Ordering;
use std::collections::BinaryHeap;
use std::io;

#[allow(unused_macros)]
macro_rules! input {
    ( $($x:expr ),*) => {
        {
            let temp_str = input_line_str();
            let mut split_result_iter = temp_str.split_whitespace();
                $(
                let buf_split_result = split_result_iter.next();
                let buf_split_result = buf_split_result.unwrap();
                    ($x) = buf_split_result.parse().unwrap();
                )*
        }
    };
}

#[allow(dead_code)]
fn input_line_str() -> String {
    let mut s = String::new();
    io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

#[allow(dead_code)]
fn p<T>(t: T)
where
    T: std::fmt::Display,
{
    println!("{}", t);
}

#[derive(Eq)]
struct St {
    cost: usize,
    edge: usize,
}

impl Ord for St {
    fn cmp(&self, other: &St) -> Ordering {
        other.cost.cmp(&self.cost)
    }
}
impl PartialOrd for St {
    fn partial_cmp(&self, other: &St) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}
impl PartialEq for St {
    fn eq(&self, other: &Self) -> bool {
        self.cost == other.cost
    }
}

fn main() {
    let k: usize;
    input!(k);
    let mut v: Vec<usize> = vec![999_999_999; k];
    let mut hp = BinaryHeap::new();
    v[1] = 1;
    hp.push(St {
        cost: 0,
        edge: 10 % k,
    });
    hp.push(St {
        cost: 1,
        edge: 2 % k,
    });

    while !hp.is_empty() {
        let e = hp.pop().unwrap();
        if v[e.edge] > e.cost {
            v[e.edge] = e.cost;
            hp.push(St {
                cost: e.cost + 1,
                edge: (e.edge + 1) % k,
            });
            hp.push(St {
                cost: e.cost,
                edge: (e.edge * 10) % k,
            });
        }
    }
    p(v[0] + 1);
}

Measured memory_bytes: 8444
def main():
    n=int(input())
    s=input()
    
    ans=s[1:].count('E')
    tmp=ans
    for i in range(n-1):
        if s[i]=='W':
            tmp+=1
        if s[i+1]=='E':
            tmp-=1
        ans=min(ans,tmp)
    tmp=s[:-1].count('W')
    ans=min(ans,tmp)
    print(ans)
if __name__=='__main__':
    main()

Measured memory_bytes: 3708
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long int
#define ii pair<int,int>
#define lli pair<ll,ll>
#define pii pair<int,int>
#include<limits>
#define deb(x) cout<<#x<<'='<<(x)<<endl
#define deb2(x,y) cout<<'['<<#x<<'='<<(x)<<','<<#y<<'='<<(y)<<']'<<endl
#define debarr(a,n) {cout<<#a<<'='; for(int i=0;i<n;i++) cout << a[i] << ' '; cout<<endl;}
#define debvec(v) {cout<<#v<<'=';for(auto itr=v.begin();itr!=v.end();itr++)cout<<*itr<<' ';cout<<endl;}
#define INF numeric_limits<int>::max()
#define NINF numeric_limits<int>::min()
#define endl "\n"
#define MP make_pair
#define SZ(x) ((int)(x).size())
#define MOD (pow(10,9)+7)
using namespace std;



int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll n;
    cin>>n;
    n--;
    vector<ll> v(n);
    for(int i=0;i<n;i++) cin>>v[i];
    sort(v.begin(),v.end());
    vector<int> m(n+1,0);
    for(auto i:v) m[i-1]++;
    for(auto i:m) cout<<i<<endl;
    return 0;
}

Measured memory_bytes: 5576
import java.util.*;
public class Main {
	public static void main(String[] args){
	  Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      long[] a = new long[n];
      int last = 0;
      for(int i=0;i<n;i++){
        a[i] = sc.nextLong();
      }

      //もし今日の金額より高い値段の日があるなら買う
      
      //もし今の手持ちよりも安くなる日があるなら、
      //その日までのうち一番高い日で売却
      //そして安くなる日に購入
      //購入条件としては、
      //今日の金額より高い値段があるなら
      //100購入1000
      //130売却1300
      //115購入@11+35
      //150売却1650+45
      
      long stock = 0;//持ち株数
      long cash = 1000;//持ち現金
      int sellday = 0;//今より安い日
      int buyprice = 0;//
      long maxprice = 0;//期間中に一番高い日
      for(int i=0;i<n;i++){
        sellday = n;
        for(int j=i+1;j<n;j++){
          if( a[j] < a[j-1] ){
            sellday = j;
            break;
          }
        }
        maxprice = 0;
        for(int j=i+1;j<sellday&&j<n;j++){
          if( maxprice < a[j] ){
            maxprice = a[j];
          }
        }
        if( maxprice > 0 ){
        stock = cash / a[i];
        cash = cash % a[i];
        cash = cash + stock * maxprice;
        i = sellday - 1;
        stock = 0 ;
        }
        //System.out.println(i+"日目:"+stock+","+cash+","+sellday);
      }
      System.out.println(cash);
	}
}

Measured memory_bytes: 27136
#include <cstdio>
#include <algorithm>
#include <iostream>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fod(i,a,b) for(int i=a;i>=b;--i)
#define efo(i,q) for(int i=A[q];i;i=B[i][0])
#define min(q,w) ((q)>(w)?(w):(q))
#define max(q,w) ((q)<(w)?(w):(q))
using namespace std;
typedef long long LL;
const int N=200500,mo=1e9+7;
int read(int &n)
{
	char ch=' ';int q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n;
}
int m,n,ans;
LL jc[N],jcn[N];
LL f[N],g[N];
LL er[N];
LL ksm(LL q,int w)
{
	LL ans=1;
	for(;w;w>>=1,q=q*q%mo)if(w&1)ans=ans*q%mo;
	return ans;
}
LL C(int m,int n){return (n>m)?0:jc[m]*jcn[m-n]%mo*jcn[n]%mo;}
int main()
{
	int q,w,mx=0;
	read(n),read(m);
	int m1=m+n;
	jc[0]=1;fo(i,1,m1)jc[i]=jc[i-1]*i%mo;
	jcn[m1]=ksm(jc[m1],mo-2);fod(i,m1-1,0)jcn[i]=jcn[i+1]*(i+1LL)%mo;
	er[0]=1;er[1]=ksm(2,mo-2);fo(i,2,m1)er[i]=er[i-1]*er[1]%mo;

	fo(i,1,m1)
	{
		if(i>m)f[i]=(f[i-1]+C(i-2,m-1)*er[i-1])%mo;else f[i]=0;
		if(i>n)g[i]=(g[i-1]+C(i-2,n-1)*er[i-1])%mo;else g[i]=0;
	}
	fo(i,1,m1)
	{
		LL t1=(1-f[i]-g[i])%mo;
		ans=(t1*er[1]+f[i])%mo;
		printf("%d\n",(ans+mo)%mo);
	}


	return 0;
}

Measured memory_bytes: 9984
n,k=map(int,input().split())
import sys
mod=10**9+7 ; inf=float("inf")
from math import sqrt, ceil
from collections import deque, Counter, defaultdict #すべてのkeyが用意されてる defaultdict(int)で初期化
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import ROUND_HALF_UP,Decimal  #変換後の末尾桁を0や0.01で指定
  #Decimal((str(0.5)).quantize(Decimal('0'), rounding=ROUND_HALF_UP))
from functools import lru_cache
from bisect import bisect_left as bileft, bisect_right as biright
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########

A=[0]*(10**5+1)
for i in range(n):
    a,b=map(int,input().split())
    A[a]+=b 
R=[0]*(10**5+1)
for i  in range(10**5):
    R[i+1]=R[i]+A[i+1]
print(bileft(R,k)) 


Measured memory_bytes: 17676
#include <bits/stdc++.h>
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int main() {
    ll a, b, c;
    cin >> a >> b >> c;
    if(a % 2 == 1 && b % 2 == 1 && c % 2 == 1)cout << min({a * b, b * c, c * a});
    else cout << 0 << endl;
}      


Measured memory_bytes: 256
import math
import itertools

N = int(input())

xy = []

for i in range(N):
    li=list(map(int,input().split()))
    xy.append(li)


#メモ化テーブル( N * 2)
#町 i と　j の距離
dis = [ [0 for col in range(N)] for row in range(N) ]

#二点間の距離を求めておく
for i in range(N):
    for j in range(N):
        dis[i][j] = math.sqrt( (xy[j][0] - xy[i][0]) ** 2 +(xy[j][1] - xy[i][1]) ** 2 )

perm = []
for i in range(N):
    perm.append(i)

ans = 0

for v in itertools.permutations(perm):
    for i in range(len(v)-1):
        ans += dis[v[i]][v[i+1]]

print(ans/math.factorial(N))


Measured memory_bytes: 41452
N = int(input())
h = [int(i) for i in input().split()]

dp = [0] * N
dp[0] = 0
dp[1] = abs(h[1]-h[0])

for i in range(2, N):
    dp_1 = dp[i-2] + abs(h[i]-h[i-2])
    dp_2 = dp[i-1] + abs(h[i]-h[i-1])
    dp[i] = min(dp_1, dp_2)
    
print(dp[N-1])

Measured memory_bytes: 13980
#include <algorithm>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <iomanip>
#include <sstream>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;
typedef long long ll;

int gcd(int a, int b) { return b ? gcd(b, a%b) : a;}
int main() {
	int a, b; cin >> a >> b;
	cout << gcd(a, b) << endl;
}



Measured memory_bytes: 3104
#include<bits/stdc++.h>
#define LL long long
#define clr(x,i) memset(x,i,sizeof(x))
using namespace std;
int n,m,a[100005],ans;
int gcd(int a,int b)
{
	if(!b) return a;
	return gcd(b,a%b);
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	if(n==1) {cout<<abs(m-a[1])<<endl; return 0;}
	ans=abs(m-a[1]);
	for(int i=2;i<=n;i++)
	  ans=gcd(ans,abs(m-a[i]));
	cout<<ans<<endl;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define all(a) a.begin(), a.end()
#define P pair<int, int>
#define F first
#define S second
#define mod 1000000007
#define INF 9000000000000000000
#define R(i) V[i]-V[i-1]
signed main() {
    int n;cin>>n;
    vector<int>V(1010,0);
    rep(i,n){
        int l;cin>>l;
        V[l]++;
    }
    rep(i,1009)V[i+1]+=V[i];
    int count=0;
    for(int i=1;i<1001;i++){
        int x=V[i]-V[i-1];
        int a=x*(x-1)*(x-2)/6;
        int b=x*(x-1)/2*(V[min((int)1009,i*2-1)]-x);
        count+=a;
        count+=b;
        for(int j=i+1;j<1001;j++){
            int y=V[j]-V[j-1];
            int c=min((int)1009,i+j-1);
            int d=max(j-i,j);
            if(c<d)continue;
            count+=x*y*(V[c]-V[d]);
        }
        //cout<<a<<' '<<b<<endl;
    }
    cout<<count<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#define MAX 100000

int p(int i){return i/2;}
int l(int i){return 2*i;}
int r(int i){return 2*i+1;}

int main(){
  int H,i,A[MAX+1];

  scanf("%d",&H);
  for(i=1;i<=H;i++) scanf("%d",&A[i]);

  for(i=1;i<=H;i++){
    printf("node %d: key = %d, ",i,A[i]);
    if(p(i)>=1) printf("parent key = %d, ",A[p(i)]);
    if(l(i)<=H) printf("left key = %d, ",A[l(i)]);
    if(r(i)<=H) printf("right key = %d, ",A[r(i)]);
    printf("\n");
  }
  return 0;
}

  



Measured memory_bytes: 2100
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		String t = sc.next();
		int count = 0;
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == t.charAt(i)) {
				++count;
			}
		}
		System.out.println(count);
	}
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int l, r;
    cin >> l >> r;
    if (l / 2019 < r / 2019) {
        cout << 0 << endl;
        return 0;
    }
    l %= 2019, r %= 2019;
    if (l >= r) {
        r += 2019;
    }
    // cout << l << " " << r << endl;
    int Min = INT_MAX;
    for (int i = l; i <= r; i++) {
        for (int j = i + 1; j <= r; j++) {
            Min = min((i * j) % 2019, Min);
        }
    }
    cout << Min << endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>
#include<limits.h>
#include<cassert>
#include<iterator>
#include<complex>
#include<stack>
#include<sstream>
using namespace std;
typedef  long long int lint;
typedef pair<int, int> IP;
typedef pair<lint, lint> LLP;
typedef pair<char, char>CP;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repr(i, n) for (int i = n; i >= 0; i--)
#define sort(v) sort((v).begin(), (v).end())
#define reverse(v) reverse((v).begin(), (v).end())
#define upper(v,hoge) upper_bound(v.begin(),v.end(),hoge)
#define lower(v,hoge) lower_bound(v.begin(),v.end(),hoge)
#define llower(v,hoge) *lower_bound(v.begin(), v.end(), hoge)
#define lupper(v,hoge) *upper_bound(v.begin(), v.end(), hoge)

int main() {
	lint N;
	cin >> N;
	vector<lint>L(N);
	rep(i, N) {
		cin >> L[i];
	}
	sort(L);
	lint ans = 0;
	lint a, b;
	rep(i, N) {
		rep(j, N) {
			if (i < j) {
				a = L[i];
				b = L[j];
				ans += upper(L, a + b - 1) - lower(L, abs(a - b) + 1);
				if (abs(a - b) < a && a < a + b)ans--;
				if (abs(a - b) < b && b < a + b)ans--;
			}

		}
	}
	cout << ans / 3 << endl;
}


Measured memory_bytes: 256
#[allow(unused_imports)]
use itertools::Itertools;
#[allow(unused_imports)]
use num::Integer;
#[allow(unused_imports)]
use proconio::derive_readable;
use proconio::fastout;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::cmp;

#[fastout]
fn main() {
  input! {
    n: usize,
    k: i64,
    a: [Usize1; n],
  }
  let mut head = 0;
  let mut cycle = 0;
  let mut visited = vec![None; n];
  let mut current = 0;
  // visited[current] = Some(0);
  let mut index = vec![0; n];
  for i in 0i64.. {
    if let Some(v) = visited[current] {
      head = v;
      cycle = i - v;
      break;
    }
    visited[current] = Some(i);
    index[i as usize] = current;
    current = a[current];
  }
  let ans = if k < head {
    index[k as usize]
  } else {
    index[((k - head) % cycle + head) as usize]
  } + 1;

  println!("{}", ans);
}


Measured memory_bytes: 9468
"""
import random
import functools
import copy
import bisect
import array
import re
import collections
import heapq
import fractions
import itertools
import string
import math
from operator import itemgetter as ig
from bisect import bisect_left, bisect_right, insort_left, insort_right
from itertools import permutations, combinations, product, accumulate, groupby
from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 7)
# import numpy as np

inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
'''for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:'''
"""
from collections import deque, defaultdict, Counter
import math
import sys
sys.setrecursionlimit(10 ** 7)


def wi(): return list(map(int, sys.stdin.readline().split()))
# WideIntPoint


def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]


def ws(): return sys.stdin.readline().split()


def si(): return int(sys.stdin.readline())  # SingleInt


def ss(): return input()


def hi(n): return [si() for _ in range(n)]


def hs(n): return [ss() for _ in range(n)]  # HeightString


def s_list(): return list(input())


def mi(n): return [wi() for _ in range(n)]  # MatrixInt


def mip(n): return [wip() for _ in range(n)]


def ms(n): return [ws() for _ in range(n)]


def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[
    0]] for _ in range(n)]  # NumberGrid


def grid(n): return [s_list() for _ in range(n)]


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm(a, b):
    """a,bの最小公倍数"""
    return a * b // gcd(a, b)


def main():
    s = input()
    if s[2] == s[3] and s[4] == s[5]:
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()


Measured memory_bytes: 38256
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <cassert>
#include <functional>

using namespace std;

#define LOG(...) printf(__VA_ARGS__)
//#define LOG(...)
#define FOR(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define REP(i,n) for(int i=0;i<(int)(n);++i)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())
#define RSORT(c) sort((c).rbegin(),(c).rend())
#define CLR(a) memset((a), 0 ,sizeof(a))

typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vb> vvb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int dx[] = { -1, 0, 1, 0 }; const int dy[] = { 0, 1, 0, -1 };
struct cminmax{
	char c;
	int minx;
	int maxx;
	int miny;
	int maxy;
};
int main() {
	int n;
	cin >> n;
	while (n--){
		bool safe = true;
		int h, w;
		cin >> h >> w;
		vector<cminmax> vcmm;
		vector<vector<char>> vvc(h);
		REP(i, h){
			string s;
			cin >> s;
			REP(j, w){
				vvc[i].push_back(s[j]);
				if (s[j] != '.'){
					if (vcmm.empty()){
						vcmm.push_back({ s[j], j, j, i, i });
					}
					else{
						int b = -1;
						REP(k, vcmm.size()){
							if (vcmm[k].c == s[j]){
								b = k;
								break;
							}
						}
						if (b == -1){
							vcmm.push_back({ s[j], j, j, i, i });
						}
						else{
							vcmm[b].maxx = max(vcmm[b].maxx, j);
							vcmm[b].minx = min(vcmm[b].minx, j);
							vcmm[b].maxy = max(vcmm[b].maxy, i);
							vcmm[b].miny = min(vcmm[b].miny, i);
						}
					}
				}
			}
		}
		for (int l = 0; l < 10&&!vcmm.empty();l++){
			if (l == 9){
				safe = false;
				break;
			}
			REP(i, vcmm.size()){
				bool rect = true;
				for (int j = vcmm[i].miny; j <= vcmm[i].maxy&&rect; j++){
					for (int k = vcmm[i].minx; k <= vcmm[i].maxx&&rect; k++){
						if (vvc[j][k] != vcmm[i].c && vvc[j][k] != '0')rect = false;
					}
				}
				if (rect){
					for (int j = vcmm[i].miny; j <= vcmm[i].maxy&&rect; j++){
						for (int k = vcmm[i].minx; k <= vcmm[i].maxx&&rect; k++){
							vvc[j][k] = '0';
						}
					}
					vcmm.erase(vcmm.begin()+i);
				}
			}
		}
		if (safe)cout << "SAFE" << endl;
		else cout << "SUSPICIOUS" << endl;
	}

}

Measured memory_bytes: 1232
#include <iostream>
#include <cmath>
#include <string.h>
#include <iomanip>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <tuple>
#include <queue>
using namespace std;

typedef long long ll;

#define INF 100000000;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repl(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rrep(i, n) for (ll i = n - 1; i >= 0; i--)
#define eps 1.0e-14;

queue<pair<int,int>> que;
string s[1005];
ll ans = 0;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};

int main(){
	int h,w; cin >> h >> w;
	rep(i,h) cin >> s[i];

	vector<vector<int>> vec(h, vector<int>(w, -1));

	rep(i,h){
		rep(j,w){
			if(s[i][j] == '#'){
				que.push(make_pair(i,j));
				vec[i][j] = 0;
			}
		}
	}
	while(que.size() != 0){
		pair<int,int> nowq = que.front();
		que.pop();
		rep(i,4){
			int nowx = nowq.first + dx[i];
			int nowy = nowq.second + dy[i];
			if(nowx >= h || nowy >= w || nowx < 0 || nowy < 0) continue;
			if(vec[nowx][nowy] == -1){
				vec[nowx][nowy] = vec[nowq.first][nowq.second] + 1;
				que.push(make_pair(nowx,nowy));
			}
		}
	}
	int ans = 0;
	rep(i,h){
		rep(j,w){
			ans = max(ans,vec[i][j]);
			//cout << vec[i][j];
		}
		//cout << endl;
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 13456
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_map>
#include<climits>
#include<cstdlib>
#include<cmath>
#include<string>
#include<iomanip>
#include<bitset>

using namespace std;

#define ll long long int

ll const MOD = 1000000007;
ll const INF = (long long int)1 << 61;

ll mypow(ll x,ll n){
    ll ret = 1;
    while(n > 0){
        if(n&1){
            ret = (ret*x)%MOD;
        }
        x = (x*x)%MOD;
        n >>= 1;
    }
    return ret;
}

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

    vector<ll> a(n);

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

    bool even = true;

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

    vector<ll> aba(n);
    for(int i = 0; i < n; i++){
        aba[i] = abs(a[i]);
    }

    sort(aba.begin(),aba.end());

    ll ans = 0;

    for(int i = 0; i < n; i++){
        ans += aba[i];
    }

    if(!even){
        ans -= aba[0]*2;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1792
# import sys
# input = sys.stdin.readline
import collections

def main():
    H, W = input_list()
    grid = [input() for i in range(H)]
    dist = [[-1]*W for _ in range(H)]
    black_cells = collections.deque()
    for h in range(H):
        for w in range(W):
            if grid[h][w] == '#':
                black_cells.append((h, w))
                dist[h][w] = 0

    def bfs(black_cells, dist):
        d = 0
        while black_cells:
            h, w = black_cells.popleft()
            d = dist[h][w]
            for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
                new_h = h + dy
                new_w = w + dx
                if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                    continue
                if dist[new_h][new_w] == -1:
                    dist[new_h][new_w] = d + 1
                    black_cells.append((new_h, new_w))
        return d
    
    print(bfs(black_cells, dist))
    
#6 5 2 5 3 2
#1 2 3 4 5 6

def input_list():
    return list(map(int, input().split()))


def input_list_str():
    return list(map(str, input().split()))


if __name__ == "__main__":
    main()


Measured memory_bytes: 115864
#include <bits/stdc++.h>
#define _USE_MATH_DEFINES

#define REP(i, x) for (int i = 0; i < (int)(x); i++)
#define REP1(i, x) for (int i = 1; i <= (int)(x); i++)
#define RREP(i, x) for (int i = ((int)(x)-1); i >= 0; i--)
#define RREP1(i, x) for (int i = ((int)(x)); i > 0; i--)
/*
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };

#define all(x) (x).begin(),(x).end()
*/

using namespace std;

int a[30];
int n, q;
/*
bool solve(int m) {
    REP(bit, 1 << n) {
        int sum = 0;
        REP(i, n) {
            if (bit & (1 << i))
                sum += a[i];
            if (sum == m)
                return true;
            if (sum > m)
                break;
        }
    }
    return false;
}
*/
bool solve(int i, int m) {
    if (m == 0)
        return true;
    if (i >= n) {
        return false;
    }
    return solve(i + 1, m) || solve(i + 1, m - a[i]);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n;
    REP(i, n) { cin >> a[i]; }
    sort(a, a + n);
    cin >> q;
    REP(i, q) {
        int m;
        cin >> m;
        cout << (solve(0, m) ? "yes" : "no") << endl;
    }
}


Measured memory_bytes: 3240
#include <iostream>

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

  long long ans = 0;
  long long acc = 0;
  for (int i=0; i<n; i++) {
    int a;
    std::cin >> a;

    if (a == 0) {
      ans += acc / 2;
      acc = 0;
    }

    acc += a;
  }
  ans += acc / 2;

  std::cout << ans << std::endl;

  return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#define INF 1e18
#define int long long
#define Rep(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) Rep(i, 0, n)
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> PP;
const int mod = 1000000007;
//const int mod = 998244353;

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

    int n;
    cin >> n;
    bool f = n < 1000;
    cout << (f ? "ABC" : "ABD") << endl;
}


Measured memory_bytes: 256
n = int(input())
a = [int(e) for e in input().split()]

d = {}
sum = 0
for e in a:
    sum += e
    if e in d:
        d[e] += 1
    else:
        d[e] = 1


q = int(input())
for i in range(q):
    b, c = [int(e) for e in input().split()]

    if b in d:
        i = d.pop(b)
        if c in d:
            d[c] += i
        else:
            d[c] = i
        sum += (c - b) * i
    
    print(sum)


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


ll N, M;

vector<int> G[100000];
int color[100000];
int white = 0;

//二部グラフ判定
bool dfs(int v, int c) {
    color[v] = c;
    if (c == 1) white++;
    for (ll i = 0; i < G[v].size(); i++) {
        if (color[G[v][i]] == c) return false;
        if (color[G[v][i]] == 0 && !dfs(G[v][i], -c)) return false;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> N >> M;
    for (ll i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--; 
        b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    if (dfs(0,1)) {cout << white*(N-white) - M << endl;} 
    else {cout << N*(N-1)/2 - M << endl;}
    return 0;
}


Measured memory_bytes: 6528
#include "bits/stdc++.h"
using namespace std;
typedef long long li;

li solve(const li l, vector<li> xs) {
    const li n = xs.size() - 1;
    li ans = xs.back();

    li accum = ans;
    for (int rb = n - 1; rb > 0; --rb) {
        int step = n - rb;
        int prev_rb = rb + 1;
        int last_r = n - 2 * step;
        li l_dist = l - xs[prev_rb];

        if (last_r >= 0) {
            accum += 2 * l_dist;
            accum += 2 * xs[last_r];
            accum += 2 * xs[last_r + 1];
            accum -= xs[prev_rb] + xs[rb];
            ans = max(ans, accum);
        } else {
            accum += 2 * l_dist;
            accum -= xs[prev_rb] + xs[rb];
            const int cancel_r = last_r + n + 1;
            accum -= 2 * (l - xs[cancel_r]);
            if (cancel_r + 1 <= n) {
                accum -= 2 * (l - xs[cancel_r + 1]);
            }
            ans = max(ans, accum);
        }
    }

    return ans;
}

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

    li l, n;
    cin >> l >> n;
    vector<li> xs(n + 1), ys(n + 1);
    for (int i = 0; i < n; ++i) {
        cin >> xs[i + 1];
        ys[n - i] = l - xs[i + 1];
    }

    const li ans = max(solve(l, xs), solve(l, ys));
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 6528
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <iomanip>

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

using namespace std;

typedef long long ll;

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

  ll n;
  cin >> n;

  ll ans = 0;

  for (ll x = 1; x * x <= n + 1; x++) {
    if ( n % x == 0 ) {
      ll m = n / x - 1;
      if ( m != 0 && n % m == n / m ) {
        ans += m;
      }
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <vector>
#include <cstring>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>

#define INF 1e9
#define nmax 200010
#define fst first
#define snd second
#define pb push_back
#define SZ(x) ((int)(x.size()))

#define MOD 998244353

#define MOD1 998244353
#define MOD2 666013
#define P1 255
#define P2 2059

using namespace std;

typedef pair<int, int> pii;
typedef long long int ll;

int n;
pii in[nmax];
int arb[nmax * 4], dp[nmax], x[nmax];

int my_search(int ll, int rr, int val)
{
    int sol = ll;

    while (ll <= rr)
    {
        int m = (ll + rr) / 2;

        if (in[m].fst <= val) { sol = m; ll = m + 1; }
        else
            rr = m - 1;
    }

    return sol;
}

int f(int x)
{
    if (x >= MOD) return x - MOD; else
        return x;
}

void update(int node, int l, int r, int pos, int val)
{
    if (l == r) {

        arb[node] = val;
        
        return;
    }

    int m = (l + r) / 2;

    if (pos <= m) update(node * 2, l, m, pos, val); else
        update(node * 2 + 1, m + 1, r, pos, val);

    arb[node] = max(arb[node * 2], arb[node * 2 + 1]);
}

int query(int node, int l, int r, int lp, int rp)
{
    if (l >= lp && r <= rp) return arb[node];

    int maxx = -1;
    int m = (l + r) / 2;

    if (lp <= m) maxx = max(maxx, query(node * 2, l, m, lp, rp));
    if (rp > m) maxx = max(maxx, query(node * 2 + 1, m + 1, r, lp, rp));

    return maxx;
}

int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; i++) scanf("%d %d", &in[i].fst, &in[i].snd);

    sort(in + 1, in + n + 1);

    // x[i] -> number of robots that get activated when i'th is activated

    x[n] = 1;

    update(1, 1, n, n, n);

    for (int i = n - 1; i >= 1; i--) {

        int pos = my_search(i, n, in[i].fst + in[i].snd - 1);

        int maxx = pos;

        if (pos > i) maxx = max(maxx, query(1, 1, n, i + 1, pos));

        x[i] = maxx - i + 1;

        update(1, 1, n, i, i + x[i] - 1);
    }

    dp[0] = 1;

    for (int i = 1; i <= n; i++) {

        // don't activate this one

        dp[i] = f(dp[i] + dp[i - 1]);

        // activate this one

        dp[i + x[i] - 1] = f(dp[i + x[i] - 1] + dp[i - 1]);
    }

    printf("%d", dp[n]);

    // IMPORTANT!!!!!
    // Are you missing something????
    // check limits, int or ll

    return 0;
}

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

using namespace std;

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

  int N; cin>>N;
  long ans = 0;
  map<int, long> cntmap;
  int d = 1;
  for (int i = 1; i <= N; i++) {
    if (i == d*10)
      d *= 10;
    auto key = i/d * 10 + i%10;
    cntmap[key]++;
  }
  for (int i = 10; i <= 99; i++) {
    ans += cntmap[i] * cntmap[i/10+i%10*10];
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
#define bit(n) (1LL << (n))
#define sz(x) ((ll)(x).size())
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
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;
}

struct mint {
  ll x;
  mint(ll x = 0) : x((x % MOD + MOD) % MOD) {
  }
  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;
  }
  /* 変数名.pow(n) */
  mint pow(ll t) const {
    if (!t)
      return 1;
    mint a = pow(t >> 1);
    a *= a;
    if (t & 1)
      a *= *this;
    return a;
  }

  // 以降はMODが素数のみ
  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;
  }
};

const int MAX = 2000;
long long fac[MAX], finv[MAX], inv[MAX];

/* 前処理 O(n) */
void COMinit() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++) {
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}

/* 計算 O(1) */
long long COM(int n, int k) {
  if (n < k)
    return 0;
  if (n < 0 || k < 0)
    return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

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

  COMinit();
  vector<vector<mint>> dp(K + 1, vector<mint>(N + 1));
  dp[0][0] = 1;
  rep(k, K) {
    rep(n, N + 1) {
      repp(nn, 0, N - n) {
        dp[k + 1][n + nn] += dp[k][n] * COM(N - n, nn) * COM(N - nn, a[k] - nn);
      }
    }
  }

  cout << dp[K][N].x << endl;
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <map>
#include <set>

typedef long long int ll;

using namespace std;
ll a,b,c,aa[100000],bb[100000];
bool ra,rb,rc;
vector<int> va,vb;

#define CE cout<<endl
#define C cout<<
#define E <<endl


int main(){
    cin>>a;
    b=100;
    c=0;
    while(b<a){
        b*=1.01;
        c++;
    }
    C c E;
}

Measured memory_bytes: 3628
package main

import (
	"fmt"
)

var X int

func main() {
	fmt.Scanf("%d", &X)

	ans := 1
	for i := 2; i < X; i++ {
		f := i
		n := i
		for n*f <= X {
			n *= f
			ans = Max(ans, n)
		}
	}
	fmt.Println(ans)
}

func Max(x, y int) int {
	if x > y {
		return x
	}
	return y
}


Measured memory_bytes: 512
#include<stdio.h>
#include<math.h>
int main()
{
    int K,X,st,end,i;
    while(scanf("%d %d",&K,&X)!=EOF)
    {
        st=X-K+1;
        end=X+K-1;
        for(i=st;i<=end;i++)
            printf("%d ",i);
        printf("\n");
    }
    return 0;
}


Measured memory_bytes: 128
n, k = map(int, input().split())
A = list(map(int, input().split()))
S = sum(A[:k])
T = 0
for i in range(k, n):
  T += max(0, A[i])
ans = max(0, S) + T
for i in range(k, n):
  S -= A[i-k]
  S += A[i]
  T += max(0, A[i-k])
  T -= max(0, A[i])
  ans = max(ans, max(0, S)+T)
print(ans)

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

using namespace std;
using ll = long long;
using ld = long double;

vector<int> dep;

void dfs(vector<vector<pair<int,int>>>& g, int v){
    for(int i = 0; i < g[v].size(); i++) {
        int nv=g[v][i].first;
        int len=g[v][i].second;
        if(dep[nv]!=-1) continue;
        dep[nv]=dep[v]+len;
        dfs(g,nv);
    }
}


//#define int long long
//signed main(){
int main() {
//    ios_base::sync_with_stdio(false);
//    cin.tie(NULL);
    int n;
    cin >> n;
    vector<vector<pair<int,int>>> g(n);
    for(int i = 0; i < n-1; i++) {
        int u,v,w;
        cin >> u >> v >> w;
        --u;
        --v;
        w%=2;
        g[u].emplace_back(make_pair(v,w));
        g[v].emplace_back(make_pair(u,w));
    }
    dep.assign(n,-1);
    dep[0]=0;
    dfs(g,0);
    for(int i = 0; i < n; i++) {
        if(dep[i]%2) cout << "0" << "\n";
        else cout << "1" << "\n";
    }



    return 0;
}

Measured memory_bytes: 8192
#include <iostream>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
using namespace std;

int main() {
	double r;
	cin >> r;
	cout << fixed;
	cout << setprecision(6);
	cout << r * r * M_PI << " " << 2 * r * M_PI << endl;
	return 0;
}


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

#define ASC(vec) vec.begin(), vec.end()		// 昇順ソート 例：sort(ASC(vec));
#define DESC(vec) vec.rbegin(), vec.rend()	// 降順ソート 例:sort(DESC(vec));
#define rep(i, n) for(int i = 0; i < (n); i++)
#define Rep(i, n) for(int i = 1; i < n; i++)

const int mod = 1000000007;
const int inf = (int)1e9 + 7;
const long long INF = 1LL << 60;

using ii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vd = vector<double>;
using vb = vector<bool>;
using vl = vector<ll>;
using vs = vector<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvb = vector<vector<bool>>;
using vii = vector<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; }

ll GCD(ll a, ll b) { return b ? GCD(b, a % b) : a; }
ll LCM(ll a, ll b) { return (a * b) / GCD(a, b); }
int round_int(int a, int b) { return (a + (b - 1)) / b; }

// 素因数分解; 返り値は(素数, 乗数)のvector配列
vector<pair<ll, int>> factorize(ll n) {
	vector<pair<ll, int>> res;
	for (ll i = 2; i * i <= n; ++i) {
		if (n % i) continue;
		res.emplace_back(i, 0);
		while (n % i == 0) {
			n /= i;
			res.back().second++;
		}
	}
	if (n != 1) res.emplace_back(n, 1);
	return res;
}

constexpr array<int, 9> dx = { 0, 1, 0, -1, -1, 1, 1, -1, 0 };
constexpr array<int, 9> dy = { 1, 0, -1, 0, 1, 1, -1, -1, 0 };
constexpr auto MAX = 100000;

// ──────────────────────────────────────────────────────────────────

int dp[10010];

int main() {
	int n, W; cin >> n >> W;
	vi v(n), w(n); rep(i, n) cin >> v[i] >> w[i];
	
	dp[0] = 0;

	rep(i, W + 1) {
		rep(j, n) {
			if (i >= w[j]) dp[i] = max(dp[i - w[j]] + v[j], dp[i]);
		}
	}
	cout << dp[W] << endl;
}


Measured memory_bytes: 3144
#include <bits/stdc++.h>
using namespace std;
int main() {
  int a,b,c;
  cin >> a >> b >> c;
  
  if(a<c && c<b || b<c && c<a){
    cout << "Yes" << endl;
  }
  else{
    cout << "No" << endl;
  }
}


Measured memory_bytes: 3600
#include<iostream>
#include<vector>

using namespace std;

/*int N=36;
bool isStable(string a[N], string b[N]){
    for(int i=0; i<N; i++){
        for(int j=i+1; j<N; j++){
            for(int c=0; c<N; c++){
                for(int d=c+1; d<N; d++){
                    if(a[i][1]==b[j][1] && a[i]==b[d] && a[j]==b[c])    return false;
                }
            }
        }
    }
    return true;
}*/
//int M=36;
bool isStable(vector<string> a, vector<string> b){
    int M=a.size();
    for(int i=0; i<M; i++){
        if(a[i]!=b[i])  return false;
    }
    return true;
}

int main(){
    int N;
    cin>>N;
    //string s[N];
    //string bubble[M];
    //string selection[M];
    vector<string>s(N);
    vector<string>bubble(N);
    vector<string>selection(N);
    for(int i=0; i<N; i++){
        cin>>s[i];
        bubble[i]=s[i];
        selection[i]=s[i];
    }

    for(int i=0; i<N; i++){
        for(int j=N-1; j>i; j--){
            if(int(bubble[j][1])<int(bubble[j-1][1])){
                string memo=bubble[j-1];
                bubble[j-1]=bubble[j];
                bubble[j]=memo;
            }
        }
    }
    for(int i=0; i<N-1; i++){
        cout<<bubble[i]<<" ";
    }
    cout<<bubble[N-1]<<endl;
    cout<<"Stable\n";
    //if(isStable(s, bubble)) cout<<"Not stable\n";
    //else    cout<<"Stable\n";

    for(int i=0; i<N; i++){
        int minj=i;
        for(int j=i; j<N; j++)
            if(int(selection[j][1])<int(selection[minj][1]))
                minj=j;
        string memo=selection[minj];
        selection[minj]=selection[i];
        selection[i]=memo;
    }
    for(int i=0; i<N-1; i++){
        cout<<selection[i]<<" ";
    }
    cout<<selection[N-1]<<endl;
    if(isStable(bubble, selection))  cout<<"Stable\n";
    else    cout<<"Not stable\n";
}



Measured memory_bytes: 3200
import java.util.*;

/**
 * A
 */
public class Main {

    void run() {

        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        int[] A = new int[n];
        int[] B = new int[n];

        int max=0;

        for(int i=0; i<n; i++) {
            A[i] = sc.nextInt();
            if(A[i]>max) {
                max = A[i];
            }
        }

        sc.close();

        countingSort(A, B, max);

        /* TOO SLOW
        for(int i=1; i<n; i++) {
            if(i == n-1) {
                System.out.println(" "+B[i]);
            } else {
                System.out.print(" "+B[i]);
            }
        }
        */

        StringBuilder br = new StringBuilder();

        for(int i=0; i<n-1; i++) {
            br.append(B[i]+" ");
        }
        System.out.println(br.append(B[n-1]));

    }

    void countingSort(int[] A, int[] B, int k) {

        int[] C = new int[k+1];

        for(int j=0; j<A.length; j++) {
            C[A[j]]++;
        }

        for(int i=1; i<k+1; i++) {
            C[i] = C[i] + C[i-1];
        }

        for(int j=A.length-1; j>=0; j--) {

            B[C[A[j]]-1] = A[j];
            C[A[j]]--;

        }

    } 

    public static void main(String[] args) {
        new Main().run();
    }
}



Measured memory_bytes: 578728
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> PA;
typedef priority_queue<int> PQ;
typedef vector<int> VE;
#define int long long
#define INF 1000000009
#define INFL 1000000000000000018
#define mod 1000000007
#define pb push_back
#define MAXN 100005

int n, m, x[MAXN], y[MAXN], a[MAXN], ans;
vector<int> fid[MAXN];
bool flag[MAXN];

signed main()
{
    cin >> n >> m;
    for(int i = 0; i <= n; i++){
        a[i] = 1;
    }
    flag[1] = true;
    for(int i = 0; i < m; i++){
        cin >> x[i] >> y[i];
        if(flag[x[i]]){
            flag[y[i]] = true;
        }
        a[x[i]]--;
        a[y[i]]++;
        if(a[x[i]] == 0){
            flag[x[i]] = false;
        }
    }

    for(int i = 1; i <= n; i++){
        if(flag[i]){
            ans++;
        }
    }
    cout << ans << endl;

    return 0;
}


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

#define int long long 

int32_t main()
{
    int n,k;
    cin>>n>>k;
    int dp[n+1][n+1][k+1];
    memset(dp, 0, sizeof(dp));
    int v[n];
    for(int i=0; i<n; i++)
    {
        cin>>v[i];
    }
    for(int i=0; i<n; i++)
    {
        for(int j=i; j<n; j++)
        {
            int alpha = 0;
            dp[i][j][1] = max(alpha, max(v[i], v[j]));
        }
    }
    for(int i=2; i<=k; i++)
    {
        for(int j=0; j<n; j++)
        {
            dp[j][j][i] = dp[j][j][1];
        }
    }
    for(int atmost_k = 2; atmost_k<=k; atmost_k++)
    {
        for(int i=0; i<n; i++)
        {
            for(int j=i+1; j<n; j++)
            {
                int alpha = 0;
                int cnt_i=1, cnt_j=1,val_i=v[i], val_j=v[j];
                if(v[i]<0)
                {
                    cnt_i = 2;
                    val_i = 0;
                }
                if(v[j]<0)
                    val_j=0, cnt_j = 2;
                dp[i][j][atmost_k] = max(dp[i][j][atmost_k-1], max(max(dp[i+1][j][atmost_k-cnt_i] + val_i, dp[i+1][j][atmost_k-1] + v[i]),max(dp[i][j-1][atmost_k-1] + v[j],val_j + dp[i][j-1][atmost_k-cnt_j])));
            }
        }
    }
    cout<<dp[0][n-1][k];
    return 0;
}

Measured memory_bytes: 2304
/*    _                     _     
  __| | _____   _____  ___| |__  
 / _` |/ _ \ \ / / _ \/ __| '_ \ 
| (_| |  __/\ V /  __/\__ \ | | |
 \__,_|\___| \_/ \___||___/_| |_|
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
#define faster       ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll          long long
#define pb          push_back
#define ppb         pop_back
#define  endl    '\n'
#define mii         map<ll int,ll int>
#define msi         map<string,ll int>
#define mis         map<ll int, string>
#define mpi         map<pair<ll int,ll int>,ll int>
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define vs          vector<string>
#define all(a)      (a).begin(),(a).end()
#define maxpq       priority_queue<ll>
#define minpq       priority_queue<ll, vector<ll>, greater<ll> >
#define F           first
#define S           second
#define rep(i,j,k)  for(int i=j;i<k;i++)
#define rrep(i,a,b)  for(ll i=a;i>=b;i--)
#define present(c,x) ((c).find(x) != (c).end())
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 
#define what_is(x)  cout << #x << " is " << x << endl;
#define DECIMAL(n)  cout << fixed ; cout << setprecision(n);
#define time        cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }


using namespace std;
using namespace __gnu_pbds;
 
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a * (b / gcd(a, b)); }
#define N  100005

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}
 
int main(){
  faster
   string s,s1;
   cin>>s>>s1;
   int n=s.length(),m=s1.length();
   int dp[n+1][m+1];
   int choice[n+1][m+1];
   memset(choice,0,sizeof(choice));
   memset(dp,0,sizeof(dp));
   vector<int> v;
   rep(i,0,n){
   	rep(j,0,m){
   		if(i>0){
   			dp[i][j]=dp[i-1][j];
   			choice[i][j]=0;
   		}
   		if(j>0){
   			if(dp[i][j-1]>dp[i][j]){
   				dp[i][j]=dp[i][j-1];
   				choice[i][j]=1;
   			}
   		}
   		if(s[i]==s1[j]){
   			dp[i][j]=1+dp[i-1][j-1];
   			choice[i][j]=2;
   		}

   	}
   }
   int i=n-1,j=m-1;
   string sub;
   while(i>=0 && j>=0){
   	if(choice[i][j]==0)i--;
   	else if(choice[i][j]==1)j--;
   	else{
   		sub.pb(s[i]);
   		i--;
   		j--;
   	}
   }
   reverse(all(sub));
   cout<<sub<<endl;
 

}


 

Measured memory_bytes: 74020
#include<bits/stdc++.h>
using namespace std;
const int maxn=1000000+100;
int trie[maxn][30];
int t[30];
int cnt[maxn*30];
char ch[30];
int c[30];
long long ans=0;
int n;
long long tot=0,ncnt=0;
void insert(){
	long long u=0;
	for(int i=0;i<tot;i++){
		int id=c[i];
		if(!trie[u][id])
		trie[u][id]=++ncnt;
		u=trie[u][id]; 
	}
	ans+=(long long)cnt[u];
	cnt[u]++;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
    	cin>>ch;
    	tot=0;
    	int len=strlen(ch);
    	for(int i=0;i<len;i++)
		t[ch[i]-'a']++;
		for(int i=0;i<=26;i++)
		  while(t[i]){
		  	c[tot++]=i;
		  	t[i]--;
		}
		insert();
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 59520
#include<iostream>
#include<algorithm>
using namespace std;
struct p{
	long x,y,z;
};
p a[1000];int n,m;long ans;
main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)cin>>a[i].x>>a[i].y>>a[i].z;
	for(int i=0;i<8;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(i&1)a[j].x*=-1;
			if(i&2)a[j].y*=-1;
			if(i&4)a[j].z*=-1;
		}
		sort(a,a+n,[](const p a,const p b){return a.x+a.y+a.z>b.x+b.y+b.z;});
		long A=0,B=0,C=0;
		for(int j=0;j<m;j++)A+=a[j].x,B+=a[j].y,C+=a[j].z;
		ans=max(ans,abs(A)+abs(B)+abs(C));
		for(int j=0;j<n;j++)
		{
			if(i&1)a[j].x*=-1;
			if(i&2)a[j].y*=-1;
			if(i&4)a[j].z*=-1;
		}
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
using namespace std;
#define N 102
int x[N],y[N];
int main() {
	int i,n,m,X,Y;
	scanf("%d%d%d%d",&n,&m,&X,&Y);
	for( i=0;i<n;i++ )
	{
		scanf("%d",&x[i]);
	}
	for( i=0;i<m;i++ )
	{
		scanf("%d",&y[i]);
	}
	sort(x,x+n);
	sort(y,y+m);
	if( x[n-1]>=y[0] || x[n-1]>=Y || y[0]<=X || Y-X==1 )
		printf("War\n");
	else
		printf("No War\n");
	return 0;
	}


Measured memory_bytes: 256
def solve():
    N = int(input())
    #AAwIdx = list(map(int,input().split()))
    AAwIdx = [(i,A) for i, A in enumerate(map(int, input().split()))]
    #for i in range(N):
    #    AAwIdx[i][0] = i
    #    AAwIdx[i][1] = AA[i]
    AA_sorted = sorted(AAwIdx, key=lambda x: x[1], reverse=True)
    #print(AA_sorted)

    answer = [[0]*(N+1) for _ in range(N+1)]

    ans_all = 0
    Idx_i = 0
    Idx_f = N-1
    for i in range(0,N):
        for no in range(i+1):
            idxi = i-no
            idxf = Idx_f-no
            ans = answer[i-no][no] + abs(AA_sorted[i][0]-idxi)*AA_sorted[i][1]
            if ans>answer[i+1-no][no]:
                answer[i+1-no][no] = ans
            ans = answer[i-no][no] + abs(AA_sorted[i][0]-idxf)*AA_sorted[i][1]
            if ans>answer[i-no][no+1]:
                answer[i-no][no+1] = ans
    for i in range(N,N+1):
        for no in range(i+1):
            if ans_all<answer[i-no][no]:
                ans_all = answer[i-no][no]

    print(ans_all)
solve()

Measured memory_bytes: 136128