akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<set>
#include<map>
#include<bitset>
#include<stack>
#include<ctime>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<pli> vpli;

inline ll read(){
    ll Hashimoto=0;
	bool Kanna=1;
    char I_Love=getchar();
    while(I_Love<'0'||I_Love>'9'){
        if(I_Love=='-')Kanna=0;
        I_Love=getchar();
    }
    while(I_Love>='0'&&I_Love<='9'){
        Hashimoto=Hashimoto*10+I_Love-'0';
        I_Love=getchar();
    }
    return (Kanna?Hashimoto:-Hashimoto);
}
template<typename T1,typename T2> inline void Umax(T1 &a,T2 b){
	if(a<b)a=b;
}
template<typename T1,typename T2> inline void Umin(T1 &a,T2 b){
	if(a>b)a=b;
}

#define I_Love_Hashimoto_Kanna main
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
#define file freopen("I_Love_Hashimoto_Kanna.out","w",stdout);
#define RE cout<<"I_Love_Hashimoto_Kanna"<<endl;
#define Tone(Kanna) cout<<Kanna<<endl;
#define Tall(Hashimoto,Kanna) for(int I_Love=0;I_Love<(Kanna);++I_Love)cout<<Hashimoto[I_Love]<<(I_Love==(Kanna)-1?"\n":" ");
#define FOR(I_Love,Hashimoto,Kanna) for(int I_Love=Hashimoto;I_Love<(Kanna);++I_Love)
#define MP(Hashimoto,Kanna) make_pair(Hashimoto,Kanna)
#define REV(Kanna) reverse(Kanna.begin(),Kanna.end());
#define SORT(Kanna) sort(Kanna.begin(),Kanna.end());
#define UNIQUE(Kanna) Kanna.erase(unique(Kanna.begin(),Kanna.end()),Kanna.end());
#define inf (int)1e9
#define linf (ll)1e18
#define mod (inf+7)

int n;
string s;
vi son[111111];
stack<int>nd;
int cur=1;

void dfs(int x,int sz){
	sz--;
	while(!nd.empty()&&sz>=nd.top()){
		int val=nd.top();
		nd.pop();
		sz-=val;
		son[x].push_back(cur);
		dfs(cur++,val);
	}
	while(sz){
		sz--;
		son[x].push_back(cur);
		dfs(cur++,1);
	}
}

int I_Love_Hashimoto_Kanna() {
	//完全想清楚了再开始写。
	//写不顺、不知道怎么写、很乱的时候，停下来好好想想。
	//做得慢总比做不出好。
	fastio;
	cin>>s;
	n=s.size();
	s='0'+s;
	if(s[1]=='0'){
		Tone(-1);
		return 0;
	}
	FOR(i,0,n+1){
		if(s[i]!=s[n-i]){
			Tone(-1);
			return 0;
		}
		if(s[i]=='1') nd.push(i);
	}
	dfs(0,n);
	FOR(i,0,n){
		FOR(j,0,son[i].size()){
			printf("%d %d\n",i+1,son[i][j]+1);
		}
	}
	
	return 0;
}


Measured memory_bytes: 12012
N, M = map(int, input().split())
K = []
S = []
for i in range(M):
    s = list(map(int, input().split()))
    K.append(s[0])
    S.append(s[1:])
P = list(map(int, input().split()))

counter = 0

for i in range(1<<N):
    b = format(i, '0%db'%N)
    flag = True
    for j in range(M):
        c = 0
        for k in S[j]:
            c += int(b[k-1])
        if c % 2 != P[j]:
            flag = False
    if flag:
        counter += 1

print(counter)

Measured memory_bytes: 41964
object Main {
  def main(args: Array[String]): Unit = {
    val pw = new java.io.PrintWriter(System.out)

    val sc = new java.util.Scanner(System.in)
    val N = sc.nextInt
    val A = Vector.fill(N)(sc.nextInt)
    sc.close()

    val max2 = A.sorted.takeRight(2)
    A.foreach(d => {
      if (d == max2.last) {
        pw.println(max2.head)
      } else {
        pw.println(max2.last)
      }
    })
    pw.flush()
  }
}

Measured memory_bytes: 75456
import itertools
from bisect import bisect_left

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

# A, B の組み合わせでソート
AB = list(map(lambda a: a[0]+a[1], itertools.product(A, B)))
AB.sort()

C.sort()
C.reverse()
c0 = C[0]
ans = [c0 + ab for ab in AB][-K:]
AB.reverse()
for c in C[1:]:
  for ab in AB:
    abc = ab + c
    i = bisect_left(ans, abc)
    if i > len(ans) - K:
      ans = (ans[:i] + [abc] + ans[i:])[-K:]
    else:
      break
ans.reverse()
for abc in ans:
  print(abc)

Measured memory_bytes: 102172
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <stdio.h>
#include <iomanip>
#include <limits>
#include <list>
#include <string>
#include <queue>
#include <deque>
#include <tuple>
#include <map>
#include <sstream>
using namespace std;
#define MOD (long long int)(1e9+7)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define FOR(i,a,b) for(int i=a; i<(int)(b); i++)
#define ALL(x) (x).begin(),(x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define SORT(c) sort(ALL(x))
#define CLR(a) memset((a), 0 ,sizeof(a))
#define PB push_back
#define MP make_pair
#define SP << " " <<
const int INF = 1001001001;
const ll LINF = 100100100100100100;
const double EPS = 1e-10;
const long double PI  = acos(-1.0L);
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
#define chmax(a,b) a = (((a)<(b))?(b):(a))
#define chmin(a,b) a = (((a)>(b))?(b):(a))

__attribute__((constructor))
void initial(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(15);
}

ll mpow(ll a, ll b){
  if(b==0) return 1;
  else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}
  else return mpow(a,b-1)*a%MOD;
}
ll lpow(ll a, ll b){
  if(b==0) return 1;
  else if(b%2==0){ll memo = lpow(a,b/2); return memo*memo;}
  else return lpow(a,b-1)*a;
}
ll gcd(ll a, ll b){
  if(b==0) return a;
  else return gcd(b,a%b);
}
vector<ll> kaijo_memo;
ll kaijo(ll n){
  if(kaijo_memo.size()>n) return kaijo_memo[n];
  if(kaijo_memo.size()==0) kaijo_memo.push_back(1);
  while(kaijo_memo.size()<=n) kaijo_memo.push_back(kaijo_memo[kaijo_memo.size()-1]*kaijo_memo.size()%MOD);
  return kaijo_memo[n];
}
vector<ll> gyaku_kaijo_memo;
ll gyaku_kaijo(ll n){
  if(gyaku_kaijo_memo.size()>n) return gyaku_kaijo_memo[n];
  if(gyaku_kaijo_memo.size()==0) gyaku_kaijo_memo.push_back(1);
  while(gyaku_kaijo_memo.size()<=n) gyaku_kaijo_memo.push_back(gyaku_kaijo_memo[gyaku_kaijo_memo.size()-1]*mpow(gyaku_kaijo_memo.size(),MOD-2)%MOD);
  return gyaku_kaijo_memo[n];
}

ll nCr(ll n, ll r){
  if(n==r) return 1;
  if(n<r ||r<0) return 0;
  ll ret = 1;
  ret *= kaijo(n); ret %= MOD;
  ret *= gyaku_kaijo(r); ret %= MOD;
  ret *= gyaku_kaijo(n-r); ret %= MOD;
  return ret;
}

signed main(){
  int n,k; cin>>n>>k;
	ll ans = 0;
	rep(i,min(k+1,n)){
		ll tmp = 1;
		tmp *= nCr(n,i); tmp *= nCr(n-1,i); tmp %= MOD;
		ans += tmp; ans %= MOD;
	}
	cout << ans << endl;
  return 0;
}


Measured memory_bytes: 5872
sx,sy,tx,ty = map(int,input().split())
tx -= sx
ty -= sy
ans = ""
ans += "U" * ty + "R" * tx
ans += "D" * ty + "L" * tx
ans += "L" + "U"*(ty+1) + "R"*(tx+1) + "D"
ans += "R" + "D"*(ty+1) + "L"*(tx+1) + "U"
print(ans)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vpi = vector<pii>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpl = vector<pll>;
using vs = vector<string>;

int main()
{
    int n;
    cin >> n;
    set<string> s;
    for(int i=0; i<n; i++)
    {
        string ss;
        cin >> ss;
        s.insert(ss);
    }
    cout << s.size() << endl;
    return 0;
}


Measured memory_bytes: 19260
import java.util.*;
import java.awt.*;
import static java.lang.System.*;
import static java.lang.Math.*;
public class Main {
    public static void main(String[] $) {
        Scanner sc = new Scanner(in);
        String s=sc.next();
        int l=0,r=1;
        int n=s.length();
        int ans=0;
        while (r<n&&l<n-1){
            if(l==r)r++;
            if(s.charAt(l)=='S'){
                if(s.charAt(r)=='T'){
                    ans++;
                    r++;
                    l++;
                }else {
                    r++;
                }
            }else{
                l++;
            }
        }
        out.println(n-ans*2);
    }
}

Measured memory_bytes: 26048
($w, $h, $n) = split(" ",<>);
@x1 = ();
@x2 = ();
@y3 = ();
@y4 = ();
for($i=0;$i<$n;$i++){
	($x, $y, $a) = split(" ",<>);
    if($a==1){
    	push @x1,$x;
    }elsif($a==2){
    	push @x2,$x;
    }elsif($a==3){
    	push @y3,$y;
    }else{
    	push @y4,$y;
    }
}

@x1 = sort {$b <=> $a} @x1;
@x2 = sort {$a <=> $b} @x2;
@y3 = sort {$b <=> $a} @y3;
@y4 = sort {$a <=> $b} @y4;
if(!@x1){$x1num=0}else{$x1num=$x1[0]};
if(!@x2){$x2num=$w}else{$x2num=$x2[0]};
if(!@y3){$y3num=0}else{$y3num=$y3[0]};
if(!@y4){$y4num=$h}else{$y4num=$y4[0]};
$tate = $x2num-$x1num;
$yoko = $y4num-$y3num;
if($tate <0 or $yoko<0){
	print 0;
} else {
	print $tate * $yoko;
}


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

int main() {
  int N, M;
  cin >> N >> M;
  
  // i番目の都市から出る道路の数
  vector<int> road_from_city(N);
  
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    
    road_from_city.at(a - 1)++;
    road_from_city.at(b - 1)++;
  }
  
  for (int i = 0; i < N; i++)
    cout << road_from_city.at(i) << endl;;
}

Measured memory_bytes: 256
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#include <iostream>
#include <stack>
#include <vector>
#include <string>
#include <map>
#include <cmath>
#include <queue>
#include <random>
#include <chrono>
using namespace std;

typedef long long LL;

int digit[70], tot;

LL n;

const int mod = 1e9 + 7;

int dp[100][4];

int Dp(int i, int acc){
    if(i == tot + 1){
        return 1;
    }
    if(dp[i][acc] != -1){
        return dp[i][acc];
    }
    int now = acc * 2 + digit[i];
    long long ans = 0;
    for(int x = 0;x < 2;x++){
        for(int y = 0;y < 2;y++){
            if(y == 1 and x != 0)
                continue;
            if(x + 2 * y > now){
                continue;
            }
            int tmp = min(3, now - x - 2 * y);
            ans += Dp(i + 1, tmp);
        }
    }
    ans %= mod;
    return dp[i][acc] = ans;
}

int main(){
    cin >> n;
    while(n > 0){
        digit[++tot] = n & 1;
        n /= 2;
    } 
    reverse(digit + 1, digit + 1 + tot);
    memset(dp, -1, sizeof(dp)); 
    cout << Dp(1, 0) << endl;
    return 0;
}


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

int k;

int main(void){
    cin >> k;
    if(k == 2 || k == 5){
        cout << -1 << endl;
        return 0;
    }
    int r = 7;
    int i = 1;
    int maxc = 1e7;
    while(maxc--){
        if(r%k == 0){
            cout << i << endl;
            return 0;
        }
        r=10*r+7;
        r%=k;
        i++;
    }
    cout << -1 << endl;
    return 0;
}


Measured memory_bytes: 3628
//2020.1.16
//s1270188 xxxmk2
//alds1_09c

#include<stdio.h>
#define N 2000000

//prototype
void maxheap(int);


//global
int data[N+1], num=0;

int main(){
  int i;
  char cmd[10];

  while(1){
    scanf(" %s",cmd);

    if(cmd[0]=='i'){
      scanf("%d",&data[++num]);

      for(i=num/2;i>0;i/=2) maxheap(i);
    }
    
    else if(cmd[0]=='e'){
      if(cmd[1]=='n') break; 
      
      if(cmd[1]=='x'){
	printf("%d\n",data[1]);
	data[1]=data[num--];
	maxheap(1);
      }
    }
  }

  
  return 0;
}

void maxheap(int i){
  int l=i*2, r=i*2+1, max;
  
  if(l<=num && data[l]>data[i]) max=l;
  else max=i;
  if(r<=num && data[r]>data[max]) max=r;

  if(max!=i){
    l=data[i];
    data[i]=data[max];
    data[max]=l;

    maxheap(max);
  }
}



Measured memory_bytes: 5608
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

n = 10
h,w = myinput()
c = mylistinput(n)
a = mylistinput(h)

d = [[float("inf")]*n for i in range(n)] 
# d[u][v]: 辺uvのコスト(存在しないときはinf)

for i in range(n):
    for j in range(n):
        cost = c[i][j]
        d[i][j] = cost

#自身のところに行くコストは０
for i in range(n):
    d[i][i] = 0

# ワーシャルフロイド（warshall_floyd）法
# d[u][v]: 辺uvのコスト(存在しないときはinf)
def warshall_floyd(n,d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

d = warshall_floyd(n,d)
# pprint(d)

ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j]==-1:
            pass
        else:
            number = a[i][j]
            ans += d[number][1]
print(ans)

Measured memory_bytes: 40412
import sys

if sys.platform =='ios':
    sys.stdin=open('input_file.txt')
    
K,S=map(int,input().split())
cnt=0

for i in range(K+1):
	x=i
	for j in range(K+1):
		y=j
		if i+j<=S and i+j>=S-K:
			cnt+=1

print(cnt)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e13;

int N;
long long K;
vector<long long> A;
vector<long long> F;

long long Training(long long X){
    long long ret = 0;
    for (int i = 0; i < N; i++) {
        long long dis = max(0LL, A[i] * F[i] - X);
        ret += (dis + F[i] - 1) / F[i];
    }
    return ret;
}

long long Binary_Search(long long ok, long long ng){
    while (abs(ok - ng) > 1) {
        long long mid = (ok + ng) / 2;
        if (Training(mid) > K) {
            ng = mid;
        } else {
            ok = mid;
        }
    }
    return ok;
}

int main(){
    cin >> N >> K;
    A.resize(N); F.resize(N);
    for (auto& a : A) cin >> a;
    for (auto& f : F) cin >> f;
    sort(A.begin(), A.end(), greater<long long>());
    sort(F.begin(), F.end());
    
    long long ans = Binary_Search(INF, -1LL);
    cout << ans << endl;
    return 0;
}

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

#define MP make_pair
#define PB push_back
#define ALL(x)      (x).begin(),(x).end()
#define REP(i,n)    for(int i=0;i<(n);i++)
#define REP1(i,n)   for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n)   for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))
 
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI > VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;
 
const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;
 
const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};


void solve(long long N, std::vector<long long> X){
    VLL sortX(ALL(X));
    sort(ALL(sortX));
    REP(i, N) {
        if(X[i] < sortX[N/2]) {
            cout << sortX[N/2] << endl;
        } else {
            cout << sortX[N/2-1] << endl;
        }
    }
}

int main(){
    long long N;
    scanf("%lld",&N);
    std::vector<long long> X(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&X[i]);
    }
    solve(N, std::move(X));
    return 0;
}


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

long lb(unsigned long a){
    long ret = 0;
    for(long s=32; s>0; s>>=1){
        if(a>>s){
            a >>= s;
            ret += s;
        }
    }
    return ret;
}

int main(void){
    long n;
    cin >> n;
    vector<long> v(n);
    for(long i=0; i<n; i++){
        cin >> v[i];
    }
    sort(v.begin(), v.end(), greater<long>());
    multiset<long,greater<long>> s(v.begin(), v.end());
    long cnt = 0;
    while(!s.empty()){
        const auto ix = s.begin();
        const auto y = (1l << lb(*ix<<1))-*ix;
        s.erase(ix);
        const auto iy = s.find(y);
        if(iy!=s.end()){
            s.erase(iy);
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}


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

typedef struct {
	int fi;
	int en;
	int p;
}vector;

int main(){
	int N,K,i,cnt=0,check,max=0,flag=0,ent;
	char ss[100001];
	scanf("%d",&N);
	scanf("%d",&K);
	scanf("%s",ss);

	check=ss[0]-'0';

	vector x[100001];

	x[cnt].fi=0;
	x[cnt].p=ss[0]-'0';
	for(i=0;i<N;i++){
		if(ss[i]-'0'!=check){
			x[cnt++].en=i;
			x[cnt].fi=i;
			x[cnt].p=ss[i]-'0';
		}
		check=ss[i]-'0';
	}
	x[cnt].en=N;

	switch((ss[0]-'0')%2){
	case 0:
		if(cnt/2<K){
			printf("%d",N);
			return 0;
		}
	break;
	case 1:
		if(cnt<=K*2){
			printf("%d",N);
			return 0;
		}

	break;
	}

	i=0;
	while(flag==0){
		switch(x[i].p){
		case 0:
			ent=i+K*2-1;
			if(ent>cnt)ent=cnt;
			if(max<x[ent].en-x[i].fi)max=x[ent].en-x[i].fi;
		break;
		case 1:
			ent=i+K*2;
			if(ent>cnt)ent=cnt;
			if(max<x[ent].en-x[i].fi)max=x[ent].en-x[i].fi;
			if(i+K*2>=cnt)flag=1;
		break;
		}
		i++;
	}

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

Measured memory_bytes: 1408
n_x_y = list(map(int, input().split()))

n = n_x_y[0]
x = n_x_y[1]
y = n_x_y[2]

def search_min(i, j):
  #候補1
  opt_1 = abs(i-j)
  #候補2
  opt_2 = abs(x-i) + 1 + abs(y-j)
  #候補3
  opt_3 = abs(y-i) + 1 + abs(x-j)
  
  return min(opt_1, opt_2, opt_3)


answer = [0]*(n-1)
for i in range(1, n):
  for j in range(i + 1, n+1):
    answer[search_min(i, j)-1] += 1
    
for i in range(len(answer)):
  print(answer[i])

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

namespace CSharpSample01
{
    
    class Vector2
    {
        public double x;
        public double y;

        public Vector2() { }
        public Vector2(double x, double y)
        {
            this.x = x;
            this.y = y;
        }

    }

    class Program
    {

        
        static void Main(string[] args)
        {
            double[] data = Console.ReadLine().Split(' ').Select(x => double.Parse(x)).ToArray();

            Vector2 p1 = new Vector2(data[0], data[1]);
            Vector2 p2 = new Vector2(data[2], data[3]);
            Vector2 ground = new Vector2(data[2] - data[0], data[3] - data[1]);

            int q = int.Parse(Console.ReadLine());

            for(int i = 0; i < q; i++)
            {
                string[] input = Console.ReadLine().Split(' ');
                Vector2 p = new Vector2(double.Parse(input[0]), double.Parse(input[1]));

                Vector2 hypo = new Vector2(p.x - p1.x, p.y - p1.y);


                Vector2 shadow = new Vector2
                {
                    x = p1.x + ground.x * (hypo.x * ground.x + hypo.y * ground.y) / (ground.x * ground.x + ground.y * ground.y),
                    y = p1.y + ground.y * (hypo.x * ground.x + hypo.y * ground.y) / (ground.x * ground.x + ground.y * ground.y)
                };

                Vector2 ps = new Vector2(shadow.x - p.x, shadow.y - p.y);

                Vector2 ans = new Vector2(p.x + ps.x * 2, p.y + ps.y * 2);

                Console.WriteLine($"{ans.x:f10} {ans.y:f10}");

            }



        }
    }
}



Measured memory_bytes: 20440
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fi first
#define sc second
#define ALL(x) x.begin(), x.end()
#define RALL(X) x.begin(), x.end()
#define FOR(i, n, k) for(i=0; i<n; i+=k)
#define FO(i, n, k) for(i=1; i<=n; i+=k)
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define N 100005
#define mid ((l+r)/2)
#define dbg(x) (cerr << #x << " : " << x << endl)
#define endl "\n"
#define MOD 100000009

using namespace std;

typedef long long int lli;

const int NMAX = 10005;
string dp[NMAX];

void max_self(string &a, string b){
	if(a.size() < b.size()) a = b;	
	else a = max(a, b);
}

int main(){
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;	
	vector <int> ar(m);
	int mp[10] = {0,2,5,5,4,5,6,3,7,6};

	for(int i=0; i<NMAX; i++) dp[i] = "";
	for(int &x: ar){
		cin >> x;
		dp[mp[x]] = '0' + x;
	}
	
	for(int i=0; i<n; i++){
		if(dp[i] != ""){
			for(int a: ar){
				if(i + mp[a] >= NMAX) break;
				max_self(dp[i + mp[a]], dp[i] + (char)((int)'0' + a));
 				max_self(dp[i + mp[a]], (char)((int)'0' + a) + dp[i]);
			}
		}	
	}

	assert(dp[n] != "");
	cout << dp[n];
	return 0;
}

// g++ -std=c++17 -Wshadow -Wall a.cpp -fsanitize=address -fsanitize=undefined -D_GLIBCXX_DEBUG -g

Measured memory_bytes: 40064
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = (int)(n); i >= 0; i--)
#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

ll N, K, T, W, H, M, C;

const int MAX = 5100000;
const int MOD = 1e9 + 7;

const double PI=3.14159265358979323846;


long long fac[MAX], finv[MAX], inv[MAX];

vector<double> cx, cy, c;
 ll MM = 1e12;

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;
    }
}

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;
}

std::vector<int> Eratosthenes(int n ){
    std::vector<bool> is_prime( n + 1 );
    for( int i = 0; i <= n; i++ ) is_prime[ i ] = true;
    std::vector<int> P;
    for( int i = 2; i <= n; i++ ){
        if( is_prime[ i ] ){
            for( int j = 2 * i; j <= n; j += i ){
                is_prime[ j ] = false;
            }
            P.emplace_back( i );
        }
    }
    return P;
}

ll gcd(ll a, ll b){
    if(a < b) swap(a, b);
    if(b == 0) return a;
    if(a%b == 0) return b;
    else return gcd(b, a%b);
}

ll lcm(ll a, ll b)
{
   return a * b / gcd(a, b);
}



int main(){
    string str;
    cin >> str;
    int n = str.size();
    bool flag = true;
    if(str.size() %2 == 0) flag = false;
    string sub = str.substr(n/2 + 1, n/2);
    //cout << sub << "\n";
    for(int i = 0; i < n/2 ; ++i){
        if(str[i] == str[n-i-1]) continue;
        flag = false;
    }
    //cout << flag << "\n";
    for(int i = 0; i < n/4; ++i){
        if(sub[i] == sub[n/2-i-1] and str[i] == str[n/2-i-1]) continue;
        flag = false;  
    }
    if(flag) cout << "Yes";
    else cout << "No";
     return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
//using Graph = vector<vector<edge>>;
using dou =long double;
string yes="yes";
string Yes="Yes";
string YES="YES";
string no="no";
string No="No";
string NO="NO";

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

#define rep(i, n)         for(int i = 0; i < (int)(n); i++)
#define brep(n)           for(int bit=0;bit<(1<<n);bit++)
#define erep(i,container) for (auto i : container)
#define irep(i, n)        for(int i = n-1; i >= (int)0; i--)
#define rrep(i,m,n) for(ll i = m; i < (ll)(n); i++)
#define reprep(i,j,h,w) rep(i,h)rep(j,w)
#define all(x) (x).begin(),(x).end()
#define VEC(type,name,n) std::vector<type> name(n);rep(i,n)std::cin >> name[i];
#define pb push_back
#define pf push_front
#define query int qq;std::cin >> qq;rep(qqq,qq)
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define itn int
#define mp make_pair
#define sum(a) accumulate(all(a),0ll)
#define keta fixed<<setprecision
//#define vvector(name,typ,m,n,a)vector<vector<typ> > name(m,vector<typ> (n,a))
#define vvector(name,typ,m,n)vector<vector<typ> > name(m,vector<typ> (n))
#define vvvector(name,t,l,m,n,a) vector<vector<vector<t> > > name(l, vector<vector<t> >(m, vector<t>(n,a)));
#define vvvvector(name,t,k,l,m,n,a) vector<vector<vector<vector<t> > > > name(k,vector<vector<vector<t> > >(l, vector<vector<t> >(m, vector<t>(n,a)) ));
#define case std::cout <<"Case #" <<qqq+1<<": "
#define res resize
#define as assign
#define ffor for(;;)
#define ppri(a,b) std::cout << a<<" "<<b << std::endl
#define pppri(a,b,c) std::cout << a<<" "<<b <<" "<< c<<std::endl
#define aall(x,n) (x).begin(),(x).begin()+(n)
#define ssum(a) accumulate(a,0ll) 

typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
//typedef long long T;
ll ceil(ll a,ll b){
    return ((a+b-1)/b);
}
const int INF = 1000000000;
const ll INF64 = 9223372036854775807ll;
const ll MOD = 1000000007ll;
const dou pi=3.141592653589793;
//mapは、if関数などで覗いただけで構成されるので注意しよう！
//std::vector<vector<int>> g;


//std::vector<std::set<int>> g;

int main(){
    string s,t;
    std::cin >> s>>t;
    sort(all(s));
    sort(all(t),greater<char>());
    if(s<t)std::cout << Yes << std::endl;
    else std::cout << No << std::endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const int inf=1e9;
const int mod=1e9+7;
typedef long long ll;
typedef vector<int> vi;
typedef string::const_iterator State;
map<string,bool> mp;
string board[15];
int T;
ll gcd(ll a,ll b)
{
  if(b>a) swap(a,b);
  if(a%b==0) return b;
  else return gcd(b,a%b);
}
int main(int argc,char const* argv[])
{
  int T;
  cin >> T;
  for(int i=0;i<T;i++)
    {
      ll a,b;
      cin >> a >> b;
      if(a==b) cout << 1 << ' ' << 0 << endl;
      else
	{
	  ll GCD=gcd(a,b);
	  if(GCD==1)
	    {
	      if(a%2==0 || b%2==0)
		{
		  cout << 1 << ' ' << 1 << endl;
		}
	      else
		{
		  ll lnum=a*b/2;
		  cout << lnum+1 << ' ' << lnum << endl;
		}
	    }
	  else
	    {
	      a/=GCD;
	      b/=GCD;
	      if(a>=b)
		{
		  swap(a,b);
		}
	      if(a==1)
		{
		  if(b%2==0)
		    {
		      cout << 1 << ' ' << 1 << endl;
		    }
		  else
		    {
		      cout << (b/2)+1 << ' ' << (b/2) << endl;
		    }
		}
	      else
		{
        
		  ll lnum=a*b/2;
		  cout << lnum+1 << ' ' << lnum << endl;
		
		}
	    }
	}
    }
  return 0;
}



Measured memory_bytes: 3088
import sys
import numpy as np
bingo = []
for _ in range(3):
    bingo.append(list(map(int,input().split())))

cl = np.array([[0,0,0],[0,0,0],[0,0,0]])

n = int(input())
st = set()
for _ in range(n):
    st.add(int(input()))

for _ in range(len(st)):
    for i in range(3):
        for j in range(3):
            if bingo[i][j] in st:
                cl[i,j] = 1

if sum(cl[0]) == 3 or sum(cl[1]) == 3 or sum(cl[2]) == 3:
    print('Yes')
elif sum(cl[:,0]) == 3 or sum(cl[:,1]) == 3 or sum(cl[:,2]) == 3:
    print('Yes')
elif cl[0,0]+cl[1,1]+cl[2,2] == 3 or cl[0,2]+cl[1,1]+cl[2,0] == 3:
    print('Yes')
else:
    print('No')

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

#define ll long long
#define INF 99999999
#define INF_LL 1LL << 60
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define REP(i, a, n) for(int i = a; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

void put_double(double obj){printf("%.12f\n",obj);};

template < typename T > std::string to_string( const T& n )
{
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
}

int main()
{
    string n;
    cin >> n;
    
    rep(i,n.size())
    {
        if(n[i] == '9') cout << 1;
        else if(n[i] == '1') cout << 9;
        else cout << n[i];
    }
    cout << endl;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

struct point{
  double x,y;
};
struct rect{
  point p1,p2;
};

bool IsIntersect(const rect &A,const rect &B){
  return (A.p1.x<=B.p2.x&&B.p1.x<=A.p2.x)&&
         (A.p1.y<=B.p2.y&&B.p1.y<=A.p2.y);
}
int main(){
  rect A,B;
  while(cin>>A.p1.x>>A.p1.y>>A.p2.x>>A.p2.y
           >>B.p1.x>>B.p1.y>>B.p2.x>>B.p2.y){
    if(IsIntersect(A,B)){
      cout<<"YES"<<endl;
    }else{
      cout<<"NO"<<endl;
    }
  }
}

Measured memory_bytes: 1224
#pragma region header
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <math.h>
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rev(i, n) for(int i = (int)(n - 1); i >= 0; i--)
#define rev1(i, n) for(int i = (int)(n); i > 0; i--)
#define pb push_back
#define ts to_string
#define all(v) (v).begin(), (v).end()
#define vi vector<int>
#define vvi vector<vector<int>>
#define vc vector<char>
#define vvc vector<vector<char>>
#define vs vector <string>
#define vvs vector <vector<string>>
#define pq  priority_queue<int>
using ll = long long;
/* ----------------よく使う数字や配列----------------- */
int dx[] = { 1,0,-1,0 };
int dy[] = { 0,1,0,-1 };
const int INF = 2000000000;
constexpr ll mod = 1e9 + 7;
constexpr long double pi = 3.141592653589793238462643383279;
/* ----------------------end----------------------- */
/* --------------------ライブラリ-------------------- */
ll fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i % mod;
}
ll gcd(ll a, ll b) {        //最大公約数
    if (b == 0) return a;
    return gcd(b, a % b);
}
ll lcm(ll a, ll b) {      //最小公倍数
    return a * b / gcd(a, b);
}
bool isprime(ll a)//素数判定、primeならtrue,違うならfalse
{
    if (a < 2) return false;
    else if (a == 2) return true;
    else if (a % 2 == 0) return false;
    double m = sqrt(a);
    for (int i = 3; i <= m; i += 2)
    {
        if (a % i == 0)
        {
            return false;
        }
    }
    // 素数である
    return true;
}
ll ketasum(ll n) {    //各桁の和
    ll sum = 0;
    while (n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
ll kind(vi SYURUI) {//vector<int>型の配列の要素の種類数
    int size = SYURUI.size();
    sort(all(SYURUI));
    int cnt = 1;
    rep(i, size-1) {
        if (SYURUI[i] != SYURUI[i + 1])cnt++;
    }
    return cnt;
}
/* ----------------------end----------------------- */
#pragma endregion
signed main() {
    int N, A, B; cin >> N >> A >> B;
    int G = A + B - N;
    G = max(G , 0LL);
    cout << min(A, B) << " " << G << endl;
}






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

int v[101], weight[101], dp[101][10001];

int main()
{
    int n, w;
    cin >> n >> w;
    for (int i = 0; i < n; ++i) cin >> v[i] >> weight[i];
    for (int i = n - 1; i >= 0; --i)
    {
        for (int j = 0; j <= w; ++j)
        {
            if (j < weight[i])dp[i][j] = dp[i + 1][j];
            else dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - weight[i]] + v[i]);
        }
    }
    cout << dp[0][w] << endl;
    return 0;
}


Measured memory_bytes: 7004
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		while (s.hasNextInt()) {
			int n = s.nextInt();
			int x = s.nextInt();
			int c = 0;
			if (n == 0 && x == 0) return;

			for (int i = 1; i <= n; ++i) {
				for (int j = i + 1; j <= n; ++j) {
					for (int k = j + 1; k <= n; ++k) {
						int sum = i + j + k;
						if (sum == x) {
							c++;
						} else if (sum > x) {
							break;
						}
					}
				}
			}
			System.out.println(c);
		}
	}
}

Measured memory_bytes: 20192
import sys
input = sys.stdin.readline

N, T = map(int, input().split())
x = 0
f_t = 0

for t in list(map(int, input().split())):
    if t >= f_t:
        x += T
    else:
        x += (t + T - f_t)
    f_t = t + T
    
print(x)

Measured memory_bytes: 25744
#include "iostream"
#include<cstring>
using namespace std;
int snooke[10000];
int main()
{
    int n,k;
    cin>>n>>k;
    memset(snooke, 0, sizeof(snooke));
    for(int i=1;i<=k;i++)
    {
        int j;
        cin>>j;
        
        for(int lol=1;lol<=j;lol++)
        {
            int f;
            cin>>f;
            snooke[f]=1;
            
        }
        
        
    }
    
    int count=0;
    for(int i=1;i<=n;i++)
    {
        if(snooke[i]==0) count++;
        
    }
    
    cout<<count<<endl;
    
}


Measured memory_bytes: 3680
from __future__ import division, print_function

''' Hey stalker :) '''
INF = 10 ** 10
TEST_CASES = False


def main():
    a,b,m = get_list()
    ref = get_list()
    micro = get_list()
    res = min(ref) + min(micro)
    for _ in range(m):
        i,j,dis = get_list()
        res = min(res, ref[i-1]+micro[j-1]-dis)
    print(res)

''' FastIO Footer by @c1729 and other contributors '''
import os
import sys
from bisect import bisect_left, bisect_right
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
# else:
#     sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")
get_int = lambda: int(input())
get_list = lambda: list(map(int, input().split()))
if __name__ == "__main__":
    if TEST_CASES:
        [main() for _ in range(int(input()))]
    else:
        main()


Measured memory_bytes: 58252
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define repp(i,m,n) for(int (i)=(m);(i)<(n);(i)++)
#define repm(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define INF (1ll<<60)
typedef long long lint;
const lint MOD =1000000007;
const lint MAX = 10000000;

 
lint fac[MAX], finv[MAX], inv[MAX];

void COMinit() // 二項係数を求める時は前処理としてCOMinit()をする
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (lint 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;
    }
}
 
// 二項係数計算
long long COM(lint n, lint k)
{
    if (n < k)
        return 0;
    if (n < 0 || k < 0)
        return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

lint primary(lint num)
{
    if (num < 2) return 0;
    else if (num == 2) return 1;
    else if (num % 2 == 0) return 0; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return 0;
        }
    }

    // 素数である
    return 1;
}

   

int main(){
    lint N,M,K;
    cin>>N>>M>>K;
    rep(i,N+1){
        repm(j,M+1){
                if(((N-i)*(M-j)+i*j)==K){
                        cout<<"Yes";
                        return 0;
                }
        }
    }
    cout<<"No";
}

Measured memory_bytes: 256
fn read_line() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim_right().to_owned()
}

fn to_vec(s: String, offset: u64) -> Vec<u64> {
    s.split_whitespace()
        .map(|s| s.parse::<u64>().unwrap() - offset)
        .collect()
}

fn main() {
    read_line();
    let v = to_vec(read_line(), 0);

    let mid: u64 = v.windows(2).map(|w| std::cmp::min(w[0], w[1])).sum();

    println!("{}", v[0] + mid + *v.last().unwrap());
}


Measured memory_bytes: 4352
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>
#include <numeric>
#include <cctype>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>


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; }

constexpr long long INF = 1LL << 60;
constexpr int inf = 1000000007;
//constexpr long long mod = 1000000007LL;
constexpr long long mod = 998244353LL;

using namespace std;
typedef long long ll;

int dh[] = { 1,0,-1,0 };
int dw[] = { 0,1,0,-1 };

struct P {
	ll cost;
	int idx;
	P(ll cost, int idx) :cost(cost), idx(idx) {}
	bool operator <(const P &p) const {
		return cost > p.cost;
	}
};
vector<ll> dijkstra(int start, vector<vector<pair<int, ll>>>& graph) {
	vector<ll> dist(graph.size(), INF); dist[start] = 0;
	priority_queue<P> pq; pq.emplace(0, start);
	while (!pq.empty()) {
		ll cost = pq.top().cost; int idx = pq.top().idx; pq.pop();
		if (dist[idx] < cost) continue;
		for (auto next : graph[idx]) if (chmin(dist[next.first], cost + next.second)) pq.emplace(dist[next.first], next.first);
	}
	return dist;
}


int main()
{

	cin.tie(nullptr);
	ios::sync_with_stdio(false);


	int H, W; cin >> H >> W;
	int sh, sw; cin >> sh >> sw; sh--; sw--;
	int th, tw; cin >> th >> tw; th--; tw--;
	vector<string> vs(H); for (int i = 0; i < H; i++) cin >> vs[i];
	vector<vector<pair<int, ll>>> g(H * W);
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (vs[i][j] == '#') continue;
			for (int k = 0; k < 4; k++) {
				int nh = i + dh[k];
				int nw = j + dw[k];
				if (nh < 0 or nh >= H or nw < 0 or nw >= W) continue;
				if (vs[nh][nw] == '#') continue;
				g[i * W + j].emplace_back(nh * W + nw, 0);
			}
			for (int k = -2; k <= 2; k++) {
				for (int l = -2; l <= 2; l++) {
					int nh = i + k;
					int nw = j + l;
					if (nh < 0 or nh >= H or nw < 0 or nw >= W) continue;
					if (vs[nh][nw] == '#') continue;
					g[i * W + j].emplace_back(nh * W + nw, 1);
				}
			}
		}
	}
	auto d = dijkstra(sh * W + sw, g);
	ll res = d[th * W + tw];
	if (res == INF) res = -1;
	cout << res << endl;
}


Measured memory_bytes: 205936
#include <bits/stdc++.h>
using namespace std;
using lint = long long;

signed main(){
  lint N; cin >> N;
  vector<lint> b(N);
  for(lint i = 0; i < N; i++) cin >> b[i];
  vector<lint> a;
  for (lint i = 0; i < N; i++) {
    for (lint j = b.size() - 1; j >= 0; j--) {
      if (j + 1 == b[j]) {
        a.push_back(j + 1);
        b.erase(b.begin() + j);
        break;
      }
    }
  }
  if(a.size() != N) cout << -1 << endl;
  else{
    for(lint i = N - 1; i >= 0; i--) cout << a[i] << " ";
    cout << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int N, T, A;
  int ans = 1;
  cin >> N >> T >> A;
  
  vector<int> a(N);
  for(int i = 1; i <= N; i++) cin >> a[i];
  
  int min = 1 << 30;
  for(int i = 1; i <= N; i++){
    int dif = 1000 * A - (T * 1000 - a[i] * 6);
    if(dif < 0) {
      dif = - dif;
    }
    if(min > dif){
      min = dif;
        ans = i;
    } 
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
S = input()
K = int(input())
cost = [(ord("z") - ord(s) + 1) % 26 for s in S]
A = [chr(ord("a") + i) for i in range(26)]

ans = ""
for i in range(len(S)-1):
    if cost[i] <= K:
        K -= cost[i]
        ans += "a"
    else:
        ans += S[i]

ans += A[(A.index(S[-1]) + K) % 26]
print(ans)


Measured memory_bytes: 4212
#include"bits/stdc++.h"
using namespace std;
#define ll long long


int main() {
    int n;
	cin >> n;
	ll ans = 0;
	ll no = 0;
	vector<ll> v(n);
	for (int i = 0; i < n; i++) {
		cin >> v[i];
		if (i > 0) {
			if (v[i] > v[i - 1]) {
				ans = max(ans, no);
				no = 0;
			}
			else {
				no++;
			}
		}
	}
	ans = max(ans, no);
	cout << ans << endl;

	return 0;
}



Measured memory_bytes: 1024
#include <iostream>

int main() {
	std::string p, s;
	std::cin >> p >> s;

	p = p + p;
	if(p.find(s) != std::string::npos){
		std::cout << "Yes" << std::endl;
	}
	else{
		std::cout << "No" << std::endl;
	}
}

Measured memory_bytes: 3224
#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 PI  3.14159265358979323846
#define lp(i,n) for(int i = 0; i <n;i++)
#define range1(i,a,b,c) for(int i = int(a);i <= int(b);i+=int(c))
#define range(i,a,b) for(int i = int(a);i <= int(b);i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define MP make_pair
#define fr first
#define sc second
#define sz(v) ((int)((v).size()))
#define sfi1(v) scanf("%d",&v)
#define sfi2(v1, v2) scanf("%d %d",&v1,&v2)
#define sfi3(v1, v2, v3) scanf("%d %d %d",&v1,&v2,&v3)
#define sfll1(v) scanf("%I64d",&v);
#define sfll2(v1, v2) scanf("%I64d %I64d",&v1,&v2)
#define sfll3(v1, v2, v3) scanf("%I64d %I64d %I64d",&v1,&v2,&v3)
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<pair<int, int> > vii;
typedef pair<int, int> pii;
template<class T> using ordered_set=tree<T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update>;
const ll MOD = 1e9 + 7;
const int OO = (int)1e6;
const int N = (int)3005;
int dx[] = {0,0,-1,1};
int dy[] = {1,-1,0,0};
void init(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
int dp[N][N];
int main() {
	#   ifdef LOCAL_PROJECT
        freopen("in.txt", "r", stdin);
    #   endif
    
    string s1,s2;
    cin>>s1>>s2;
    int n=sz(s1),m=sz(s2);
    for(int i=0;i<=n;i++){
        for(int j=0;j<=m;j++){
            if(j==0||i==0){
                dp[i][j]=0;
                continue;
            }else if(s1[i-1]==s2[j-1]){
                dp[i][j]=dp[i-1][j-1]+1;
            }else {
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    string ans;
    for(int i=n,j=m;i>0&&j>0;){
       if(s1[i-1]==s2[j-1]){
           ans+=s1[i-1];
           i--,j--;
           continue;
       }
       if(dp[i-1][j]>dp[i][j-1])i--;
       else j--;
    }
    // printf("%d",dp[n][m]);
    reverse(all(ans));
    printf("%s",ans.c_str());
    return 0;
}

Measured memory_bytes: 38964
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) REP(i,0,n)
#define REP(i,s,e) for(int i=(s); i<(int)(e); i++)
#define repr(i, n) REPR(i, n, 0)
#define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--)
#define pb push_back
#define all(r) r.begin(),r.end()
#define rall(r) r.rbegin(),r.rend()
#define fi first
#define se second

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll INF = 1e18;
const ll MOD = 1e9 + 7;
const double EPS = 1e-8;

template<typename T> T chmax(T& a, const T& b){return a = (a > b ? a : b);}
template<typename T> T chmin(T& a, const T& b){return a = (a < b ? a : b);}

int main(){
    char c;
    cin >> c;
    if(c >= 'A' && c <= 'Z') cout << "A" << '\n';
    else cout << "a" << '\n'; 
    return 0;
}

Measured memory_bytes: 3632
sa=str(input())
sb=str(input())
sc=str(input())
sa=list(sa)
sb=list(sb)
sc=list(sc)
temp=sa[0]
del sa[0]
while True:
  if temp=="a":
    if len(sa)==0:
      print("A")
      break
    temp=sa[0]
    del sa[0]
  if temp=="b":
    if len(sb)==0:
      print("B")
      break
    temp=sb[0]
    del sb[0]
  if temp=="c":
    if len(sc)==0:
      print("C")
      break
    temp=sc[0]
    del sc[0]

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
#define ll long long 
int ctoi(char c) {return c-'0';}/*char to int*/
int gcd(ll a,ll b){return b?gcd(b,a%b):a;}/*MAX*/
int lcm(ll a,ll b){return a*b/gcd(a,b);}/*MIN*/
bool primecheck(ll n){/*sosuu*/if(n < 2) return false;else{for(int i = 2; i * i <= n; i++){if(n % i == 0) return false;}return true;}}
string  reverserange(string s,ll a,ll b){reverse(s.begin()+a-1,s.begin()+b); return s;}
int  main(){
 int n;
 cin >> n; 
 bool pp =true,qq=true; vector<int>p(n),q(n),a(n); int pi=-1,qi=-1,x=0;
 for(int i=0;i<n;i++){
     a.at(i)=i+1;
 }

 for(int i=0;i<n;i++){
     cin >> p.at(i);
     if(p.at(i)!=a.at(i))pp=false;
 }
  for(int i=0;i<n;i++){
     cin >> q.at(i);
     if(q.at(i)!=a.at(i))qq=false;
 }
    if(qq)qi=0;
    if(pp)pi=0;

 while(pi==-1||qi==-1){
    next_permutation(a.begin(), a.end());
    x++;
     pp =true,qq=true;
    for(int i=0;i<n;i++){
        if(a.at(i)!=p.at(i))pp=false;
        if(a.at(i)!=q.at(i))qq=false;
    }
if(pp)pi=x;
if(qq)qi=x;
 }
cout << abs(pi-qi)<<endl;
}







Measured memory_bytes: 256
fun main(arr:Array<String>) {
    val (n,l) = readLine()!!.split(" ").map { it.toInt() }
    val apples = (0 until n).map { it + l }
    val applePie = apples.sum()
    var ans = apples.map { applePie - it }.sortedBy { Math.abs(applePie - it) }
    println(ans[0])
}



Measured memory_bytes: 37860
n = int(input())
given_A = list(map(int, input().split()))
A = []
for kabuka in given_A:
    if len(A) > 0 and kabuka == A[-1]:
        continue
    else:
        A.append(kabuka)

# 株価が全て同じ時のコーナーケース
if len(A) == 1:
    print(1000)
    exit()

money = 1000
stock = 0
n = len(A)
for i in range(len(A)):
    if i == 0:
        if A[i] < A[i + 1]:
            stock = money // A[i]
            money = money % A[i]
    elif i == n - 1:        
        if A[i - 1] < A[i]:
            money += stock*A[i]
            stock = 0
    else:
        if (A[i - 1] < A[i]) & (A[i] > A[i + 1]):
            money += stock*A[i]
            stock = 0
        elif (A[i - 1] > A[i]) & (A[i] < A[i + 1]):
            stock = money // A[i]
            money = money % A[i]
print(money)
            




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

int n;
bool stat = false;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=9;i++){
		if(n % i == 0 && 1 <= n/i && n/i <= 9) stat = true;
	}
	if(stat) printf("Yes");
	else printf("No");
	return 0;
}


Measured memory_bytes: 256