akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

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

X,Y = inputSL()

if ord(X) == ord(Y):
  print("=")
elif ord(X) > ord(Y):
  print(">")
else:
  print("<")

Measured memory_bytes: 65388
#!/usr/bin/env python3
import sys
import heapq
from collections import deque
input = lambda: sys.stdin.readline()[:-1]
sys.setrecursionlimit(10**8)
inf = float('inf')
mod = 10**9+7

h,w=map(int,input().split())
A=[list(input()) for i in range(h)]
# A=(tuple(input()) for i in range(h))
# print(A)
dis=[[-1]*w for i in range(h)]
hq=deque()
for i in range(h):
    for j in range(w):
        if A[i][j]=="#":
            hq.append((0,i,j))
            dis[i][j]=0
dii=[(1,0),(-1,0),(0,1),(0,-1)]
# heapq.heapify(hq)
ans=0
while hq:
    count,i,j=hq.popleft()
    for di,dj in dii:
        if not (0<=i+di<h and 0<=j+dj<w):
            continue
        if dis[i+di][j+dj]==-1:
            hq.append((count+1, i+di, j+dj))
            dis[i+di][j+dj]=count+1
            ans=max(ans,count+1)
#             # print(count+1)
# ans=0
# for Ai in dis:
#     ans=max(ans,max(Ai))
print(ans)
# for d in dis:
#     print(d)

    
    


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

int main(){
 int P, Q, R, min, sum; 
 min = 500;
 cin >> P >> Q >> R; 
 sum = P + Q;
 if (min > sum) min = sum; 
 sum = R + Q;
 if (min > sum) min = sum;
 sum = P + R;
 if (min > sum) min = sum;
 cout << min;  
 return 0; 
}

Measured memory_bytes: 256
I=lambda:list(map(int,input().split()))
n=I()
t,a=I()
s=10**7
p=0
A=I()
for j in range(len(A)):
  i=A[j]
  q=abs(a-(t-0.006*i))
  if q < s:
    s = q
    p = j+1
print(p)
    


Measured memory_bytes: 3188
import java.util.*;
class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int r = scanner.nextInt();
        int s = scanner.nextInt();
        int p = scanner.nextInt();
        String ts = scanner.next();
        StringBuilder t = new StringBuilder(ts);
        int ans = 0;
        for(int i = 0; i < n; i++){
            if(i < k){
                ans += getMax(t.charAt(i), r, s, p);
            }else{
                if(t.charAt(i-k) != t.charAt(i)){ans += getMax(t.charAt(i), r, s, p);}
                else{t = t.replace(i, i+1, "?");}
            }
        }
        System.out.println(ans);
    }
    public static int getMax(char hand, int r, int s, int p){
        if(hand == 'r'){return p;}
        else if(hand == 's'){return r;}
        else{return s;}
    }
}


Measured memory_bytes: 26856
#include <bits/stdc++.h>  // g++ -std=c++14 -o a a.cpp

using namespace std;

typedef pair<int, int> P;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define repto(i, n) for(int i = 0; i <= (n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end()) // ユニークなvectorにする。連続した値を除去して切り出す。
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
#define DEBUG(x) cout << #x << ": " << x << endl;

__attribute__((constructor))
void initial() {
  cin.tie(0);
  ios::sync_with_stdio(false);
}

int main() {
  int m, f, b;
  cin >> m >> f >> b;
  if (m >= b) {
    cout << 0 << endl;
  } else {
    int lest = b - m;
    if (lest <= f) {
      cout << lest << endl;
    } else {
      cout << "NA" << endl;
    }
  }
}



Measured memory_bytes: 3188
#include <bits/stdc++.h> // Tomasz Nowak
using namespace std;     // XIII LO Szczecin
using L = long long;

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

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

	vector<L> groupScore(1 << n);
	for(int mask = 1; mask < (1 << n); ++mask)
		for(int i = 0; i < n; ++i)
			if(mask & (1 << i))
				for(int j = i + 1; j < n; ++j)
					if(mask & (1 << j))
						groupScore[mask] += a[i][j];

	vector<L> dp(1 << n);
	for(int mask = 1; mask < (1 << n); ++mask)
		for(int submask = mask; submask > 0; submask = (submask - 1) & mask)
			dp[mask] = max(dp[mask], groupScore[submask] + dp[mask ^ submask]);

	cout << dp[(1 << n) - 1] << '\n';
}


Measured memory_bytes: 1280
void main() {
	auto ip = readAs!(int[]), A = ip[0], B = ip[1], C = ip[2];
	if(A == B && B == C) {
		if(A % 2 == 0) {
			writeln(-1);
			return;
		} else {
			writeln(0);
			return;
		}
	}
	ulong cnt;
	while(A % 2 == 0 && B % 2 == 0 && C % 2 == 0) {
		int tmpA = A, tmpB = B, tmpC = C;
		A = tmpB/2 + tmpC/2;
		B = tmpA/2 + tmpC/2;
		C = tmpA/2 + tmpB/2;
		cnt++;
	}
	cnt.writeln;
}

// ===================================

import std.stdio;
import std.string;
import std.functional;
import std.conv;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}


Measured memory_bytes: 256
//
//  main.cpp

#include <iostream>
using namespace std;


int main(){	
	int n,answer=0;
	string str;
	string ring[100];
	cin >> str >> n;
	for(int i=0;i<n;i++){
		cin >> ring[i];
		ring[i] += ring[i];
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<ring[i].size()-str.size();j++){
			string memo = ring[i].substr(j,str.size());
			if(memo == str){
				answer ++;
				break;
			}
		}
	}
	cout << answer << endl;
	return 0;
}

Measured memory_bytes: 3164
#include <bits/stdc++.h>
 
#define f first
#define s second
#define pb push_back
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
 
const int N = (int)2e5 + 123, inf = 1e9, mod = 1e9 + 7;
const ll INF = 1e18;
 
int n, m, q, a[N], b[N], aa = inf, bb = inf, ans;
int main()
{
	scanf("%d%d%d", &n, &m, &q);
	for(int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
		aa = min(aa, a[i]);
	}
	for(int i = 1; i <= m; i++){
		scanf("%d", &b[i]);
		bb = min(bb, b[i]);
	}
	ans = aa + bb;
	while(q--){
		int x, y, c;
		scanf("%d%d%d", &x, &y, &c);
		ans = min(ans, a[x] + b[y] - c);
	}
	printf("%d", ans);
}



Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
#define repr(i, a, b) for (int i = a; i < b; i++)
#define rep(i, n) for (int i = 0; i < n; i++)
typedef long long ll;
#define H 1000000000

struct abc{
    ll first;
    ll second;
};

int main(){
    ll n;
    cin >> n;
    vector<abc> vec(n);
    for(ll i=0;i<n;i++){
        ll x,l;
        cin >> x >> l;
        vec[i].first=x-l;
        vec[i].second=x+l;
    }
    
    sort(vec.begin(),vec.end(),[](const abc& x,const abc& y) {return x.second < y.second;});
    
    ll now,ans=1;
    
    for(ll i=0;i<n;i++){
        ll now=vec[i].second;
        ll j=i;
        while(j<n){
            if(now<=vec[j].first){
                ans++;
                break;
            }
            j++;
        }
        i=j-1;
        if(i>=n-2) break;
    }
    
    cout << ans << endl;
    
    return 0;
}






Measured memory_bytes: 1920
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
#define ll long long
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
using pii = pair<int, int>;

int main()
{
	usecppio
	int k, x;
	cin >> k >> x;
	for (int i = x-k+1; i<=x+k-1; i++)
	{
		cout << i <<' ';
	}
}


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

using namespace std;

#define x first
#define y second
#define mp make_pair
#define pb push_back

typedef long long ll;

const ll MOD = 1e9+7;
const ll INF = 1e9+5;

double dp[3005];

int main() {
	int n;
	scanf("%d", &n);
	dp[0] = 1;
	for (int i=1 ; i<=n ; i++) {
		double x;
		scanf("%lf", &x);
	//	cout <<"x = "<<x<<endl;
		for (int j=i ; j>=0 ; j--) {
			dp[j] = dp[j] * (1-x);
			if (j) dp[j] += dp[j-1] * x;
	//		cout <<"dp["<<j<<"] = "<<dp[j]<<endl;
		}
	}
	double sol = 0;
	for (int i=(n+1)/2 ; i<=n ; i++) sol += dp[i];
	printf("%.10lf\n", sol);
	return 0;
}

Measured memory_bytes: 3840
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(I, a, b) for (int i = (a); i < (b); ++i)
using namespace std;
using ll = long long;

int main() {
  ll a,b;
  cin >> a >> b;
  ll c,d;
  cin >> c >> d;  
  a--;
  ll sum = 0,dif = 0;
  
  ll gc = gcd(c,d);
  ll e = d / gc;
  e *= c;
  
  sum += b;
  sum -= b/c;
  sum -= b/d;
  sum += b/e;
  
  dif += a;
  dif -= a/c;
  dif -= a/d;
  dif += a/e;
  
  ll ans = sum - dif;
  cout << ans << endl;           
              
}

Measured memory_bytes: 3592
W,H,N = map(int,input().split())

L = 0
R = W
D = 0
U = H

for _ in range(N):
  x,y,a = map(int,input().split())
  if a == 1:
    L = max(L,x)
  if a == 2:
    R = min(R,x)
  if a == 3:
    D = max(D,y)
  if a == 4:
    U = min(U,y)

x = max(0,R-L)
y = max(0,U-D)
answer = x*y

print(answer)


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

using namespace std;

#define Vi vector<int>
#define FOR(i,s,e) for (int i=s; i<e; i++)
#define ITER(v) v.begin(), v.end()

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

    string str;

    cin >> str;
    reverse(ITER(str));
    cout << str << endl;

    return 0;
}

Measured memory_bytes: 3156
def solve(n, query):
    for l, r, d in query:
        if is_same(l, r):
            if d != diff(l, r):
                return 'No'
        else:
            unite(l, r, d)
    return 'Yes'


def unite(x, y, w):
    w += diff_weight[x]-diff_weight[y]
    rt_x = find(x)
    rt_y = find(y)

    if rt_x == rt_y:
        return
    if rank[rt_x] >= rank[rt_y]:
        par[rt_y] = rt_x
        diff_weight[rt_y] = w
        if rank[rt_x] == rank[rt_y]:
            rank[rt_x] += 1
    else:
        par[rt_x] = rt_y
        diff_weight[rt_x] = -w


def find(x):
    if par[x] < 0:
        return x
    else:
        px = find(par[x])
        diff_weight[x] += diff_weight[par[x]]
        par[x] = px
        return px


def weight(x):
    find(x)
    return diff_weight[x]


def is_same(x, y):
    return find(x) == find(y)


def diff(x, y):
    return weight(y)-weight(x)


if __name__ == '__main__':
    n, m = map(int, input().split())
    par, rank = [-1]*(n+1), [0]*(n+1)
    diff_weight = [0]*(n+1)
    query = []
    for _ in range(m):
        l, r, d = map(int, input().split())
        query.append((l, r, d))
    print(solve(n, query))


Measured memory_bytes: 39884
//
//  main.cpp
//  ALDS1_7_C

#include <iostream>
#include <vector>
#define rep(i,n) for(int i=0;i<(n);++i)
using namespace std;
using P=pair<int,int>;
using ll = long long;
#define NIL -1
#define MAX 10010
struct Node { int parent,left,right;};
struct Node T[MAX]; // 親　左の子　右の子
void preParse(int u){ //　先行順巡回
    if(u==NIL) return;
    printf(" %d",u);
    preParse(T[u].left);
    preParse(T[u].right);
}
void inParse(int u){ //　中間順巡回
    if(u==NIL) return;
    inParse(T[u].left);
    printf(" %d",u);
    inParse(T[u].right);
}
void postParse(int u){ //　後行順巡回
    if(u==NIL) return;
    postParse(T[u].left);
    postParse(T[u].right);
    printf(" %d",u);
}
int main(int argc, const char * argv[]) {
    int n; // 節の数
    scanf("%d",&n);
    rep(i,n) T[i].parent=NIL; // 初期化
    int v,l,r;
    rep(i,n){
        scanf("%d %d %d",&v,&l,&r); // 節番号　左の子　右の子
        T[v].left=l;
        T[v].right=r;
        if(l!=NIL) T[l].parent=v;
        if(r!=NIL) T[r].parent=v;
    }
    // 根を探す
    int root=0;
    rep(i,n) if(T[i].parent==NIL) root=i;
    printf("Preorder\n");
    preParse(root);
    printf("\nInorder\n");
    inParse(root);
    printf("\nPostorder\n");
    postParse(root);
    printf("\n");
    return 0;
}



Measured memory_bytes: 3152
#include <stdio.h>

int n;
int w[100000];

int track( int );

int main( void ) {
	int k, i, limit, left, right;

	scanf("%d %d", &n, &k );

	for( i = 0; i < n; i++ ) {
		scanf("%d", &w[i] );
	}
	
	left = 0;
	right = 1e9;
	while( right-left > 1 ){
		limit = (left+right)/2;
		
		if( track(limit) <= k ){
			right = limit;
		}
		else{
			left = limit;
		}
	}
	printf("%d\n", right );

	return 0;
}

int track( int limit ) {
	int i, pre, tr;

	pre = 0;
	tr = 1;
	for( i = 0; i < n; i++ ) {
		if( w[i] > limit ) {
			return 1e9;
		}

		if( w[i] + pre <= limit ) {
			pre += w[i];
		}
		else {
			tr++;
			pre = w[i];
		}
	}

	return tr;
}


Measured memory_bytes: 2232
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
#define rep(i,n) for (ll i=0;i<n;++i)
#define rep2(i,a,b) for (ll i=a;i<b;++i)
const ll MOD=1000000007;

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

int main() {
    int N;
    cin >> N;
    vector<Pii> red(N),blue(N);
    rep(i,N){
        int a,b;
        cin >> a >> b;
        red[i]=Pii(a,b);
    }
    rep(i,N){
        int c,d;
        cin >> c >> d;
        blue[i]=Pii(d,c);
    }
    sort(red.begin(),red.end());
    sort(blue.begin(),blue.end());
    int ans=0;
    rep(i,N){
        int ex=101;
        rep(j,N){
            if (red[j].first<blue[i].second&&red[j].second<blue[i].first){
                ex=j;
            }
        }
        if (ex>N-1){
            continue;
        }
        ans++;
        red[ex]=Pii(201,201);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
class Mint < Numeric
  
  attr_reader :value, :mod
  @@mod = 10 ** 9 + 7
  
  def initialize(value)
    @value = value
  end
  
  def +(other)
    if other.kind_of?(Mint)
      Mint.new((value + other.value) % @@mod)
    elsif other.kind_of?(Integer)
      Mint.new((value + other) % @@mod)
    else
      x, y = other.coerce(self)
      x + y
    end
  end
  
  def -(other)
    if other.kind_of?(Mint)
      Mint.new((value - other.value) % @@mod)
    elsif other.kind_of?(Integer)
      Mint.new((value - other) % @@mod)
    else
      x, y = other.coerce(self)
      x - y
    end
  end
  
  def *(other)
    if other.kind_of?(Mint)
      Mint.new((value * other.value) % @@mod)
    elsif other.kind_of?(Integer)
      Mint.new((value * other) % @@mod)
    else
      x, y = other.coerce(self)
      x * y
    end
  end
  
  def /(other)
    if other.kind_of?(Mint)
      Mint.new((value * other.value.pow(@@mod-2, @@mod) % @@mod ))
    elsif other.kind_of?(Integer)
      Mint.new((value * other.pow(@@mod-2, @@mod) % @@mod ))
    else
      x, y = other.coerce(self)
      x / y
    end
  end
  
  # def %(other)
  #   if other.kind_of?(Mint)
  #     raise MintDivisionError
  #   elsif other.kind_of?(Integer)
  #     Mint.new(value % @@mod)
  #   else
  #     x, y = other.coerce(self)
  #     x % y
  #   end
  # end
  
  def coerce(other)
    if other.kind_of?(Integer)
      return [Mint.new(other), self]
    elsif other.kind_of?(Mint)
      return [other, self]
    else
      super
    end
  end
  
  def inspect
    "#{value} (mod #{@@mod})"
  end
  
  def to_s
    "#{value % @@mod}"
  end
end

class Integer
  
  def coerce(other)
    if other.kind_of?(Mint)
      return [other, Mint.new(self)]
    elsif other.kind_of?(Integer)
      return [other, self]
    else
      super
    end
  end
  
end

class MintDivisionError < StandardError
  def initialize(msg="divided by Mint")
    super
  end
end

class Range
  alias_method :primitive_initialize, :initialize
  def initialize(s,t)
    s = s.value if s.kind_of?(Mint)
    t = t.value if s.kind_of?(Mint)
    primitive_initialize(s,t)
  end
end

n, k = gets.to_s.split.map{|e|e.to_i}
 
ans = (k..n+1).map{|i| Mint.new(i) * (n + n - i + 1) / 2 - i * ( i - 1 ) / 2 + 1 }.sum
 
puts ans

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

#define debug(x) cout <<"DEBUG"<<" "<< #x << ":" << x << '\n'

//↓0-originか1-originでn回繰り返し
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)      //0-origin昇順
#define rep1(i,n) for(int i = 1; i <= ((int)(n)); i++)    //1-origin昇順
#define rrep(i,n) for(int i = ((int)(n)-1); i >= 0; i--)  //0-origin降順
#define rrep1(i,n) for(int i = ((int)(n)); i >= 1; i--)   //1-origin降順
//rep2 -> 第二引数 m から n 回繰り返し ex) m=5 n=3 なら i=5,i=6,i=7 まで
#define rep2(i,m,n) for(int i = ((int)(m)); i < ((int)(n))+((int)(m)); i++)
#define SIZE(x) ((int)((x).size()))
#define all(x) (x).begin(),(x).end()
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vii;  //2次元配列
typedef vector<ll> vll;
typedef vector<string> vs;
typedef pair<int,int> PII;
template<class T,class U> inline bool chmax(T &a, const U &b){if(a<b){a=b;return 1;}return 0;}
template<class T,class U> inline bool chmin(T &a, const U &b){if(a>b){a=b;return 1;}return 0;}

/* 円周率は M_PI を使おうね */
const ll infll = (1LL<<62)-1;
const int inf = (1<<30)-1;

/*FUNCs=================================================*/


/*MAIN==================================================*/
signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);   //cin cout 高速化
    //cout << fixed << setprecision(10);
    
    int n; cin >> n;
    vll a(n);
    rep(i,n) {
        cin >> a[i];
    }
    vector<vll> dp(2, vll(100005));
    dp[0][0] = a[0];
    dp[1][0] = a[0]*(-1);
    for(int i = 1; i < n; ++i) {
        /*
        dp[0][p] : Apが元の数のままの、A0~Apの最適な合計値
        dp[1][p] : Apが元の数のままの、A0~apの最適な合計値
        */
        dp[0][i] = max(dp[0][i-1]+a[i], dp[1][i-1]+a[i]*(-1));  //ひっくり返さない
        if(i==n-1) break;  // 最後はひっくり返せない
        dp[1][i] = max(dp[0][i-1]+a[i]*(-1), dp[1][i-1]+a[i]);  //ひっくり返す
    }
    cout << max(dp[0][n-1], dp[1][n-1]) << endl;
}

Measured memory_bytes: 3456
#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
	int x, y, z;
	int tx, ty, tz;
	int i, n;
	scanf("%d", &n);
	x = y = z = 0;
	while (n--) {
		scanf("%d%d%d", &tz, &tx, &ty);
		if (abs(x - tx) + abs(y - ty) + z > tz || x + tx + y + ty + z + tz & 1) {
			puts("No");
			return 0;
		}
		x = tx;
		y = ty;
		z = tz;
	}
	puts("Yes");
	return 0;
}


Measured memory_bytes: 128
S = input()
n = len(S)
mod = (10**9 + 7)

dp = [[0] * 4 for _ in range(n + 1)]

dp[n] = [0, 0, 0, 1]
for i in range(n-1, -1, -1):
    if S[i] == '?':
        dp[i][3] =  dp[i+1][3] * 3 % mod
        dp[i][2] = (dp[i+1][2] * 3 + dp[i+1][3]) % mod
        dp[i][1] = (dp[i+1][1] * 3 + dp[i+1][2]) % mod
        dp[i][0] = (dp[i+1][0] * 3 + dp[i+1][1]) % mod
    elif S[i] == 'C':
        dp[i][3] =  dp[i+1][3] % mod
        dp[i][2] = (dp[i+1][2] + dp[i+1][3]) % mod
        dp[i][1] =  dp[i+1][1] % mod
        dp[i][0] =  dp[i+1][0] % mod
    elif S[i] == 'B':
        dp[i][3] =  dp[i+1][3] % mod
        dp[i][2] =  dp[i+1][2] % mod
        dp[i][1] = (dp[i+1][1] + dp[i+1][2]) % mod
        dp[i][0] =  dp[i+1][0] % mod
    elif S[i] == 'A':
        dp[i][3] =  dp[i+1][3]
        dp[i][2] =  dp[i+1][2]
        dp[i][1] =  dp[i+1][1]
        dp[i][0] = (dp[i+1][0] + dp[i+1][1]) % mod
print(dp[0][0])

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

/**
 * [IPC - Contest III]
 * @author Rodrigo Moreira Pires de Andrade
 * @version 13/04/2020
*/

using namespace std;

// Functions and class come here..
bool Solvef(int *a, int n, int k) {

    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            if((a[j] - a[i]) > k)
                return false;
        }
    }

    return true;
}

int main() {

    int solve[5];
    int maxsize;

    for(int i = 0; i < 5; i++) 
        cin >> solve[i];

    cin >> maxsize;

    if(Solvef(solve, 5, maxsize)) {
        cout << "Yay!" << endl;
    } else {
        cout << ":(" << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <cmath>
#include <iomanip>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <numeric>

typedef unsigned long long ULONG;
typedef long long LONG;
using namespace std;

#define PI 3.1415926535897932384626433
#define _DBG_

#define BIG 10000000000 //10

#define LAST 10000000 //10^7

#define MOD (LONG)(10e8 + 7)



int main(void) {
	int L, R, d;
	cin >> L >> R >> d;
	int count = 0;
	for (int i = L; i <= R; i++) {
		if (i%d == 0) {
			count++;
		}
	}
	cout << count << endl;
	return 0;
}


Measured memory_bytes: 3584
#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
const int MOD=1e9+7;
typedef pair<int,int> pii;
typedef long long ll;
template<typename A,size_t N,typename T>
void Fill(A (&array)[N],const T &val)
{
    std::fill( (T*)array,(T*)(array+N),val );
}

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

int main(void)
{
    int N,M,correct=0,pena=0;
    int p[100005];
    int WA[100005];
    bool AC[100005];
    memset(WA,0,sizeof(WA));
    memset(AC,false,sizeof(AC));
    string S[100005];
    cin >> N >> M;
    for(int i=0;i<M;i++)
    {
        cin >> p[i] >> S[i];
        if(S[i]=="AC") AC[p[i]]=true;
        else
        {
            if(S[i]!="AC" && !AC[p[i]]) WA[p[i]]++;
        }
    }
    for(int i=1;i<=N;i++)
    {
        if(AC[i]) 
        {
            correct++;
            pena+=WA[i];
        }
    }
    cout << correct << ' ' << pena << endl;

}

Measured memory_bytes: 6656
a,b,c=map(int,input().split())
seven=0
five=0
if(a==5):
  five+=1
elif(a==7):
  seven+=1
if(b==5):
  five+=1
elif(b==7):
  seven+=1
if(c==5):
  five+=1
elif(c==7):
  seven+=1
if(five==2 and seven==1):
  print("YES")
else:
  print("NO")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, o, n) for (auto i = (o); (i) < (n); ++(i))
#define FOR1(i, n) FOR(i, 1, n+1)
#define REP(i, n) FOR(i, 0, n)
#define REPR(i, n) for (auto i = (n)-1; (i) >= 0; --i)
#define REPI(itr, v) for (auto itr = v.begin(); itr != v.end(); ++itr)
#define REPIR(itr, v) for (auto itr = v.rbegin(); itr != v.rend(); ++itr)
#define fi first
#define se second
#define ll long long
#define int long long
#define V2(name, h, w) vector<vector<int> > name((h), vector<int>(w));
#define myCeil(dividend, divisor) ceil((double)(dividend) / (double)(divisor))
#define myFloor(dividend, divisor) floor((double)(dividend) / (double)(divisor))
#define calcDigits(num) floor(log10(num))+1

#define dl(line) cerr << "RUN: until " << (line) << "th line." << endl;
#define dv(name, value) cerr << (name) << " is " << (value) << endl;
#define da(v)  cerr << "["; REPI(itr, v){cerr << *itr << (itr != --v.end() ? ", " : "");} cerr << "]" << endl;
#define dpa(v) cerr << "[ " << endl;REPI(itr, v) { cerr << "  [" << (*itr).first << ", " << (*itr).second << ']' << (itr != --v.end() ? "," : "") << endl; } cerr << "]" << endl;


void solve(long long A, long long B, long long C, long long K){
  int cnt = 0;

  if (K > A) {
    K -= A;
    cnt += A;
  } else {
    cnt = K;
    K = 0;
    cout << cnt << endl;
    return;
  }
  if (K > B) {
    K -= B;
  } else {
    K = 0;
    cout << cnt << endl;
    return;
  }
  cnt -= K;
  cout << cnt << endl;
}

signed main(){
  long long A;
  scanf("%lld",&A);
  long long B;
  scanf("%lld",&B);
  long long C;
  scanf("%lld",&C);
  long long K;
  scanf("%lld",&K);
  solve(A, B, C, K);
}


Measured memory_bytes: 3688
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
#include <cmath>
using namespace std;

int main() {
    string s, t;
    cin >> s >> t;
    int n1 = s.size(), n2 = t.size();
    vector<int> sa(n1 + 1, 0), sb(n1 + 1, 0), ta(n2 + 1, 0), tb(n2 + 1, 0);
    for (int i = 0; i < n1; i++) {
        if (s[i] == 'A') {
            sa[i + 1] = sa[i] + 1;
            sb[i + 1] = sb[i];
        } else {
            sa[i + 1] = sa[i];
            sb[i + 1] = sb[i] + 1;
        }
    }
    for (int i = 0; i < n2; i++) {
        if (t[i] == 'A') {
            ta[i + 1] = ta[i] + 1;
            tb[i + 1] = tb[i];
        } else {
            ta[i + 1] = ta[i];
            tb[i + 1] = tb[i] + 1;
        }
    }
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        int c1 = sa[b] - sa[a - 1] + 2 * (sb[b] - sb[a - 1]);
        int c2 = ta[d] - ta[c - 1] + 2 * (tb[d] - tb[c - 1]);
        // cout << c1 << " " << c2 << endl;
        if (c1 % 3 == c2 % 3) {
            cout << "YES";
        } else {
            cout << "NO";
        }
        cout << endl;
    }
}


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

#define M_PI       3.14159265358979323846   // pi

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> t3;

#define rep(a,n) for(ll a = 0;a < n;a++)

static const ll INF = 1e15;
static const ll mod = 1e9+7;

template<typename T>
static inline void chmin(T& ref, const T  value) {
    if (ref > value) ref = value;
}

template<typename T>
static inline void chmax(T& ref, const T value) {
    if (ref < value) ref = value;
}

struct MaxFlowCalculator {
	int max_flow(int s, int t, const vector<vector<pair<int, int>>>& g) {
		struct edge_ { int to, cap, rev; };
		vector<bool> used(g.size(), false);
		vector<vector<edge_>> G(g.size());
		for (int i = 0; i < g.size(); i++) for (int j = 0; j < g[i].size(); j++)
		{
			int from = i, to = g[i][j].second;
			int cap = g[i][j].first;
			G[from].push_back({ to, cap, (int)G[to].size() });
			G[to].push_back({ from, 0, (int)G[from].size() - 1 });
		}
		auto dfs = [&](auto&& f, int v, int t, int fl)->int {
			if (v == t) return fl;
			used[v] = true;
			rep(i, G[v].size()) {
				edge_& e = G[v][i];
					if (!used[e.to] && e.cap > 0) {
					int d = f(f, e.to, t, min(fl, e.cap));
					if (d > 0) {
						e.cap -= d;
						G[e.to][e.rev].cap += d;
						return d;
					}
				}
			}
			return 0;
		};
		int flow = 0;
		while (1) {
			used.assign(used.size(), false);
			int f = dfs(dfs, s, t, INT_MAX);
			if (f == 0) return flow;
			flow += f;
		}
	}
};

int main() {
	ll p, r, q;
	cin >> p >> r >> q;
	ll a1 = p + r;
	ll a2 = r + q;
	ll a3 = p + q;
	cout << min(a1, min(a2, a3)) << endl;
    return 0;
}


Measured memory_bytes: 3576
n,m = gets.split.map(&:to_i)
xs = gets.split.map(&:to_i).sort

if n >= m
  puts 0
  exit
end
if n == 1
  puts xs[-1] - xs[0]
  exit
end

distances = []
(xs.size-1).times do |i|
  distances.push xs[i+1] - xs[i]
end
puts distances.sort[0, distances.size-(n-1)].inject(:+)


Measured memory_bytes: 11248
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll ZERO = 0;
const int Inf = 1000000000;
const ll INF= 1e18;
const ll MOD = 1000000007;
const double PI = 3.1415926535897;
typedef pair<ll,ll> P;

int fac[1000010], finv[1000010], inv[1000010];

// テーブルを作る前処理
void COMinit()
{
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < 1000010; 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;
}

int main() {
    ll N;
    cin >> N;
    string S;
    cin >> S;
    COMinit();
    vector<int> vec(26);
    for(int i = 0;i < N;i++) {
        vec.at(S.at(i) - 'a')++;
    }
    ll ret = 1;
    for(int i = 0;i < 26;i++) {
        ret = ret * (vec.at(i) + 1) % MOD;
    }
    if(ret == 0) {
        cout << MOD - 1 << endl;
    }
    else {
        cout << ret - 1 << endl;
    }
}

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

int main() {
  int64_t a,b;
  cin>>a>>b;
  int x = b-a;
  if (a*b <= 0) cout << "Zero" << endl;
  else if (a>=0||x%2) cout << "Positive" << endl;
  else cout << "Negative" << endl;  
}


Measured memory_bytes: 256
#include<bits/stdc++.h>  
#define Rg register 
#define i60 long long 
#define fp( i , x , y ) for(Rg int i=(x); i<=(y); ++i) 
#define fq( i , x , y ) for(Rg int i=(y); i>=(x); --i) 
using namespace std ; 
const int hgs = 1e9+7 , N = 2005 ; 
i60 f[N][N] , n , k , fac[N*N] , inv[N*N] ; 
i60 power( i60 A , int B ) { 
    i60 tep = 1 ; 
    for( ; B ; B >>= 1 ) { 
        if( B&1 ) tep = tep * A % hgs ; 
        A = A * A % hgs ; 
	} return tep ;  } 
i60 C ( int A , int B ) { return A == 0 ? 1 : fac[B] * inv[A] % hgs * inv[B-A] % hgs ; }  
signed main( ) { 
    cin >> n >> k ;  fac[0] = 1 ; 
    if( k == 1 ) { cout << 1 << endl ; return 0 ; } 
    fp( i , 1 , n*k ) fac[i] = fac[i-1] * i % hgs ;  
    fp( i , 0 , n*k ) inv[i] = power( fac[i] , hgs-2 ) ;  
    fp( i , 1 , n ) f[i][0] = 1 ; 
    fp( i , 1 , n ) 
      fp( j , 1 , i ) 
	    f[i][j] = ( f[i-1][j] + f[i][j-1] 
		   * (n-j+1) % hgs * C( k-2 , n*k-i-(k-1)*(j-1)-1 ) ) % hgs ; 
	cout << f[n][n] << endl ; 
    return 0 ; 
} 

Measured memory_bytes: 94464
#include <stdio.h>
#include <stdlib.h>

int cmp(const void*a,const void*b){
	return *(int*)b-*(int*)a;
}
int main(void){
	int N;
	scanf("%d",&N);
	int i;
	int A[N];
	int count = 0;
	long long a=0,b=0;
	for(i=0;i<N;i++)scanf("%d",&A[i]);
	qsort(A,N,sizeof(int),cmp);
	for(i=0;i<N;i++){
		count =0;
		while(A[i]==A[i+1]){
			i++;
			count++;
			if(count>0)break;
		}
		if(count>0){
			if(a==0)a = A[i];
			else{
				b = A[i];
				printf("%lld",a*b);
				return 0;
			}
		}
	}
	printf("0");
	return 0;
}

Measured memory_bytes: 892
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+10;
using namespace std;
ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
int n,m,k,t,len;
ll ans;
char a[20];
void dfs(int pos,ll now)
{
    if(pos==len)
    {
        ans+=now;
        return;
    }
    for(int i=1;pos+i<=len;i++)
    {
        ll p=0;
        for(int j=pos;j<=pos+i-1;j++)p=p*10+a[j]-'0';
        dfs(pos+i,now+p);
    }
}
int main()
{
    int i,j;
    scanf("%s",a);
    len=strlen(a);
    dfs(0,0LL);
    printf("%lld\n",ans);
    //system("Pause");
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h> //Andrei Alexandru a.k.a Sho10
#define ll long long
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define all(a) (a).begin(), (a).end()
#define sz size
#define f first
#define s second
#define pb push_back
#define er erase
#define in insert
#define mp make_pair
#define pi pair
#define rc(s) return cout<<s,0
#define endl '\n'
#define mod 1000000007
#define modul 998244353
#define PI 3.14159265359
#define CODE_START  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
ll n,viz[100005];
map<pair<ll,ll>,ll>m;
vector<ll>v;
int32_t main(){
CODE_START;
cin>>n;
for(ll i=2;i<=sqrt(n);i++)
if(n%i==0){
        v.pb(i);
    if(n/i!=i){
        v.pb(n/i);
    }
}
if(n!=1){
    v.pb(n);
}
sort(v.begin(),v.end());
ll s=0,ans=0;
for(ll i=0;i<v.size();i++)
{
    s=0;
    while(n%v[i]==0&&n!=0){
        s++;
        n=n/v[i];
    }
    ll x=0;
    for (ll i=1;i<=1e9;i++)
    {
        if(i*(i+1)/2>s){
            x=i-1;
            break;
        }
    }
    ans=ans+x;
}
cout<<ans<<endl;
}


Measured memory_bytes: 3700
#!/usr/bin/env python3
import sys
INF = float("inf")


def solve(N: int, a: "List[int]", b: "List[int]", c: "List[int]"):
    DP = [[0]*(N+1) for _ in range(3)]
    for i in range(N):
        # 行動a[i]を選ぶ場合
        DP[0][i+1] = max(DP[1][i], DP[2][i])+a[i]
        # 行動b[i]を選ぶ場合
        DP[1][i+1] = max(DP[2][i], DP[0][i])+b[i]
        # 行動c[i]を選ぶ場合
        DP[2][i+1] = max(DP[0][i], DP[1][i])+c[i]
    print(max(DP[0][N], DP[1][N], DP[2][N]))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N)  # type: "List[int]"
    b = [int()] * (N)  # type: "List[int]"
    c = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, a, b, c)


if __name__ == '__main__':
    main()


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

int main(){
  string s;
  cin >> s;
  static bool IsFirst = false;
  int A_idx, Z_idx = -1;
  rep(i,s.length()){
    if(s[i] == 'A' && !IsFirst){
      A_idx = i;
      IsFirst = true;
    }
    if(s[i] == 'Z' && Z_idx < i) Z_idx = i;
  }
  cout << Z_idx - A_idx + 1 << endl;
  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
 
int a[110];

int main() {
  int n;
  int count = 0;
  
  cin >> n;

    for (int i=0; i < n;i++)
    {
        cin >> a[i];
    }
  for (int i = 0; i < n;i++){
    if(((i+1)%2) != 0 && (a[i] % 2) != 0 ){
      count++;
    }
  }

    cout << count;
  
  return 0;

}

Measured memory_bytes: 3636
//Compiler optimization
#pragma GCC optimize("Ofast")

//include
#include <bits/stdc++.h>
using namespace std;

//typedef
typedef long long ll;
typedef double db;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef string S;
typedef queue<int> qi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<vl> mat;

//macro
#define sort(a) sort(a.begin(),a.end())
#define reverse(a) reverse(a.begin(),a.end())
#define unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define fr(i,n)for(ll i=0;i<(n);i++)
#define ifr(i,n)for(ll i=(n)-1;i>=0;i--)
#define all(x) x.begin(),x.end()

//abbreviation
#define pb push_back
#define elif else if
#define mp make_pair
#define endl '\n'

//debug
#define debug(x) cerr << #x << ': ' << x << endl

//const
const  ll INF = 1e18;

//どうせ使う
ll a,b,c,i,j,k,l,m,n,ans,tmp,hoge,fuga,piyo;

int main(){
    ll x; cin >> x;
    if(x>=30)cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3544
from itertools import accumulate
from collections import deque

N,W=list(map(int,input().split()))
arr=[deque([]) for i in range(4)]

w1,v=list(map(int,input().split()))
arr[0].append(v)

for i in range(N-1):
    w,v=list(map(int,input().split()))
    arr[w-w1].append(v)

for i in range(4):
    arr[i]=sorted(arr[i],reverse=True)
    arr[i]=deque(accumulate(arr[i]))
    arr[i].appendleft(0)

ans=0
for i in range(len(arr[0])):
    for j in range(len(arr[1])):
        for k in range(len(arr[2])):
            for h in range(len(arr[3])):
                weight=(i+j+k+h)*w1+j+2*k+3*h
                value=arr[0][i]+arr[1][j]+arr[2][k]+arr[3][h]
                if weight>W:
                    break
                elif value>ans:
                    ans=value
print(ans)

Measured memory_bytes: 3316
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <queue>
#include <bitset>
#include <stack>
#include <functional>

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...)
#endif

#define rep_(i, a_, b_, a, b, ...) for (int i = (a), i##_len = (b); i < i##_len; ++i)
#define rep(i, ...) rep_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define reprev_(i, a_, b_, a, b, ...) for (int i = (b-1), i##_min = (a); i >= i##_min; --i)
#define reprev(i, ...) reprev_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#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; }
#define fls(x) (64 - __builtin_clzll(x))
#define pcnt(x) __builtin_popcountll(x)
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int,int> P;
typedef long double ld;

int main (void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s, t; cin >> s >> t;
    ll ans = (ll)1e18;
    rep (i, s.size() - t.size() + 1) {
        ll tmp = 0;
        rep (j, t.size()) if (s[i + j] != t[j]) tmp++;
        chmin(ans, tmp);
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 3652
cs = []
3.times do
  cs << gets.split.map(&:to_i)
end
w_div = []
h_div = []
for i in 0..2 do
  w_div << [cs[i][0] - cs[i][1], cs[i][1] - cs[i][2]]
  h_div << [cs[0][i] - cs[1][i], cs[1][i] - cs[2][i]]
end

ans = 'Yes'
for i in 0..1 do
  if w_div[i] != w_div[i+1] || h_div[i] != h_div[i+1]
    ans = 'No'
  end
end
puts ans


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

using namespace std;

#define ll long long int
#define ld long double
#define MAX 200007
#define MOD 1000000007
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

int main(){

    fast;
    string  a,b;
    cin >> a >> b;
    if(a.size()==b.size()-1){

        int flg = 1;

        for(ll i=0;i<a.size();i++){
            if(a[i]!=b[i]){
                flg = 0;
                break;
            }
        }

        if(flg){
            cout << "Yes";
        }
        else{
            cout << "No\n";
        }

    }
    else{
        cout << "No\n";
    }


}


//    cout << fixed << setprecision(2);


Measured memory_bytes: 3608
#include "bits/stdc++.h"
using namespace std;
 
using ll = long long;
 
const ll inf = 1e18;
const int N = 2 * 1e5 + 10;

ll res;
ll dp[100][N];
std::vector<pair<ll, ll>> v;

ll go(ll idx, ll pic, ll capacity){
	if(idx == v.size()) return 0;
	ll xx = 0, yy = 0;
	if(dp[idx][pic] + 1)return dp[idx][pic];
	if(v[idx].first + pic <= capacity){
		xx = v[idx].second + go(idx + 1, pic + v[idx].first, capacity);
	}
	yy = go(idx + 1, pic, capacity);
	return dp[idx][pic] = max(yy, xx);
}

void solve(){
	ll n;
	cin >> n;
	ll capacity;
	cin >> capacity;
	for (int i = 0; i < n; ++i){
		ll x, y;
		cin >> x >> y;
		v.push_back({x, y});
	}
	memset(dp, -1, sizeof dp);
	cout << go(0, 0, capacity);
}
 
int main(int argc, char const *argv[]){
	ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
    ll t = 1;
    //cin >> t;
    while(t--){
    	solve();
    }
}//smf

Measured memory_bytes: 156544
#include <bits/stdc++.h>
#define for1(a,b,i) for(int i=a;i<=b;++i)
#define FOR2(a,b,i) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
inline int read() {
	int f=1,sum=0;
	char x=getchar();
	for(;(x<'0'||x>'9');x=getchar()) if(x=='-') f=-1;
	for(;x>='0'&&x<='9';x=getchar()) sum=sum*10+x-'0';
	return f*sum;
}

#define M 605
#define mod 1000000007
int n,K;
int pos[M],sum[M];
int g[M],f[M][M],ans;

inline void inc(int &x,int y) {x+=y,x-=x>=mod?mod:0;}

inline void dp(int l,int r) {
	if(sum[r]-sum[l-1]&1) return;
	for1(l,r,i) if(pos[i]&&pos[i]<l||pos[i]>r) return;
	int x=g[sum[r]-sum[l-1]];
	for1(l,r-1,i) if(f[l][i]) inc(x,mod-1ll*f[l][i]*g[sum[r]-sum[i]]%mod);
	f[l][r]=x;
	inc(ans,1ll*x*g[n-2*K-sum[r]+sum[l-1]]%mod);
}

int main () {
	//freopen("a.in","r",stdin);
	n=read()*2,K=read();
	for1(1,K,i) {
		int x=read(),y=read();
		pos[x]=y,pos[y]=x;
	}
	g[0]=1;
	for(int i=2;i<=n;i+=2) g[i]=1ll*(i-1)*g[i-2]%mod;
	for1(1,n,i) sum[i]=sum[i-1]+(!pos[i]);
	for1(1,n,i) FOR2(n-i+1,1,j) dp(j,j+i-1);
	cout<<ans<<endl;
}

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

using ll=long long;
#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(),x.end()
#define REACH cerr<<"reached line "<<__LINE__<<endl
#define DBG(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl

using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

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

int read(){
	int i;
	scanf("%lld",&i);
	return i;
}

void printSpace(){
	printf(" ");
}

void printEoln(){
	printf("\n");
}

void print(int x,int suc=1){
	printf("%lld",x);
	if(suc==1)
		printEoln();
	if(suc==2)
		printSpace();
}

string readString(){
	static char buf[3341919];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341919];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(a>b)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

const int inf=LLONG_MAX/3;

signed main(){
	int n=read(),cur=read();
	vi pos(n),d(n),ans(n);
	REP(i,n){
		pos[i]=cur;
		d[i]=read();
		cur=min(cur,abs(cur-d[i]));
	}
	int idx=0;
	for(int i=n-1;i>=0;i--){
		ans[i]=idx<pos[i];
		if(idx>=d[i]/2)idx+=d[i];
	}
	int q=read();
	REP(i,q){
		int x=read()-1;
		printf(ans[x]?"YES\n":"NO\n");
	}
}


Measured memory_bytes: 13696
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int main()
{
  
  int k,n;
  cin>>k>>n;
  
  int a[n];
  for(int i=0;i<n;i++)cin>>a[i];
  
  int m=a[n-1]-a[0];
  
  for(int i=1;i<n-1;i++)
  {
      m=min(m,a[i]+k-a[i+1]);
     // cout<<m<<" "<<a[i]<<" "<<n<<" "<<a[i+1];
      
  }
  cout<<m;
  
  return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
string S;
int i, j, k, n, mx;
bool flag;
int main(){
	cin>>S;
	n=(int)S.size();
	for(j=i+1; j<n; j++){
		if((j-i)%2!=0)
			continue;
		flag=true;
		for(k=0; k<j/2; k++){
			if(S[k]!=S[j/2+k])	flag=false;
		}
		if(flag)
			mx=max(mx, j);
	}
	cout<<mx;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <bitset>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>

using namespace std;


int main(){

	vector<int> zeronum;
	zeronum.push_back(0);
	int count = 0;
	for(int i = 1; i <= 50000; i++){
		int tmp = i;
		while(tmp % 5 == 0){
			count++;
			tmp /= 5;
		}
		zeronum.push_back(count);
	}

	int n = 0;
	while(cin >> n && n != 0){
		cout << zeronum[n] << endl;
	}
	return 0;
}

Measured memory_bytes: 1344
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {
		Main mainObj = new Main();
		mainObj.solve();
	}

	public void solve() throws IOException {
		FastScanner fs = new FastScanner();
		int n = fs.nextInt();
		int[] arr = fs.nextIntArr(n);
		
		int ans = 0;
		for(int i = 0; i < n-2; i++) {
			for(int j = i+1; j < n-1; j++) {
				for(int k = j+1; k < n; k++) {
					
					int a = arr[i];
					int b = arr[j];
					int c = arr[k];
					
					if(a == b || a == c || c == b) {
						continue;
					}
					
					if(a+b > c && b+c > a && a+c > b) {
						ans++;
					}
				}
			}
		}
		System.out.println(ans);
	}

	

	public class FastScanner {

		BufferedReader reader;
		private StringTokenizer st;

		public FastScanner() {
			st = null;
			reader = new BufferedReader(new InputStreamReader(System.in));
		}

		public String next() throws IOException {
			if (st == null || !st.hasMoreElements()) {
				st = new StringTokenizer(reader.readLine());
			}
			return st.nextToken();
		}

		public String nextLine() throws IOException {
			st = null;
			String readLine = null;
			readLine = reader.readLine();
			return readLine;
		}

		public int nextInt() throws NumberFormatException, IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

		public int[] nextIntArr(int n) throws NumberFormatException, IOException {
			int[] retArr = new int[n];
			for (int i = 0; i < n; i++) {
				retArr[i] = nextInt();
			}
			return retArr;
		}

		public long[] nextLongArr(int n) throws NumberFormatException, IOException {
			long[] retArr = new long[n];
			for (int i = 0; i < n; i++) {
				retArr[i] = nextLong();
			}
			return retArr;
		}

		public void close() throws IOException {
			reader.close();
		}
	}

}


Measured memory_bytes: 33680
use strict;
use warnings;
use utf8;

my $line = <STDIN>;
my @nd = split(/\s/, $line);
my $N = $nd[0];
my $D = $nd[1];

my $nnn = $N;

my $person = 0;
while($nnn > 0){
    $nnn -= (1+2*$D);
    $person++;
}

print($person);

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

int main(){
    int n,l,s = 0,m = 1e5,sub;
    cin >> n >> l;
    for(int i = 0;i < n;i ++){
        s += l+i;
        if(abs(l+i)<m){
            m = min(m,abs(l+i));
            sub = l+i;
        }
    }
    cout << s-sub << endl;
    return 0;
}

Measured memory_bytes: 256