akhauriyash/Code-Regression huggingface dataset:
// Template from https://techracho.bpsinc.jp/jhonda/2019_08_05/78537

// input macro for competive-programming from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };

    ($iter:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($next:expr, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, bytes) => {
        read_value!($iter, String).into_bytes()
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    use std::io::Read;
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();

    println!("{}", solve(&s));
}

macro_rules! test {
    ($($input:expr => $output:expr),* $(,)*) => {
        #[test]
        fn solve_test() {
            $(
                assert_eq!(solve($input), $output);
            )*
        }
    };
}

test! {
r#"8"# => r#"5"#,
//a={8,4,2,1,4,2,1,4,2,1,....} です。a5=a2なので、答えは5
r#"7"# => r#"18"#,
//a={7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1,4,2,1,.....} です。
r#"54"# => r#"114"#,
}

fn solve(src: &str) -> String {
    input! {
        source = src,
        s: isize,
    }

    let mut map = std::collections::HashMap::new();
    map.entry(s).or_insert(1);

    let mut ans = 0;

    let mut x = s;

    for i in 1..1000000 {
        x = if x % 2 == 0 { x / 2 } else { 3 * x + 1 };

        let count = map.entry(x).or_insert(0);
        *count += 1;
        if *count == 2 {
            ans = i + 1;
            break;
        }
    }

    ans.to_string()
}

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

int main() {
    int N;
    cin>>N;
    vector<long> A(N);
    vector<long> B(N);
    vector<long> C(N);
    for(int i=0;i<N;++i){
        cin>>A[i];
    }
    for(int i=0;i<N;++i){
        cin>>B[i];
    }
    for(int i=0;i<N;++i){
        cin>>C[i];
    }
    sort(A.begin(), A.end());
    sort(C.begin(), C.end());
    long ans = 0;
    long a, c;
    for(int i=0;i<N;++i){
        a = lower_bound(A.begin(), A.end(), B[i]) - A.begin();
        c = C.end() - upper_bound(C.begin(), C.end(), B[i]);
        ans += a*c;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
map <int,int> mp;
vector<int> V;
list<int> L;
stack<int> S;
queue<int> Q;
deque<int> dq;
#define INF (1<<30)
#define INFLL (1ll<<60)
#define EPS (1e-10)
static const int MAX=100000;
static const int NMAX=50;
static const int MMAX=50;
ll ans=1ll;
int main(){
    cin.tie(0);  ios::sync_with_stdio(false);
    
    int  N,M; cin>>N>>M;
    
    if(abs(N-M)>1){
        cout<<0<<"\n";
        return 0;
    }
    
    for(int i=1;i<=N;i++){
        ans=(ans*i)%((int)pow(10,9)+7);
    }
    for(int i=1;i<=M;i++){
        ans=(ans*i)%((int)pow(10,9)+7);
    }
    
    cout<<(N==M?(2*ans)%((int)pow(10,9)+7):ans)<<"\n";
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair <int, int> P;

void printVec(std::vector<int> &vec) {
  std::cout << "";
  for (auto it = vec.begin(); it != vec.end(); ++it) {
    std::cout << *it << " ";
  }
  std::cout << std::endl;
}

int main() {
  int a, b, c, d;

  cin >> a >> b >> c >> d;
  int x, y;
  x = c / b;
  if (c % b != 0) {
    x = x + 1;
  }
  y = a / d;
  if (a % d != 0) {
    y = y + 1;
  }
  if (x > y) {
    cout << "No" << endl;
  } else {
    cout << "Yes" << endl;
  }
	return 0;
}

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

#define rep(i, n)     for (int i = 0; i < n; ++i)
#define rep1(i, n)    for (int i = 1; i < n + 1; ++i)
#define repN(i, m, n) for (int i = m; i < n; ++i)
#define repR(i, n)    for (int i = n - 1; i >= 0; --i)

using namespace std;

int main() {
	int n;
	long long count = 0;
	cin >> n;
	if (n < 3) {
		cout << 0;
		return 0;
	}
	vector<int> stick(n);
	rep(i, n) {
		int t;
		scanf("%d", &t);
		stick[i] = t;
	}

	sort(stick.begin(), stick.end());
	rep(i, n) {
		repN(j, i + 1, n) {
			if (stick[j] == stick[i]) {
				continue;
			}
			repN(k, j + 1, n) {
				if (stick[k] == stick[j] || stick[k] == stick[i]) {
					continue;
				}
				if (stick[i] + stick[j] > stick[k]) {
					++count;
				} else {
					break;
				}
			}
		}
	}

	cout << count;

	return 0;
}


Measured memory_bytes: 3704
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
const int N = 2e7+5;
ll a[N];
void solve(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    int ans = 1;
    for(int i=1;i<n;i++){
        if(s[i]!=s[i-1])ans++;
    }
    cout<<ans<<endl;
}
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t = 1;
//    cin>>t;
    while(t--)solve();
    return 0;
}


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

int main(void) {
	int a, b,i, sum = 0;
	cin >> a >> b;
	if (3 <= a, b <= 20) {
		for (i = 0; i < 2; i++) {
			if (a > b) {
				sum = sum + a;
				a--;
			}
			else {
				sum = sum + b;
				b--;
			}
		}
		cout << sum;
	}
	else
		cout << "0";
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{   long long n,m,x,y;
  double s;
	while(~scanf("%lld%lld%lld%lld",&n,&m,&x,&y))
	{    s=n*m/2.0; 
        if(n%2==0&&m%2==0&&n/2==x&&m/2==y)
        {
		printf("%.6lf 1\n",s);
		                      
        }
        else
        {
        	printf("%.6lf 0\n",s);
		
		}
		
	} 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

using boost::multiprecision::cpp_int;
using namespace std;

#if __has_include("print.hpp")
  #include "print.hpp"
#endif

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define MOD 1000000007

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

// DPテーブル
const int MAX_N = 10100;
const int MAX_W = 10100;
int dp[MAX_N][MAX_W]; // 12 種類だが余裕をもつ

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  int h, n;
  cin >> h >> n;
  vector<int> a(n), b(n);
  rep(i, n){
    cin >> a[i] >> b[i];
  }

  for (int i = 0; i < MAX_N; ++i) for (int w = 0; w < MAX_W; ++w) dp[i][w] = INT_MAX / 2;
  dp[0][0] = 0;

  for (int i = 0; i < n; i++) {
    for (int j = 0; j <= h; j++) {
      dp[i+1][j] = min(dp[i][j], dp[i+1][j]);
      dp[i+1][min(j+a[i], h)] = min(dp[i+1][j]+b[i], dp[i+1][min(j+a[i], h)]);
    }
  }

  cout << dp[n][h] << endl;
}


Measured memory_bytes: 398848
#include <bits/stdc++.h>
using namespace std;
#define Hello ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define endl '\n'
#define F first
#define S second
int main()
{
    Hello
    int n;
    ll ans = 0;
    cin >> n;
    int a[n + 5], b[n + 5];
    for(int i = 0; i <= n; i++)
        cin >> a[i];
    for(int i = 0; i < n; i++)
        cin >> b[i];
    for(int i = 0; i < n; i++)
    {
        int temp = min(a[i], b[i]);
        a[i] -= temp;
        b[i] -= temp;
        ans += temp;

        if(b[i])
        {
            temp = min(b[i], a[i + 1]);
            a[i + 1] -= temp;
            ans += temp;
        }
    }
    cout << ans;
    return 0;
}


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

int n;
int query[205];
int ans[205];

int send_q(){
	printf("?");
	for(int i=0;i<n;i++){
		printf(" %d",query[i]);
	}
	printf("\n");
	fflush(stdout);
	string str;
	cin >> str;
	if(str=="Blue")return 1;
	return 0;
}

void send_a(){
	printf("! ");
	for(int i=0;i<n*2;i++){
		if(ans[i]==1){
			printf("B");
		}else{
			printf("R");
		}
	}
	printf("\n");
	fflush(stdout);
}

int send_q_bs(int f){
	for(int i=0;i<n;i++){
		query[i]=f+i+1;
	}
	return send_q();
}


int main(void){
	scanf("%d",&n);
	bool flag=false;
	int l=0,r=n;
	int lv=send_q_bs(l);
	int rv=send_q_bs(r);
	while(l+1<r){
		int mid=(l+r)/2;
		int mv=send_q_bs(mid);
		if(lv==mv && mv==rv){
			l=mid;
		}else if(lv==mv){
			l=mid;
		}else{
			r=mid;
		}
	}
	memset(ans,-1,sizeof(ans));
	int i=l;
	//printf("%d\n",i);
	for(int j=0;j<=i;j++){
		for(int k=0;k<n-1;k++){
			query[k]=i+k+2;
		}
		query[n-1]=j+1;
		ans[j]=send_q();
	}
	//send_a();
	for(int j=i+n;j<n*2;j++){
		for(int k=0;k<n-1;k++){
			query[k]=i+k+2;
		}
		query[n-1]=j+1;
		ans[j]=send_q();
	}
	//send_a();
	for(int j=i+n-1;j>=i+1;j--){
		int pos=0;
		for(int k=i+1;k<i+n;k++){
			if(j==k)continue;
			query[pos++]=k+1;
		}
		query[n-2]=i+1;
		query[n-1]=i+n+1;
		ans[j]=1-send_q();
	}
	send_a();
	return 0;
}


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N,H,W;

int R[101010],C[101010],A[101010];
int ok[201010];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<202020> uf;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>H>>W;
	vector<vector<int>> V;
	FOR(i,N) {
		cin>>R[i]>>C[i]>>A[i];
		R[i]--;
		C[i]--;
		V.push_back({A[i],R[i],C[i]});
	}
	FOR(i,H) ok[i]=1;
	FOR(i,W) ok[H+i]=1;
	
	sort(ALL(V));
	reverse(ALL(V));
	ll ret=0;
	FORR(v,V) {
		int y=v[1];
		int x=v[2];
		
		if(ok[uf[y]]&&ok[uf[H+x]]) {
			if(uf[y]==uf[H+x]) {
				ok[uf[y]]=0;
			}
			else {
				uf(y,H+x);
			}
			ret+=v[0];
		}
		else if(ok[uf[y]]) {
			ok[uf[y]]=0;
			ret+=v[0];
		}
		else if(ok[uf[H+x]]) {
			ok[uf[H+x]]=0;
			ret+=v[0];
		}
	}
	cout<<ret<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


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

int main(){
  int N;
  string S;
  cin >> N >> S;
  int Ans=0;
  for(int i=0; i<N-2; i++){
    if(S.at(i)=='A' && S.at(i+1)=='B' && S.at(i+2)=='C'){
      Ans++;
    }
  }
  cout << Ans << endl;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"strings"
)

func main() {
	var n string
	fmt.Scan(&n)

	arr := strings.Split(n, "")
	for i := 0; i < len(n); i++ {
		fmt.Print(solve(arr[i]))
	}
	fmt.Println("")
}

func solve(s string) string {
	if s == "1" {
		return "9"
	} else {
		return "1"
	}
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
int n,m,arr[105],sum;
bool valid(int x){
  if(x*4*m>=sum) return true;
  return false;
}
int main() {
  cin>>n>>m;
  for(int i=1;i<=n;i++){
    cin>>arr[i];
    sum+=arr[i];
  }
  sort(arr+1,arr+n+1);
  for(int i=n;i>=n-m+1;i--){
    if(!valid(arr[i])){
      cout<<"No"<<endl;
      return 0;
    } 
  }
  cout<<"Yes"<<endl;
}

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

#define pb push_back
#define eb emplace_back

typedef long long ll;
typedef unsigned long long ull;

using namespace std;





void one_case() {
    int n;
    cin >> n;
    int best = 50;
    while (n--) {
        int a;
        cin >> a;
        int cur = 0;
        while (a) {
            if (a % 2 == 0) {
                ++cur;
                a /= 2;
            }else {
                break;
            }
        }
        best = min(best, cur);
    }
    cout << best << "\n";


}


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


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

    return 0;
}


Measured memory_bytes: 256
import sys,collections as cl,bisect as bs , heapq as hq
sys.setrecursionlimit(100000)
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
n,m = m()

a = l()

de = []
su=0
for i in range(n):
    hq.heappush(de,-a[i])

for i in range(m):
    kkk = hq.heappop(de)
    kkk = -(-kkk//2)
    hq.heappush(de,kkk)
print(-1*sum(de))









Measured memory_bytes: 64792
#include <bits/stdc++.h>
      
#define FOR(i,a,b) for( ll i = (a); i < (ll)(b); i++ )
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort( (x).begin(),(x).end() )
#define REVERSE(x) reverse( (x).begin(),(x).end() )
#define UNIQUE(x) (x).erase( unique( ALL( (x) ) ) , (x).end() )
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())
#define SHOW(x) cout << #x << " = " << x << endl
#define SHOWA(x,n) for( int yui = 0; yui < n; yui++ ){ cout << x[yui] << " "; } cout << endl

#define pb emplace_back
#define fi first
#define se second

using namespace std;

typedef long double ld;
typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vpl> gr;
typedef vector<vl> ml;
typedef vector<vd> md;
typedef vector<vi> mi;
     
const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ld EPS = 1e-12;
const ll MOD = 1e9+7;
     
template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> inline T sq( T a ){ return a * a; }

ll in(){ long long int x; scanf( "%lld" , &x ); return x; }
char yuyushiki[1000010]; string stin(){ scanf( "%s" , yuyushiki ); return yuyushiki; }

// head

int n;

int a[200010];
int b[200010];

int main(){

  n = in();
  REP(i, n){
    a[i] = in();
    b[i] = a[i];
  }

  sort(b, b+n);

  REP(i, n){
    if(a[i] <= b[n/2-1]){
      printf("%d\n", b[n/2]);
    } else {
      printf("%d\n", b[n/2-1]);
    }
  }
  
  return 0;
}


Measured memory_bytes: 3712
#include<stdio.h>

int main()
{
	int a, b;
	scanf("%d %d", &a, &b);
	if (a + b == 15){
		printf("+");
	}
	else if (a*b == 15){
		printf("*");
	}
	else{
		printf("x");
	}
	return 0;
}

Measured memory_bytes: 128
// #define _GLIBCXX_DEBUG
#pragma GCC diagnostic ignored "-Wsign-compare"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < int(n); ++i)

using Bit = bitset<16>;

void solve() {
    int n, m;
    cin >> n >> m;

    vector<int> S[11];
    int P[11];

    rep(i, m) {
        int k;
        cin >> k;
        S[i].resize(k);
        rep(j, k) {
            cin >> S[i][j];
            --S[i][j];
        }
    }

    rep(i, m) cin >> P[i];

    auto count_on = [&](int switch_id, const Bit &bit) {
        const auto sw = S[switch_id];
        int cnt = 0;
        for (auto &idx : sw)
            if (bit[idx]) ++cnt;
        return cnt;
    };

    auto is_all = [&](const Bit &bit) {
        rep(i, m) {
            if (count_on(i, bit) % 2 != P[i]) return false;
        }
        return true;
    };

    int ans = 0;
    rep(b, 1 << n) {
        Bit bit(b);
        if (is_all(b)) ++ans;
    }
    cout << ans << "\n";
}
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}

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

int main() {
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  int x = A + B;
  int y = C + D;
  
  if (x > y) {
    cout << "Left" << endl;
  }
  
  else if (x == y) {
    cout << "Balanced" << endl;
  }

  else {
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define reps(i, a, n) for (int i = (a); i < (n); ++i)
#define rep(i, n) reps(i, 0, n)
#define deps(i, a, n) for (int i = (a); i >= (n); --i)
#define dep(i, n) deps(i, n, 0)
#define inf 2147483647
#define int long long

signed main(void)
{
	int x, k, d; cin >> x >> k >> d;
	double min, max;
	min = (double)x - (double)k * (double)d;
	max = (double)x + (double)k * (double)d;
	if (min == 0 || max == 0) {cout << 0 << endl; return 0;}
	if (min < 0 && max < 0) {cout << - x - k * d << endl; return 0;}
	if (min > 0 && max > 0) {cout << x - k * d << endl; return 0;}
	if (x < 0) x = -x;
	int tmp = x % d;
	if ((x / d) % 2 == k % 2) {cout << tmp << endl; return 0;}
	cout << d - tmp << endl;
}


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

int main(){
  int N;
  cin >> N;
  string S;
  map<string,int>M;
  
  ll ans = 0;
  
  rep(i,N){
    cin >> S;
    sort(S.begin(),S.end());
    if(M.count(S))M[S]++;
    else M[S] = 0;
    ans += M[S];
    
  }
  
  cout << ans << endl;
}

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

typedef long long ll;
const int MAXN = 3001;

int N, A[MAXN];
ll dp[MAXN][MAXN][2];

ll opt(int l, int r, int p) { // returns x-y with range(l, r)
    // printf("looking at %d-%d for player %d\n", l, r, p);
    if (~dp[l][r][p]) return (dp[l][r][p]);

    if (l==r) {
        if (p==0) return A[l];
        else return -A[l];
    }
    if (p==0) {
        ll back = opt(l+1, r, 1) + A[l];
        ll front = opt(l, r-1, 1) + A[r];
        return dp[l][r][p] = max(back, front);       
    } else {
        ll back = opt(l+1, r, 0) - A[l];
        ll front = opt(l, r-1, 0) - A[r];
        return dp[l][r][p] = min(back, front);
    }
}

int main() {
    cin>>N;
    for (int i=0;i<N;i++) cin>>A[i];
    memset(dp, -1, sizeof(dp));
    cout<<opt(0, N-1, 0)<<"\n";
}

Measured memory_bytes: 141184
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
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 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(a,i,j) a.resize(i);rep(ii,i)a[ii].resize(j); 
#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) 
#define gre(n) greater<n>()

typedef long long ll;
//
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
//typedef long long T;
const int INF = 1000000000;
const double dINF = 1000000000;
const ll INF64 = 922337203685477580ll;
const ll MOD = 1000000007ll;
//const ll MOD = 67280421310721ll;
const dou pi=3.141592653589793;
//メモ
//二次元配列のresizeのしかた
//vv.resize(n);
//for(size_t i=0; i<n; i++){
// vv[i].resize(n);
//}

//メモ
//負の辺を持つ最短経路問題では到達不可経路でも初期化値より小さくなりうるので注意しよう！
int main(){
    string s;
    std::cin >> s;
    if(s[2]==s[3]&&s[4]==s[5])std::cout << Yes << std::endl;
    else std::cout << No << std::endl;
}

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

typedef long long int ll;

int main()
{
    ll n, m;
    cin >> n >> m;
    vector<string> a(n), b(m);
    for(ll i = 0;i < n;i++){
        cin >> a[i];
    }
    for(ll i = 0;i < m;i++){
        cin >> b[i];
    }

    for(ll i = 0;i < n - m + 1;i++){
        for(ll j = 0;j < n - m + 1;j++){
            bool f = false;
            for(ll k = 0;k < m;k++){
                for(ll l = 0;l < m;l++){
                    if(a[i + k][j + l] != b[k][l]){
                        f = true;
                    }
                }
            }
            if(!f){
                cout << "Yes";

                return 0;
            }
        }
    }

    cout << "No";

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <utility>
#include <map>
#include <algorithm>
#include <queue>
#include <cmath>

using namespace std;

int main() {
	int n;
	cin >> n;
	vector < double > v(n);
	double ans=0;

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

	sort(v.begin(), v.end());
	// ans = (v[0]+v[1]) / 2;
	ans = v[0];
	for(int i=1; i<n; i++) {
		// ans += (1/a[i]);
		ans = (ans+v[i]) / 2;
		// ans = ans/2 + v[i]/2;
	}
	// cout << ans << endl;
	printf("%.5f\n", ans);

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#define int long long
using namespace std;

int q[4];
int n;

signed main()
{
	cin >> q[0] >> q[1] >> q[2] >> q[3];
	cin >> n;
	
	int cheap = min(q[0] * 8, min(q[1] * 4, min(q[2] * 2, q[3])));
	int ans = (n / 2) * cheap; n %= 2;
	
	if (n) {
		int a = q[0] * 4;
		int b = q[0] * 2 + q[1];
		int c = q[1] * 2;
		int d = q[2];
		ans += min(a, min(b, min(c, d)));
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

using namespace std;

int H, W, N;

int main(){
    cin >> H >> W >> N;

    if(H < W){
        std::swap(H, W);
    }

    int ans = N / H;
    if(0 < (N % H))
        ans++;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
n,m = map(int,input().split())
a = list()
for i in range(n):
    a.append(list(map(int,input().split())))
b = list()
for i in range(m):
    b.append(int(input()))
for i in range(n):
    ans = 0
    for j in range(m):
        ans += a[i][j]*b[j]
    print(ans)


Measured memory_bytes: 6008
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<n; i++)
#define INF 1000000
#define int long long
using namespace std;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
typedef pair<int,int> P;
signed main(){
    string s;
    cin >> s;
    int k;
    cin >> k;
    int pos = 0;
    while(1){
        if(pos == k-1) {
            cout << s[pos] << endl;
            return 0;
        }
        if(s[pos] != '1') {
            cout << s[pos] << endl;
            return 0;
        }
        pos++;
    }
    return 0;
}


Measured memory_bytes: 256
import java.io.*;
import java.io.ObjectInputStream.*;
import java.util.*;
import java.util.regex.*;


public class Main {

	final static long MOD = 1000000007;
	//final static long MOD = 998244353;

	public static String[] Ws = null;
	public static int wsIndx = 0;
	public static BufferedReader in = null;
	public static long cnt=0;
	public static PrintWriter pw = new PrintWriter(System.out);
	public static void main(String[] args) throws Exception {
		solutionA(args);
		if(in!=null){
			in.close();
		}
		pw.flush();
		pw.close();
	}

	public static void solutionA(String[] args) throws Exception{

		int Q = nextInt();

		boolean[] flg = sleveOferatosthenes(100001);
		int[] rui = new int[flg.length];
		int sum=0;
		for(int i=0;i<flg.length;i++) {
			if(flg[i]&&flg[(i+1)/2]) {
				sum++;
			}
			rui[i]=sum;
		}

		for(int i=0;i<Q;i++) {
			int[] q = nextInts();
			int ans = rui[q[1]]-rui[q[0]-1];

			pw.println(ans);
		}

	}

	public static boolean[] sleveOferatosthenes(int n) {
		boolean[] x = new boolean[n];
		Arrays.fill(x,true);
		x[0]=false;
		x[1]=false;
		int max=(int)Math.ceil(Math.sqrt(n)+0.1);
		for(int i=2;i<max;i+=2) {
			if(!x[i]) {
				continue;
			}
			for(int k=i*i;k<n;k+=i) {
				x[k]=false;
			}
			if(i==2) {
				i--;
			}
		}
		return x;
	}

	public static void check() throws Exception{
		if(in == null){
			in = new BufferedReader(new InputStreamReader(System.in));
		}
		if(Ws==null || Ws.length<=wsIndx){
			Ws = in.readLine().split(" ");
			wsIndx=0;
		}
	}
	public static int nextInt()throws Exception{
		check();
		return Integer.parseInt(Ws[wsIndx++]);
	}

	public static long nextLong()throws Exception{
		check();
		return Long.parseLong(Ws[wsIndx++]);
	}

	public static String nextString()throws Exception{
		check();
		return Ws[wsIndx++];
	}

	public static int[] nextInts()throws Exception{
		check();
		int[] tmp = new int[Ws.length];
		for(int i=0;i<tmp.length;i++){
			tmp[i]=Integer.parseInt(Ws[i]);
		}
		wsIndx=Ws.length;
		return tmp;
	}

	public static long[] nextLongs()throws Exception{
		check();
		long[] tmp = new long[Ws.length];
		for(int i=0;i<tmp.length;i++){
			tmp[i]=Long.parseLong(Ws[i]);
		}
		wsIndx=Ws.length;
		return tmp;
	}

	public static String[] nextStrings()throws Exception{
		check();
		wsIndx=Ws.length;
		return Ws;
	}


}



Measured memory_bytes: 46516
from io import StringIO
from collections import *
from functools import *
import sys


def main(inputs):
    # n = int(next(inputs))
    # n, k = map(int, next(inputs).split())
    # xs = list(map(int, next(inputs).split()))
    r, d, x = map(int, next(inputs).split())
    for i in range(10):
        x = r*x-d
        print(x)
        pass
    return


def gen_inputs(str_=None):
    inputs = StringIO(str_) if str_ else sys.stdin
    while True:
        a = inputs.readline().rstrip()
        yield a
        pass
    pass


if __name__ == "__main__":
    main(gen_inputs())
    pass


Measured memory_bytes: 3692
N = gets.to_i
s = Array.new(N)
for i in 0..(N-1)
  s[i] = gets.chomp.split("")
end
ab = Array.new(N).map{Array.new(3, 0)}
nAB = nBA = nA = nB = 0

for i in 0..(N-1)
  for j in 0..(s[i].size - 1)
    if j == 0 && s[i][j] == "B"
      ab[i][2] = 1
    elsif j == s[i].size - 1 && s[i][j] == "A"
      ab[i][1] = 1
    end
    if j < s[i].size - 1
      if s[i][j..(j+1)].join == "AB"
        ab[i][0] += 1
      end
    end
  end
  nAB += ab[i][0]
  if ab[i][1] == 1 && ab[i][2] == 1
    nBA += 1
  elsif ab[i][1] == 1
    nA += 1
  elsif ab[i][2] == 1
    nB += 1
  end
end

if nBA == 0
  puts nAB + [nA, nB].min
else
  if nA == 0 && nB == 0
    puts nAB + nBA - 1
  elsif nA == 0 || nB == 0
    puts nAB + nBA
  else
    puts nAB + nBA + 1 + [nA, nB].min - 1
  end
end

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

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

    long long ans = 0;
    if (p == 2 || p == 5) {
        for (int i = 0; i < n; i++) {
            if ((s[n-i-1] - '0') % p == 0) ans += n - i;
        }
    }
    else {
        long long val[p] = {};
        long long dig = 1;
        long long cur = 0;
        val[cur]++;
        for (int i = 0; i < n; i++) {
            cur = (cur + (s[n-i-1] - '0') * dig) % p;
            dig = dig * 10 % p;
            val[cur]++;
        }
        for (int i = 0; i < p; i++) ans += val[i] * (val[i] - 1) / 2;
    }
    cout << ans << endl;
}

Measured memory_bytes: 644
using System;


public class hello
{
    public static void Main()
    {
        var n = int.Parse(Console.ReadLine().Trim());
        var ary = new int[n];
        string[]  line = Console.ReadLine().Trim().Split(' ');
        for (int i = 0; i < n; i++) ary[i] = int.Parse(line[i]);
        var count = 0;
        var flag = 1;
        while ( flag == 1)
        {
            flag = 0;
            for (int i = n-1; i >=1; --i)
            {
                if (ary[i] < ary[i-1])
                {
                    count += 1;
                    var buf = ary[i - 1];
                    ary[i - 1] = ary[i];
                    ary[i] = buf;
                    flag = 1;
                }
            }
        }
        for (int i = 0; i < n; i++)
        {
            if (i == n - 1) Console.WriteLine(ary[i]);
            else Console.Write("{0} ", ary[i]);
        }
        Console.WriteLine(count);
    }
}

Measured memory_bytes: 9172
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_ints(): return list(map(int, read().split()))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


N, K = read_ints()
AB = read_tuple(N)
AB.sort()

# めちゃくちゃセグ木と二部探したくなるけど線形探索で十分

now = 0  # i番目の要素をすべて考慮したとき何番目の数になるか
# 初めてK以上になったときの数が答え
for a, b in AB:
    now += b
    if now >= K:
        print(a)
        exit()


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

int main()
{
    string n;
    cin >> n;
    for(int i = 0; i < 3; i++) {
        if(n[i] == '1') {
            cout << 9;
        } else if(n[i] == '9') {
            cout << 1;
        } else {
            cout << n[i];
        }
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 3616
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <climits>
#include <numeric>
#include <cmath>
#include <queue>
#include <sstream>
#include <string.h>
#include <bitset>
#include <stack>

using namespace std;
typedef long long ll;

bool cmp(const pair<string, int> &a, const pair<string, int> &b)
{
  if (a.first == b.first) {
    return a.second > b.second;
  }
  return a.first < b.first;
}


int main() {
  int N;
  cin >> N;
  
  vector<string> s(N);
  vector<int> p(N);
  for (int i = 0; i < N; i++) {
    cin >> s[i] >> p[i];
  }
  
  vector<int> vec(N);
  iota(vec.begin(), vec.end(), 0);
  sort(vec.begin(), vec.end(), [&](int x, int y) {
    if (s[x] == s[y]) {
      return p[x] > p[y];
    }
    return s[x] < s[y];
  });
  for (auto itr = vec.begin(); itr != vec.end(); itr++) {
    cout << *itr + 1 << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>]
#include <map>
#include <math.h>
#include <set>
using namespace std;
typedef long long ll;

int main(){
ll n;cin>>n;
vector<ll> a(n),b(n),c(n);
for(ll i=0;i<n;i++)cin>>a[i];
for(ll i=0;i<n;i++)cin>>b[i];
for(ll i=0;i<n;i++)cin>>c[i];
sort(a.begin(),a.end());
sort(b.begin(),b.end());
sort(c.begin(),c.end());
ll ans=0;
for(ll i=0;i<n;i++){
    auto x=lower_bound(a.begin(),a.end(),b[i]);
    auto y=upper_bound(c.begin(),c.end(),b[i]);
    ll aa=x-a.begin();
    ll bb=c.end()-y;
    ans+=aa*bb;
}
cout<<ans;

}

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

int main() {
  int n;
  double a, sum;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> a;
    sum += (1.0f / a);
  }
  double ans =  1.0f / sum ;
  cout << std::fixed;
  cout << std::setprecision(6) << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define fi first
#define se second
#define sz(x) (int)(x).size()
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
template<typename T> inline bool chmax(T &a,T b){if(a<b){a=b;return 1;}return 0;}
template<typename T> inline bool chmin(T &a,T b){if(b<a){a=b;return 1;}return 0;}
template<typename T> vector<T> make_vec(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>
auto make_vec(size_t a,Ts... ts){return vector<decltype(make_vec<T>(ts...))>(a,make_vec<T>(ts...));}
template<typename T,typename U,typename... V>
typename enable_if<is_same<T,U>::value>::type fill_v(U &u,const V... v){u=U(v...);}
template<typename T,typename U,typename... V>
typename enable_if<!is_same<T,U>::value>::type fill_v(U &u,const V... v){for(auto &e:u)fill_v<T>(e,v...);}

const int mod = 1000000007;

struct mint {
    long long x;
    mint(long long x=0) : x((x % mod + mod) % mod) {}
    mint operator-() const { return mint(-x);}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += mod - a.x) >= mod) x -= mod;
        return *this;
    }
    mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
    mint operator+(const mint a) const { return mint(*this) += a;}
    mint operator-(const mint a) const { return mint(*this) -= a;}
    mint operator*(const mint a) const { return mint(*this) *= a;}
    mint pow(long long t) const {
        if (!t) return 1;
        mint a = pow(t>>1);
        a *= a;
        if (t&1) a *= *this;
        return a;
    }
    mint inv() const { return pow(mod-2);}
    mint& operator/=(const mint a) { return *this *= a.inv();}
    mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
bool operator==(const mint& a, const mint& b) { return a.x == b.x;}

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

    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;
    vector<pair<char, int>> cnt;
    cnt.emplace_back(s[0], 0);
    rep(i, n) {
        if (cnt.back().fi == s[i]) cnt.back().se++;
        else cnt.emplace_back(s[i], 1);
    }
    mint ans = 1;
    rep(i, sz(cnt)) {
        int type = cnt[i].se;
        if (i == 0) {
            if (type == 1) {
                ans *= 3;
            } else {
                ans *= 6;
            }
        } else {
            int pre = cnt[i-1].se;
            if (pre == 2) {
                if (type == 2) {
                    ans *= 3;
                } else {
                    ans *= 1;
                }
            } else {
                ans *= 2;
            }
        }
    }
    cout << ans << endl;
}


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

int main() {
  
  int d;
  cin >> d;
  
  if (d == 25) cout << "Christmas" << endl;
  if (d == 24) cout << "Christmas Eve" << endl;
  if (d == 23) cout << "Christmas Eve Eve" << endl;
  if (d == 22) cout << "Christmas Eve Eve Eve" << endl;
  
}


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

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define inv(n, a) for(int i = 0; i < n; i++) cin >> a[i]
#define MOD 1000000007
#define INF 1e7
#define LINF 1e15
typedef long long ll;
typedef long double ld;
using Graph = vector<vector<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; }
// 'a' = 97 'z' = 122 => 'a' = 0 'z' = 25

int main() {
    ll n; ll k; cin >> n >> k;
    vector<ll> a(n+1);
    for(int i = 1; i <= n; i++) cin >> a[i];
    vector<ll> visited(n+1); //その街には何回目に来た？
    vector<ll> visited_(n+1); //その回数で来たのはどこの街？
    ll cur = 1, i = 0;
    while(i < k){
        if(visited[cur] != 0){
            ll size = i - visited[cur];
            ll before_loop = visited[cur];
            k -= before_loop;
            ll cnt = (k % size) + before_loop;
            cout << visited_[cnt] << endl;
            return 0;
        }
        visited[cur] = i;
        visited_[i] = cur;
        cur = a[cur];
        i++;
    }
    cout << cur << endl;
}


Measured memory_bytes: 8012
//#include "pch.h"
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <utility>
#include <queue>
#include <algorithm>
#include <functional>
#include <string>
#include <bitset>

#define ll long long
#define fri(n) for(i=0;i<(n);i++)
#define frj(n) for(j=0;j<(n);i++)
#define min(p,q) ((p)<(q)?(p):(q))
#define max(p,q) ((p)>(q)?(p):(q))
#define INF 1000000000000000000//10^18
#define INFINT 2000000001//2*10^9+1
#define MOD 1000000007
#define MODANOTHER 998244353
#define PI acos(-1)

using namespace std;

int main(void)
{
	//変数の宣言
	int h,w;
	static char s[510];
	static int a[510][510];
	int color=0;

	//よく使う変数
	int i,j,k,l;
	int flag=0;
	int ans=0;
	int count=0;
	int temp=0;
	int temp1=0;
	int temp2=0;
	int max=0;
	int min=INFINT;
	int len=0;
	int sum=0;
	int ok=0;
	int ng=0;



	//データの読み込み


	scanf("%d %d",&h,&w);
//	scanf_s("%d %d",&h,&w);

	for(i=0;i<h;i++){
		scanf("%s",s);
//		scanf_s("%s",s,510);
		for(j=0;j<w;j++){
			if(s[j]=='#'){
				a[i][j]=1;
			}else{
				a[i][j]=0;
			}
		}
	}


	//	printf("nは%dです\n", n);
	//	printf("データの読み込み終了\n");
	//実際の処理

	temp2=-1;
	for(i=0;i<h;i++){
		flag=0;
		for(j=0;j<w;j++){
			if(a[i][j]==1){
				flag=1;
			}
		}
		if(flag==1){
			if(temp2==-1){
				temp2=i;
			}
			for(j=0;j<w;j++){
				if(a[i][j]==0) a[i][j]=color+2;
			}
			color=color^1;
			if(temp<i-1){
				for(j=0;j<w;j++){
					if(a[i][j]==1){
						for(k=temp+1;k<i;k++){
							a[k][j]=color+2;
						}
					}
				}
			}
			temp=i;
		}
	}

	for(j=0;j<w;j++){
		a[temp2-1][j]=3;
	}

	for(i=0;i<h;i++){
		a[i][0]=2;
		a[i][w-1]=3;
	}

	//	printf("計算部分終了\n");

	//出力

	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			if(a[i][j]==1||a[i][j]==2){
				printf("%c",'#');
			}else{
				printf("%c",'.');
			}
		}
		printf("\n");
	}
	printf("\n");
	for(i=0;i<h;i++){
		for(j=0;j<w;j++){
			if(a[i][j]==1||a[i][j]==3){
				printf("%c",'#');
			}else{
				printf("%c",'.');
			}
		}
		printf("\n");
	}

	//	printf("結果の出力終了\n");


	return 0;
}



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

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

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

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

const ll INF = 1e9+10;
const ll MOD = 1e9+7;
const ll LINF = 1e18;

ll n,k; 
vll p,c;

bool visited[5005];
ll dp[5005][5005];
ll sub[5005];

ll from;
void dfs(ll v, ll score, ll cnt){
  if(visited[v]){
    dp[from][0]=score;
    sub[from]=cnt;
    return;
  }
  visited[v]=1;
  score+=c[v];
  cnt++;
  dp[from][cnt]=score;
  
  dfs(p[v], score, cnt);
}

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  
  cin>>n>>k;
  p.resize(n); c.resize(n);
  rep(i,n) cin>>p[i], p[i]--;
  rep(i,n) cin>>c[i];
  
  rep(i,n){
    rep(j,n) visited[j]=0;
    from=i;
    dfs(i, 0, 0);
  }
  
  ll ans=-LINF;
  rep(i,n){
    
    // 限界まで回って余った分の中で最大
    {
      ll loop_cnt=k/sub[i];
      ll tmp=dp[i][0]*loop_cnt;
      ll r=k%sub[i];
      ll ma;
      if(loop_cnt>0) ma=0;
      else ma=-LINF;
      rep(j,r) chmax(ma, dp[i][j+1]);
      tmp+=ma;
      chmax(ans, tmp);
    }
    
    // 限界一歩手前まで行ってサイクルの中で最大
    {
      ll loop_cnt=k/sub[i]-1;
      if(loop_cnt>0){
        ll tmp=dp[i][0]*loop_cnt;
        ll ma;
        if(loop_cnt>1) ma=0;
        else ma=-LINF;
        rep(j,sub[i]) chmax(ma, dp[i][j+1]);
        tmp+=ma;
        chmax(ans, tmp);
      }
    }
    
    // 周回しないでサイクル内で最大
    {
      ll ma=-LINF;
      rep(j,min(k,sub[i])) chmax(ma, dp[i][j+1]);
      chmax(ans, ma);
    }
    
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 199296
n,m = map(int, input().split())
a = [[] for _ in range(n)]
b = ""
c = ""
ans = 0
for i in range(n):
  a[i] = list(input())
for j in range(m):
  b += input()
for i in range(n-m+1):
  for j in range(n-m+1):
    for k in range(i,i+m):
      for l in range(j,j+m):
        c += a[k][l]
    if c == b:
      ans += 1
      break
    c = ""
print("Yes" if ans > 0 else "No")

Measured memory_bytes: 9112
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <tuple>
#include <cassert>
#include <exception>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<P> vp;
#define rep(i,a,n) for(ll i = (a);i < (n);i++)
#define per(i,a,n) for(ll i = (a);i > (n);i--)
#define lep(i,a,n) for(ll i = (a);i <= (n);i++)
#define pel(i,a,n) for(ll i = (a);i >= (n);i--)
#define clr(a,b) memset((a),(b),sizeof(a))
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define sz size()
#define print(X) cout << (X) << endl
#define fprint(NUM,X) cout << fixed << setprecision(NUM) << (X) << endl
#define fprints(NUM,X,Y) cout << fixed << setprecision(NUM) << (X) << " " << (Y) << endl
const ll INF = 1e+9+7;
ll n,m,l;
string s,t;
ll d[200010],dp[1010][1010];
double w[1000],v[1000];
double box[200010];

#define MAX 10000
class Prim{
private:
  struct Edge{int to,cost;};
  static const int INF = 1e+9+7;
  vector<Edge> G[MAX];
  int mincost[MAX];
  bool used[MAX];
  int N;
  int m;

public:

  Prim(){
    cin >> N >> m;
    for(int i = 0;i < m;i++){
      int p,q,r;
      cin >> p >> q >> r;
      G[p].pb(Edge{q,r});
      G[q].pb(Edge{p,r});
    }
  }
  int prim(){
    int res = 0;
    for(int i = 0;i < N;i++){
      mincost[i] = INF;
      used[i] = false;
    }
    mincost[0] = 0;
    while(1){
      int v = -1;
      for(int i = 0;i < N;i++){
        if(!used[i] && (v == -1 || mincost[i] < mincost[v]))v = i;
      }
      if(v == -1)break;
      used[v] = true;
      res += mincost[v];
      for(int i = 0;i < G[v].size();i++){
        mincost[G[v][i].to] = min(mincost[G[v][i].to],G[v][i].cost);
      }
    }
    return res;
  }
};

int main(){
  Prim p;
  cout << p.prim() << endl;
  return 0;
}



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

#define rep(i,n) for(long long i=0; i<(long long)(n);i++)
#define rep2(i,s,n) for(long long i=(s); i<(long long)(n);i++)

typedef long long ll;

const ll inf = 1e18+7;
const ll mod = 1e9+7;

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

    if(a<b){
        rep(i,b){
            cout<<a;
        }
        cout<<endl;
        return 0;
    }
    rep(i,a){
        cout<<b;
    }
    cout<<endl;
}


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

using namespace std;

int main(){
	while(true){
		int h,w;
		cin >> h >> w;
		if(h==0)break;
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				cout << '#';
			}
			cout << endl;
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 3096
#include <iostream>//cout<<right で右揃え
#include <iomanip>//cout<<setw(数字) で空白による桁揃え
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <cstdlib>//abs()で整数絶対値
#include <cmath>//abs()かfabs()で少数絶対値
#include <functional>//sort第三引数greater<型名>()で降順
#include <map>

using namespace std;
using ll = long long int;

int main(){
    ll X,K,D;cin>>X>>K>>D;
    if(K<=(abs(X)/D)){
        cout << abs(X) - K * D << endl;
        return 0;
    }else{
        K -= abs(X) / D;
        X %= D;
        if(X<0){
            if(K%2==1) X += D;
        }else{
            if(K%2==1) X -= D;
        }
        cout << abs(X) << endl;
    }
    return 0;
}

Measured memory_bytes: 3632