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

//Greatest Common Divisor
int findGCD(int a, int b) {
    if (a > b) swap(a, b);
    if (b % a == 0) return a;
    return findGCD(a, b % a);
}

int main(void) {
    int a, b;
    cin >> a >> b;
    cout << findGCD(a, b) << endl;
    return 0;
}

Measured memory_bytes: 1160
def read_input():
	a, b = map(int, input().split())
	return a, b
	
	
def submit():
	a, b = read_input()
	
	if a <= 8 and b <= 8:
		print('Yay!')
	else:
		print(':(')
	
	
if __name__ == '__main__':
	submit()


Measured memory_bytes: 2940
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] input = new int[N];
		for (int i = 0; i < input.length; i++) {
			input[i] = sc.nextInt();
		}
		Arrays.sort(input);
		int beginIndex = 0;
		int endIndex = 0;
		int res = 1;
		while (endIndex < N - 1) {
			if (input[endIndex] - input[beginIndex] < 3) {
				if (res < endIndex - beginIndex + 1) {
					res = endIndex - beginIndex + 1;
				}
			}
			if (input[endIndex + 1] - input[beginIndex] < 3) {
				endIndex++;
				continue;
			}
			if (beginIndex == endIndex) {
				beginIndex++;
				endIndex++;
			}
			beginIndex++;
		}
		if (beginIndex != N && input[N - 1] - input[beginIndex] < 3) {
			endIndex = N - 1;
			if (res < endIndex - beginIndex + 1) {
				res = endIndex - beginIndex + 1;
			}
		}
		System.out.println(res);
	}
}


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

int main()
{
	int n;
	cin >> n;
	vector<vector<int64_t>> arr(n, vector<int64_t>(3));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			cin >> arr[i][j];
		}
	}
	vector<vector<int64_t>> dp(n, vector<int64_t>(3));
	dp[0][0] = arr[0][0];
	dp[0][1] = arr[0][1];
	dp[0][2] = arr[0][2];
	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			for (int k = 0; k < 3; k++)
			{
				if (j == k)
				{
					continue;
				}
				dp[i][k] = max(dp[i][k], dp[i - 1][j] + arr[i][k]);
			}
		}
	}
	cout << max({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]}) << endl;
	return 0;
}

Measured memory_bytes: 11136
#include<bits/stdc++.h>
using namespace std;
int main()
{
  long long int a[2],b[2],ans=-1000000000000000000000;
  for(int i=0;i<2;i++)
    cin>>a[i];
    for(int i=0;i<2;i++)
    cin>>b[i];
 
  for(int i=0;i<2;i++)
  {
    for(int j=0;j<2;j++)
    {
      ans=max(ans,a[i]*b[j]);
    }
  }
  cout<<ans;
  return 0;
}

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

#define rep(i, n) for (int i = 0; i < n; ++i)
#define all(x) (x).begin(),(x).end()

using ll = long long;
using P = pair<int,int>;
using mp =  map<int,int>;

const int MOD = 1e9 + 7;

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

    int n;
    cin >> n;
    vector<int> v(n);
    vector<int> tmp(n);
    rep(i, n){
        cin >> v.at(i);
        tmp.at(i) = v.at(i);
    }
    sort(all(tmp));

    rep(i, n) {
        if(v.at(i) <= tmp.at(n/2 -1)){
            cout << tmp.at(n/2) << endl;
        }else{
            cout << tmp.at(n/2 - 1) << endl;
        }
    }


    return 0;
}


Measured memory_bytes: 3840
#include<bits/stdc++.h>
using namespace std;
const long long inf = 1e9;
int n, A, B, C, x[10];
int f(int i, int a, int b, int c){
	if(i == n){
		if(!a || !b || !c)
			return inf;
		return abs(A - a) + abs(b - B) + abs(c - C);
	}
	int m1 = f(i + 1, a, b, c);
	m1 = min(m1, f(i + 1, a + x[i], b, c) + (a?10:0));
	m1 = min(m1, f(i + 1, a, b + x[i], c) + (b?10:0));
	m1 = min(m1, f(i + 1, a, b, c + x[i]) + (c?10:0));
	return m1;
}
int main(){
	cin >> n >> A >> B >> C;
	for(int i = 0; i < n; i++)
		cin >> x[i];
	cout << f(0, 0, 0, 0);
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
using namespace std;
const int A=10,B=2,C=1;
int dp[20020],x;
int main()
{
	int cnt[4];
	for(int i=1;i<=3;i++)cin>>cnt[i];
	cin>>x;
	x/=50;
	for(int i=0;i<=cnt[1];i++)
	dp[A*i]=1;
	for(int i=x;i>=0;i--)
	if(dp[i])for(int j=1;j<=cnt[2];j++)
	dp[i+B*j]+=dp[i];
	for(int i=x;i>=0;i--)
	if(dp[i])for(int j=1;j<=cnt[3];j++)
	dp[i+C*j]+=dp[i];
	cout<<dp[x]<<endl;
}

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

public class Main {
	private static void solve(){
	//Implement solution here.
		int n = ni();
		char[] s = next().toCharArray();
		String result = "";
		if(n % 2 == 0) {
			result = "Yes";
			for(int i = 0; i < n / 2; i++) {
				if(s[i] != s[i + (n/2)]) {
					result = "No";
					break;
				}
			}
		} else {
			result = "No";
		}
		System.out.println(result);		
	}

    //Switch input source (stdin/file)
	private static BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
	public static void main(String[] args){
        String debugDataPath = System.getenv("DD_PATH");        
        if(debugDataPath != null){
            try{
            	br = new BufferedReader(new InputStreamReader(new FileInputStream(new File(debugDataPath))));
            }catch(Exception e){
                throw new RuntimeException(e);
            }
        }
        solve();
	}

    //Input read utility
	private static StringTokenizer tokenizer = null;
	public static String next() {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(br.readLine());
			} catch (Exception e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}
    //Get next single int
	private static int ni() {
		return Integer.parseInt(next());
	}
    //Get next single long
	private static long nl() {
		return Long.parseLong(next());
	}
    //Get next single double
	private static double nd() {
		return Double.parseDouble(next());
	}
    //Get next int array from one line
	private static int[] na(int n) {
		int[] a = new int[n];
		for (int i = 0; i < n; i++)
			a[i] = ni();
		return a;
	}
	//Get next char array from one line
	private static char[] ns() {
		return next().toCharArray();
	}
    //Get next long array from one line
	private static long[] nal(int n) {
		long[] a = new long[n];
		for (int i = 0; i < n; i++)
			a[i] = nl();
		return a;
	}
}


Measured memory_bytes: 21332
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ld long double
#define al(a) (a).begin(),(a).end()
#define mk make_pair
#define check cout<<"?"<<endl;

ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;

int main(){
    ll k,a,b; cin>>k>>a>>b;
    if(a+2>=b) cout<<k+1<<endl;
    else{
        if(a-1>=k) cout<<k+1<<endl;
        else{
            k-=a-1;
            cout<<a+(b-a)*(k/2)+k%2<<endl;
        }
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
        using namespace std;
   #define int long long
const int MAX = 510000;
const int MOD = 1000000007;
 vector<pair<int,int>>p;
int dp[(1ll<<9)][100001];
     signed main(){
         cout << std::fixed << std::setprecision(15);
int n;
cin>>n;
int v[n],w[n];
for(int i=0;i<n;i++)cin>>v[i]>>w[i];

for(int i=0;i<w[0];i++)dp[0][i]=0;
for(int i=w[0];i<100001;i++)dp[0][i]=v[0];
for(int i=1;i<n&&i<(1ll<<9);i++){
     for(int j=0;j<w[i];j++)dp[i][j]=dp[(i+1)/2-1][j];
     for(int j=w[i];j<100001;j++)dp[i][j]=max(dp[(i+1)/2-1][j],dp[(i+1)/2-1][j-w[i]]+v[i]);
}
int q,x,l;
cin>>q;
for(int Q=0;Q<q;Q++){
     cin>>x>>l;x--;
    p.clear();
     p.push_back({0,0});
     while(x>=(1ll<<9)){
          int t=p.size();
          for(int i=0;i<t;i++)if(p[i].first+w[x]<=l)p.push_back({p[i].first+w[x],p[i].second+v[x]});
          x=(x+1)/2-1;
     }
     int ans=0;
     for(auto&& i :p)ans=max(ans,dp[x][l-i.first]+i.second);
     cout<<ans<<endl;

}
     }

 


 






    





      

        


Measured memory_bytes: 407744
n,m=map(int,input().split())
p=[]
s=[]
for i in range(m):
	P,S=input().split()
	P=int(P)-1
	p.append(P)
	s.append(S)

wa=[0 for i in range(n)]
ac=[0 for i in range(n)]
for i in range(m):
	if s[i]=="AC":
		ac[p[i]]+=1
	else:
		if ac[p[i]]==0:
			wa[p[i]]+=1

sum_ac=0
pena=0
for i in range(n):
	if ac[i]!=0:
		sum_ac+=1
		pena+=wa[i]
print(sum_ac,end=' ')
print(pena)

Measured memory_bytes: 14976
/*created by tanishk gupta*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define repl(i,a,n) for(long long int i=a;i<n;i++)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef vector<int> VI;
typedef long long int ll;
typedef unsigned long long ull;
//typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll MOD=1e9+7;
const ll mod=1e9+7;
//const llint MOD;
const ll N=(ll)(1e6+1);
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll add(ll a,ll b){return ((a%MOD)+(b%MOD))%MOD;}
ll mul(ll a,ll b){return ((a%MOD)*(b%MOD))%MOD;}
ll sub(ll a,ll b){return ((a%MOD)-(b%MOD)+MOD)%MOD;}
ll binpow(ll x, ll y){ll z = 1;while(y){if(y & 1) z = mul(z, x);x = mul(x, x);y >>= 1;}return z;}
ll inv(int x){return binpow(x, MOD - 2);}
ll divide(ll x, ll y){return mul(x, inv(y));}
ll fact[N];
void precalc(){fact[0] = 1;for(ll i = 1; i < N; i++)fact[i] = mul(fact[i - 1], i);}
ll C(ll n, ll k){return divide(fact[n], mul(fact[k], fact[n - k]));}
//bool prime[N];
//void sieve() {for(int i=2;i<N;i++) {prime[i]=true;}for (int p=2; p*p<=N; p++){if (prime[p] == true){for (int i=p*p; i<=N; i += p)prime[i] = false;}}}
ll legendpow(ll n, ll p){ll total = 0;while (n){n /= p;total += n;}return total;}

//head==================================================================================



int main()
{
IOS;
ll a,b,c,d;
cin>>a>>b>>c>>d;
ll ans=max(a*d,a*c);
ans=max({ans,b*d,b*c});
cout << ans<<endl;
}

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

int main() {
	int setN;
	cin >> setN;
	string A,B;

	for (int i=0;i<setN;i++) {
		cin >> A;
		cin >> B;
		int L[2000][2000] ={};

		for(int j=1;j<A.length()+1;j++) {
			for(int l=1;l<B.length()+1;l++) {
				if(A[j-1] == B[l-1]) {
					L[j][l] = 1+L[j-1][l-1];

				} else {
					L[j][l] = max(L[j-1][l],L[j][l-1]);
				}
				
			}
		}
		/*
		for(int j=0;j<A.length()+1;j++) {
			cout << endl;
			for(int l=0;l<B.length()+1;l++) {
				cout << L[j][l] << " ";
				
			}
		}
		*/

		cout << L[A.length()][B.length()] << endl;


	}
}

Measured memory_bytes: 18760
#include <malloc.h>
#include <stdio.h>

#define MX 1000001
typedef struct Node {
    int u;
    struct Node *next;
} node;
node *edge[MX+2], *cur;
node *New(int a) {
    node *temp = (node *)malloc(sizeof(node));
    temp->next = NULL;
    temp->u = a;
    return temp;
}
node *add(node *root, int a) {
    node *temp = New(a);
    if (root == NULL) return temp;
    temp->next = root;
    return temp;
}
int min(int a, int b) {
    return (a < b) ? a : b;
}
int max(int a, int b) {
    return (a < b) ? b : a;
}
int notHash(int a, int b) {
    int id = min(a, b) * 1000 + max(a, b);
    return id;
}
int n, a, b, in[MX];
void init() {
    for (int i = 0; i <= MX; i++) {
        in[i] = 0;
        edge[i] = NULL;
    }
    cur = NULL;
}
void MRoy() {
    init();
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a);
        for (int j = 0; j < n - 2; j++) {
            scanf("%d", &b);
            int u = notHash(i, a);
            int v = notHash(i, b);
            edge[u] = add(edge[u], v);
            a = b;
            in[v]++;
        }
    }
    int times = 0;
    for (int i = 1; i <= MX; i++) {
        if (in[i] == 0) {
            cur = add(cur, i);
            times++;
        }
    }
    int days = 0, total = 0;
    while (times) {
        days++;
        total += times;
        int t = 0;
        node *after = NULL;
        while(cur!=NULL){
            int u = cur->u;
            node *tm = edge[u];
            while (tm != NULL) {
                int v = tm->u;
                in[v]--;
                if (in[v] == 0) {
                    after = add(after, v);
                    t++;
                }
                tm = tm->next;
            }
            cur = cur->next;
        }
        cur = after;
        times = t;
    }
    if (total == MX) {
        printf("%d\n", days);
    } else
        printf("-1\n");
}
int main() {
    MRoy();
    return 0;
}

Measured memory_bytes: 74368
import java.util.Scanner;


public class Main {
	Scanner sc = new Scanner(System.in);
	
	void run(){
		int w = sc.nextInt();
		int n = sc.nextInt();
		int[][] a = new int[n][2];
		int[] ans = new int[w];
		
		// format yoko
		for(int i = 0; i<n; i++){
			String[] s = sc.next().split(",");
			a[i][0] = Integer.parseInt(s[0]);
			a[i][1] = Integer.parseInt(s[1]);
		}
		
		for(int j = 1; j<=w; j++){
			int t = j;
			for(int k = 0; k<n; k++){
				if(a[k][0] == t){
					t = a[k][1];
				}else if(a[k][1] == t){
					t = a[k][0];
				}
			}
			ans[t-1] = j;
		}
		
		for(int i = 0; i<w; i++){
			System.out.println(ans[i]);
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}

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

using ll = long long;
using ull = unsigned long long;
#define repi(n) for (long long i = 0; i < (n); ++i)
#define repj(n) for (long long j = 0; j < (n); ++j)
#define repk(n) for (long long k = 0; k < (n); ++k)
#define rep(i, a, b) for (auto i = (a); i < (b); ++i)
#define itr(itr) for (auto&& v : (itr))
#define updatemax(t, v) (t = std::max(t, (v)))
#define updatemin(t, v) (t = std::min(t, (v)))

int main() {
  ll n, x, t;
  cin >> n >> x >> t;
  cout << (n + x - 1) / x * t << endl;
}


Measured memory_bytes: 3584
#include <bits/stdc++.h>
#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define ALL(x) x.begin(), x.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
random_device rnd;
mt19937 mt(rnd());
using ll = long long;
using lld = long double;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;
using PII = pair<int, int>;
const int IINF = 1 << 30;
const ll INF = 1ll << 60;
const ll MOD = 1000000007;

int main()
{
    ll n, x, m;
    cin >> n >> x >> m;
    VI buf(m, -1);
    ll cur = x;

    ll ans = 0;
    VL log(m, 0);
    rep(i, n)
    {
        ans += cur;
        log[i] = cur;
        buf[cur] = i;
        cur = (cur * cur) % m;

        if (buf[cur] != -1)
        {
            // cerr << cur << endl;
            int start = buf[cur];
            ll rem = n - i - 1;
            ll tmp = 0;
            rep(j, start, i + 1)
            {
                //  cerr << j << " " << log[j] << endl;
                tmp += log[j];
            }
            //cerr << (i - start + 1) << endl;
            ans += tmp * (rem / (i - start + 1));
            rem %= (i - start + 1);
            rep(j, rem)
            {
                ans += cur;
                cur = (cur * cur) % m;
            }
            cout << ans << endl;
            return 0;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4572
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <vector>
#define REP(i, n) for(int i = 0; i < (n); ++i)
typedef long long ll;
const int MOD = 1000000007;
using namespace std;

int main(){
    int n, ans=0; cin >> n;
    vector<int> h(n+1, 0);
    REP(i, n){
        cin >> h[i+1];
        ans += max(0, h[i+1] - h[i]);
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 256
(let ((s (read-line))
      (x 0))
  (with-input-from-string (in s)
    (setf x (loop :for c := (read-char in nil nil)
                  :for i :from 0
                  :if (char= c #\Space)
                  :return i)))
  (format t "~A~A~%" (subseq s (1+ x)) (subseq s 0 x)))


Measured memory_bytes: 23980
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace atcoder_ensyuu1
{
    class Program
    {
        private static void Main(string[] args)
        {
            int[] values = GetConsole();

            if (values[0] < 1 || values[0] > 100)
            {
                Console.WriteLine("error");
                return;
            }

            if (values[1] < 0 || values[1] > 4111)
            {
                Console.WriteLine("error");
                return;
            }

            int rating = values[1];
            if (values[0] < 10)
            {
                rating = rating + 100 * (10 - values[0]);
            }
            Console.WriteLine(rating);
        }

        private static int[] GetConsole()
        {
            return Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        }

        private static int[] GetConsole2()
        {
            //入力値例"3 4"を、' (スペース)'で文字を区切り、string型の文字列配列{"3", "4"}に変換
            string[] strs = Console.ReadLine().Split(' ');
            //int型の配列sssを用意
            int[] sss = new int[2];
            //文字列配列{"3", "4"}をint型配列{3, 4}に変換
            for (int i = 0; i < strs.Length; i++)
            {
                sss[i] = int.Parse(strs[i]);
            }
            return sss;
        }
    }
}



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

int main() {

#ifdef _test
    freopen( "in.txt", "r", stdin);
#endif

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


Measured memory_bytes: 19016
array = Array.new

2.times do
    val = gets.split.map!{|i| i.to_i}
    array.push(val)
end

h = array[0][0]
a = array[1]

a.each{|num|
    h = h - num
}

if h <= 0
    puts("Yes")
else
    puts("No")
end


Measured memory_bytes: 7300
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <queue>

#define rep(i,n) for(int i=0;i<n;i++)
#define dup(x,y) (((x)+(y)-1)/(y)) // dup * y >= x なる最小のdup.
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
using Graph = vector<vector<int>>;

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

  bool ans = false;
  if(a==b) {
    if(b!=c) ans = true;
  } else if(b==c) {
    if(c!=a) ans = true;
  } else if(c==a) {
    if(a!=b) ans = true;
  }
  
  if(ans) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;
}

Measured memory_bytes: 256
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase

/*
cout<<fixed<<setprecision(20);
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1000000007;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
int main(void){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,m,i,j,ans=0;cin>>n>>m;
	vector<int>dp(n);
	vector<vector<int>>go(n);
	vector<int>zi(n);
	while(m--){
		int x,y;cin>>x>>y;x--;y--;
		go[x].pub(y);zi[y]++;
	}
	queue<int>que;
	for(i=0;i<n;i++){if(zi[i]==0){que.push(i);}}
	while(que.size()){
		int t=que.front();que.pop();
		for(auto it:go[t]){
			maxeq(dp[it],dp[t]+1);
			maxeq(ans,dp[it]);
			zi[it]--;
			if(zi[it]==0){que.push(it);}
		}
	}
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 6528
#include"bits/stdc++.h"
using namespace std;
#define LL long long
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define PB push_back
#define MP make_pair
#define all(x) x.begin(),x.end()
#define MOD 1000000007

int N;
bool isOK(string S){
	string AGC = "AGC";
	if(search(S.begin(), S.end(), AGC.begin(), AGC.end()) != S.end()) return false;
	swap(S[0],S[1]);
	if(search(S.begin(), S.end(), AGC.begin(), AGC.end()) != S.end()) return false;
	swap(S[0],S[1]);
	swap(S[1],S[2]);
	if(search(S.begin(), S.end(), AGC.begin(), AGC.end()) != S.end()) return false;
	swap(S[1],S[2]);
	swap(S[2],S[3]);
	if(search(S.begin(), S.end(), AGC.begin(), AGC.end()) != S.end()) return false;
	return true;
}
map<pair<int,string>, LL> dp;
LL solve(int now, string mae){
	if(now == N) return 1;
	if(dp.count(MP(now,mae)) == 1) return dp[MP(now,mae)];
	LL ans = 0;
	if(isOK(mae+"A")) ans += solve(now+1, mae.substr(1,2)+"A");
	if(isOK(mae+"G")) ans += solve(now+1, mae.substr(1,2)+"G");
	if(isOK(mae+"C")) ans += solve(now+1, mae.substr(1,2)+"C");
	if(isOK(mae+"T")) ans += solve(now+1, mae.substr(1,2)+"T");
	return dp[MP(now,mae)] = ans % MOD;
}

int main(){
	cin >> N;
	cout << solve(0,"...") << endl;

	return 0;
}


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

using namespace std;

#ifdef DGC
#include "debug.h"
#else
#define debug(...) 9715
#endif
typedef long long ll;
typedef long double ld;
typedef complex<ll> point;
#define F first
#define S second



int main()
{
	#ifdef DGC
		//freopen("a.in", "r", stdin);
		//freopen("b.out", "w", stdout);
	#endif

	ios_base::sync_with_stdio(0), cin.tie(0);

	int x;
	cin >> x;

	for (; ; ++x)
	{
		bool ok = true;
		for (int i = 2; i < x; ++i)
			if (x % i == 0)
			{
				ok = false;
				break;
			}
		if (ok)
		{
			cout << x << "\n";
			break;
		}
	}

	return 0;
}



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

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

int main() {
    int N;
    cin >> N;
    vector<int> V(N);
    vector<int> C(N);

    rep(i, N)
        cin >> V.at(i);
    rep(i, N)
        cin >> C.at(i);

    int ans = 0;
    rep(i, N) {
        if (V.at(i) > C.at(i))
            ans += (V.at(i) - C.at(i));
    }
    cout << ans << endl;
}

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







int main(){
  


  int64_t n,k;
  cin>>n>>k;
  
  vector<int64_t> data(n+1);
  
  for (int64_t i=1;i<=n;i++){
    int64_t tmp;
    cin>>tmp;
    data.at(i)=tmp;
  }
  

  vector<int64_t> myrep(1,1);
  

  
  
  set<int64_t> check;
  check.insert(1);
  
  int64_t mymemory;
  int64_t j;
  

  
  for (int64_t i=0;i<n;i++){
    int64_t tmp=myrep.at(i);
    if (check.find(data.at(tmp))!=check.end()){
      mymemory=i;
      
      
      for (int k=0;k<n;k++){
        if (myrep.at(k)==data.at(tmp)){
          j=k; 
          break;
        }
      }
      
      break;
    }
    
      
 
    
        

    else {
      myrep.push_back(data.at(tmp));
      check.insert(data.at(tmp));
    }
  }

  
  
 
  int64_t repsize=mymemory-j+1;
  
  int64_t tmp;
  
  if (k>=j){
    tmp=((k-j)%repsize)+j;
  }
  else {
    tmp=k;
  }
  
  

  
  cout<<myrep.at(tmp)<<endl;
  

      
  
  
  
  
  
    
  
  
  
}

Measured memory_bytes: 15364
#include<iostream>
#include<string.h>
#include<algorithm>
#include<queue>
#include<vector>

#define MAX 5000

using namespace std;

void input();

int lose[MAX + 1];
int n, m, w[100000], l[100000];
queue<int> q;

int main() {

	bool yes = false;
	input();

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

		int t = 0, cnt = 0;
		for (int j = 1; j <= n; j++) {
			if (lose[j] == 0) {
				t = j;
				cnt++;

			}
		}
		if (cnt >= 2) yes = true;
		lose[t] = 5000 ;
		q.push(t);
		for (int j = 0; j < m; j++) if (w[j]==t) lose[l[j]]--;

	}
	for (int i = 0; i < n; i++) {
		int ans = q.front();
		cout << ans << endl;
		q.pop();
	}
	if (yes == true) cout << 1 << endl;
	else cout << 0 << endl;

	//cin >> n;
	return 0;
}

void input() {

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> w[i] >> l[i];
		lose[l[i]]++;

	}
}



Measured memory_bytes: 3960
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 1000000000000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


#define SIZE 1000005

string line;
ll dp[SIZE][2];

int main(){

	cin >> line;
	line = '0'+line;

	int N = line.length();

	for(int i = 0; i <= N; i++){
		dp[i][0] = HUGE_NUM;
		dp[i][1] = HUGE_NUM;
	}

	dp[0][0] = 0;

	for(int i = 0; i < N; i++){

		ll num = line[i]-'0';

		dp[i+1][0] = min(dp[i+1][0],dp[i][0]+num);
		dp[i+1][1] = min(dp[i+1][1],dp[i][0]+num+1);

		dp[i+1][0] = min(dp[i+1][0],dp[i][1]+10-num);
		dp[i+1][1] = min(dp[i+1][1],dp[i][1]+9-num);
	}

	printf("%lld\n",dp[N][0]);

	return 0;
}


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

const int Max = 100;
const int Infty = (1 << 21);
const int white = 0;
const int gray = 1;
const int black = 2;

int n, M[Max][Max];
int d[Max], p[Max], color[Max];


void dijkstra(int s){
    for(int i=0; i<n; i++){
        d[i] = Infty;
        p[i] = -1;
        color[i] = white;
    }
    d[s] = 0;
    int minv, u;
    while(1){
        minv = Infty;
        u = -1;
        for(int i=0; i<n; i++){
            if(color[i] != black && d[i] < minv){
                u = i;
                minv = d[i];
            }
        }
        if(u == -1) break;
        color[u] = black;
        for(int v=0; v<n; v++){
            if(color[v] != black && M[u][v] != Infty){
                if(d[v] > d[u] + M[u][v]){
                    d[v] = d[u] + M[u][v];
                    p[v] = u;
                    color[v] = gray;
                }
            }
        }
    }
    return;
}


int main(){
    cin >> n;
    int u, k, v, c;
    for(int i=0; i<n; i++){
        for(int l=0; l<n; l++){
            M[i][l] = Infty;
        }
        cin >> u >> k;
        for(int j=0; j<k; j++){
            cin >> v >> c;
            M[u][v] = c;
        }
    }

    dijkstra(0);
    for(int i=0; i<n; i++){
        cout << i << " " << d[i] << endl;
    }

    return 0;
}


Measured memory_bytes: 3132
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <cassert>
#include <bitset>
using namespace std;
#define MOD 1000000007

long long dp[301][301][301];

void add(long long &x, long long y){
    x = (x + y) % MOD;
}

int main(){
    int N, M;
    cin >> N >> M;
    vector<vector<pair<int, int>>> lxs(301);
    for(int i=0; i<M; i++){
        int l, r, x;
        cin >> l >> r >> x;
        if(l == r){
            if(x > 1){
                cout << 0 << endl;
                return 0;
            }
        }else lxs[r].emplace_back(l, x);
    }

    dp[0][0][0] = 1;
    dp[1][0][0] = 1;
    dp[0][1][0] = 1;
    dp[0][0][1] = 1;
    for(int k=1; k<N; k++){
        for(int i=0; i<k; i++){
            for(int j=0; j<k; j++){
                add(dp[k+1][i][j], dp[k][i][j]);
                add(dp[k][k+1][j], dp[k][i][j]);
                add(dp[k][i][k+1], dp[k][i][j]);

                add(dp[i][k+1][j], dp[i][k][j]);
                add(dp[k+1][k][j], dp[i][k][j]);
                add(dp[i][k][k+1], dp[i][k][j]);

                add(dp[i][j][k+1], dp[i][j][k]);
                add(dp[i][k+1][k], dp[i][j][k]);
                add(dp[k+1][j][k], dp[i][j][k]);
            }
        }
        for(auto lx : lxs[k+1]){
            int l, x;
            tie(l, x) = lx;
            for(int i=0; i<=k; i++){
                for(int j=0; j<=k; j++){
                    if(
                        ( x==1 && (i >= l || j >= l) ) ||
                        ( x==2 && ( (i >= l && j >= l) || (i < l && j < l) ) ) ||
                        ( x==3 && ( (i < l || j < l) ) )
                      ){
                        dp[k+1][i][j] = 0;
                        dp[i][k+1][j] = 0;
                        dp[i][j][k+1] = 0;
                    }
                }
            }
        }
    }
    long long ans = 0;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            add(ans, dp[N][i][j]);
            add(ans, dp[i][N][j]);
            add(ans, dp[i][j][N]);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 213376
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define INF 1e9;
using namespace std;
using ll = long long;
int main() {
    ll N , A , B;
    cin >> N >> A >> B;
    if(A % 2 == 0 && B % 2 == 0){
        cout << (B - A) / 2 << endl;
    }
    else if(A % 2 == 1 && B % 2 == 1){
        cout << (B - A) / 2 << endl;
    }
    else{
        cout << min(A - 1 , N - B) + 1 + (B - A - 1) / 2 << endl;
    }
}


Measured memory_bytes: 3532
#include<iostream>
using namespace std;
int main()
{
  int a,b,k;
  cin>>a>>b;
  if(b==1)
    k=0;
  else if(b>1 && b<=a)
    k=1;
  else if(b>a && b<=2*a-1)
    k=2;
  else
  {k=2;
    while(a+(k-1)*(a-1)<b)
  {
    k++;
  }
  }
  cout<<k;
  return 0;
}


Measured memory_bytes: 256
#052_C
n = int(input())
mod = 10 ** 9 + 7

div = [0 for _ in range(n)]
for i in range(1, n+1):
    x = i
    for j in range(2, x+1):
        while x % j == 0:
            x //= j
            div[j-1] += 1
ans = 1
for i in range(n):
    ans = ans * (div[i] + 1) % mod

print(ans)

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

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define DUMP(v) REP(aa, (v).size()) { cout << v[aa]; if (aa != v.size() - 1)cout << " "; else cout << endl; }
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll max(ll a, int b) { return max(a, ll(b)); }
ll max(int a, ll b) { return max(ll(a), b); }
ll min(ll a, int b) { return min(a, ll(b)); }
ll min(int a, ll b) { return min(ll(a), b); }
///(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)(´・ω・`)///


struct Edge { int to, cap, rev, cost; };
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;




struct MaxFlow {
	Graph G;
	vi level, iter;
	MaxFlow(Graph g) {
		int n = g.size();
		level.resize(n);
		iter.resize(n);
		G = g;
	}
	void add_edge(int from, int to, int cap, int cost = 0) {
		G[from].push_back(Edge{ to, cap, (int)G[to].size(),cost });
		G[to].push_back(Edge{ from,0,(int)G[from].size() - 1,-cost });
	}

	void bfs(int s) {
		fill(ALL(level), -1);
		queue<int> q;
		level[s] = 0;
		q.push(s);
		while (!q.empty()) {
			int v = q.front(); q.pop();
			for (int i = 0; i < G[v].size(); i++) {
				Edge &e = G[v][i];
				if (e.cap > 0 && level[e.to] < 0) {
					level[e.to] = level[v] + 1;
					q.push(e.to);
				}
			}
		}
	}
	int dfs(int v, int t, int f) {
		if (v == t)return f;
		for (int &i = iter[v]; i < G[v].size(); i++) {
			Edge &e = G[v][i];
			if (e.cap > 0 && level[v] < level[e.to]) {
				int d = dfs(e.to, t, min(f, e.cap));
				if (d > 0) {
					e.cap -= d;
					G[e.to][e.rev].cap += d;
					return d;
				}
			}
		}
		return 0;
	}
	int max_flow(int s, int t) {
		int flow = 0;
		for (;;) {
			bfs(s);
			if (level[t] < 0)return flow;
			fill(ALL(iter), 0);
			int f;
			while ((f = dfs(s, t, INF)) > 0) {
				flow += f;
			}
		}
	}
};

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	Graph g(n);
	MaxFlow f(g);
	REP(i, m) {
		int a, b, c;
		cin >> a >> b >> c;
		f.add_edge(a, b, c);
	}
	cout << f.max_flow(0, n - 1) << endl;
}

Measured memory_bytes: 3248
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
	char a, b;

	cin >> a >> b;

	if (a == 'H') {
		if (b == 'H') {
			cout << "H" << endl;
		}
		else {
			cout << "D" << endl;
		}
	}
	else {
		if (b == 'H') {
			cout << "D" << endl;
		}
		else {
			cout << "H" << endl;
		}
	}

}

Measured memory_bytes: 256
#149_E. 2分探索. 神.ちょい変えた版





















N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort()
A.reverse()

def PairCount_and_TotalSum_over(x):
  c,k,si,i = [0,0,0,0]
  for j in reversed(range(N)):
    while i<N and A[i]+A[j]>=x:
      si += A[i]
      i += 1
    c += i
    k += si + A[j]*i
    
  return (c, k)

def binary_search(l, u):
  m = (l+u)//2
  c, k = PairCount_and_TotalSum_over(m)
  if c<M:
    return binary_search(l, m)
  else:
    if l==m:
      print(k-(c-M)*l)
    else:
      return binary_search(m, u)

binary_search(0, A[0]*2+1)


Measured memory_bytes: 14388
#include <stdio.h>
int signal(int *da,int set){
	if(set==1){
		if(*da==0){
			*da=1;
			return 1;
		}
		else{
			*da=1;
			return 0;
		}
	}
	else {
		if(*da==0){
			*da=0;
			return 0;
		}
		else{
			*da=0;
			return 1;
		}
	}
}

class seg{
public:
	int a,b,c,d,e,f,g;
	int da,db,dc,dd,de,df,dg;
	void empty();
	void set(int num);
	void Set(int num);
};
void seg::empty(){
  /*switch(num){
  case 0:
	  a=b=c=d=e=f=1;
	  g=0;
	  break;
  case 1:
	  b=c=1;
	  a=d=e=f=g=0;
	  break;
  case 2:
	  a=b=d=e=g=1;
	  c=f=0;
	  break;
  case 3:
	  a=b=c=d=g=1;
	  f=e=0;
	  break;
  case 4:
	  b=c=f=g=1;
	  a=e=d=0;
	  break;
  case 5:
	  a=c=d=f=g=1;
	  b=e=0;
	  break;
  case 6:
	  a=c=d=e=f=g=1;
	  b=0;
  case 7:
	  a=b=c=f=1;
	  e=d=g=0;
	  break;
  case 8:
	  a=b=c=d=e=f=g=1;
	  break;
  case 9:
	  a=b=c=d=f=g=1;
	  e=0;
	  break;
  }*/
	a=b=c=d=e=f=g=0;
	da=a;db=b;dc=c;dd=d;de=e;df=f;dg=g;
	//printf("%d%d%d%d%d%d%d%d\n",g,f,e,d,c,b,a);
}

void seg::set(int num){
	switch(num){
	case 0:
		a = signal(&da,1);
		b = signal(&db,1);
		c = signal(&dc,1);
		d = signal(&dd,1);
		e = signal(&de,1);
		f = signal(&df,1);
		g = signal(&dg,0);
		break;
	case 1:
		a = signal(&da,0);
		b = signal(&db,1);
		c = signal(&dc,1);
		d = signal(&dd,0);
		e = signal(&de,0);
		f = signal(&df,0);
		g = signal(&dg,0);
		break;
	case 2:
		a = signal(&da,1);
		b = signal(&db,1);
		c = signal(&dc,0);
		d = signal(&dd,1);
		e = signal(&de,1);
		f = signal(&df,0);
		g = signal(&dg,1);
		break;
	case 3:
		a = signal(&da,1);
		b = signal(&db,1);
		c = signal(&dc,1);
		d = signal(&dd,1);
		e = signal(&de,0);
		f = signal(&df,0);
		g = signal(&dg,1);
		break;
	case 4:
		a = signal(&da,0);
		b = signal(&db,1);
		c = signal(&dc,1);
		d = signal(&dd,0);
		e = signal(&de,0);
		f = signal(&df,1);
		g = signal(&dg,1);
		break;
	case 5:
		a = signal(&da,1);
		b = signal(&db,0);
		c = signal(&dc,1);
		d = signal(&dd,1);
		e = signal(&de,0);
		f = signal(&df,1);
		g = signal(&dg,1);
		break;
	case 6:
		a = signal(&da,1);
		b = signal(&db,0);
		c = signal(&dc,1);
		d = signal(&dd,1);
		e = signal(&de,1);
		f = signal(&df,1);
		g = signal(&dg,1);
		break;
	case 7:
		a = signal(&da,1);
		b = signal(&db,1);
		c = signal(&dc,1);
		d = signal(&dd,0);
		e = signal(&de,0);
		f = signal(&df,1);
		g = signal(&dg,0);
		break;
	case 8:
		a = signal(&da,1);
		b = signal(&db,1);
		c = signal(&dc,1);
		d = signal(&dd,1);
		e = signal(&de,1);
		f = signal(&df,1);
		g = signal(&dg,1);
		break;
	case 9:
		a = signal(&da,1);
		b = signal(&db,1);
		c = signal(&dc,1);
		d = signal(&dd,1);
		e = signal(&de,0);
		f = signal(&df,1);
		g = signal(&dg,1);
		break;
	}
	printf("%d%d%d%d%d%d%d\n",g,f,e,d,c,b,a);
}

	
int main(){
	int num,n;
	seg seg;
	seg.empty();
	scanf("%d",&n);
	while(n!=-1){
		while(n--){
			scanf("%d",&num);
			seg.set(num);
		}
		seg.empty();
		scanf("%d",&n);
	}
	return 0;
}
		
		
	

Measured memory_bytes: 1028
import qualified Data.IntSet as S

main :: IO ()
main = do
    [n, _] <- map read . words <$> getLine
    ds <- S.fromList . map read . words <$> getLine
    print $ solve n ds
 
solve :: Int -> S.IntSet -> Int
solve n ds = head $ filter (favo ds) [n..]

favo :: S.IntSet -> Int -> Bool
favo ds = S.null . S.intersection ds . S.fromList . map (read . pure) . show


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

int main() {
  int n;
  cin >> n;
  for(int i=n;i>=1;i--) {
    if( (i&(i-1)) == 0) {
      cout << i << endl;
      return 0;
    }
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
#define F first
#define S second
#define MP make_pair
#define int long long
#define INF long(1e18)
using namespace std;
typedef pair<int, int> P;
typedef pair<P, int> PP;


int n, m, k, s, pp, q, ans[100001];
int dead[100001];
vector<int> road[100001], root;
inline int in() {
	int temp;
	scanf("%ld", &temp);
	return temp;
}
void bfs(int sta)
{
	queue<P> que;
	que.push(MP(sta, 0));
	dead[sta] = -1;
	while (!que.empty())
	{
		P p = que.front();
		que.pop();
		if (p.S == s) continue;
		for (int i = 0; i < road[p.F].size(); i++)
		{
			if (!dead[road[p.F][i]] || dead[road[p.F][i]] > p.S + 1)
			{
				que.push(MP(road[p.F][i], p.S + 1));
				dead[road[p.F][i]] = p.S + 1;
			}
		}
	}
}
void dijkstra() {
	priority_queue<P> pq;
	pq.push(MP(0, 1));
	ans[1] = 0;
	while (!pq.empty())
	{
		P p = pq.top();
		pq.pop();
		for (int i = 0; i < road[p.S].size(); i++)
		{
			if (dead[road[p.S][i]] == -1) continue;
			if (!dead[road[p.S][i]] && ans[road[p.S][i]] < p.F - pp)
			{
				pq.push(MP(p.F - pp, road[p.S][i]));
				ans[road[p.S][i]] = p.F - pp;
			}
			else if (ans[road[p.S][i]] < p.F - q) {
				pq.push(MP(p.F - q, road[p.S][i]));
				ans[road[p.S][i]] = p.F - q;
			}
		}
	}
}
signed main()
{
	cin >> n >> m >> k >> s >> pp >> q;
	for (int i = 0; i < k; i++)
	{
		root.push_back(in());
	}
	for (int i = 0; i < m; i++)
	{
		int a = in(), b = in();
		road[a].push_back(b);
		road[b].push_back(a);
	}
	for (int i = 0; i < k; i++)
	{
		bfs(root[i]);
	}
	fill(ans, ans + n + 1, -INF);
	dijkstra();
	if (!dead[n])
		cout << -ans[n] - pp << endl;
	else
		cout << -ans[n] - q << endl;
}

Measured memory_bytes: 13668
#include<bits/stdc++.h>
using namespace std;
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pint;
typedef vector<long long> vlong;
#define vpush(a,x) a.push_back(x);
#define rep(i, n) REP(i, 0, n)
#define all(v) v.begin(), v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define INF 2e9
signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int h,w,max=0;
    cin>>h>>w;
    vector<vector<int> > c(h+1,vector<int>(w+1));
    REP(i,1,h+1){
	REP(j,1,w+1){
	    cin>>c[i][j];
	}
    }
    vector<vector<int> > count(h+1,vector<int>(w+1));
    REP(i,1,h+1){
	REP(j,1,w+1){
	    if(c[i][j]==0){
		int min=9999999;
		if(min>count[i-1][j]){
		    min=count[i-1][j];
		}
		if(min>count[i-1][j-1]){
		    min=count[i-1][j-1];
		}
		if(min>count[i][j-1]){
		    min=count[i][j-1];
		}
		count[i][j]=min+1;
	    }
	    if(count[i][j]>max){
		max=count[i][j];	
	    }
	}
    }
    cout<<max*max<<'\n';
    return(0);
}



Measured memory_bytes: 18320
n,k = map(int,input().split())
lst1 = list(map(int,input().split()))

import fractions as math
#リスト l の最大公約数
def gcdlist(l):
    a = l[0]
    for i in range(len(l)):
        a = math.gcd(a,l[i])
        if a == 1:
            break
    return a


p = gcdlist(lst1)

if max(lst1) < k:
    print("IMPOSSIBLE")

elif k in lst1:
    print("POSSIBLE")

elif k%p==0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

Measured memory_bytes: 81436
#include<bits/stdc++.h>
#define to edge[i].v
#define mp make_pair
#define rint register int
#define debug(x) cerr<<#x<<"="<<x<<endl
#define fgx cerr<<"-------------"<<endl
#define N 100010
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
int a[N]; ll pre[N],suf[N]; char c[N];
int main()
{	ios::sync_with_stdio(false);
	int n; ll ans=0; cin>>n>>a[1]; pre[1]=a[1];
	for(rint i=2;i<=n;i++) cin>>c[i]>>a[i];
	for(rint i=2;i<=n;i++) pre[i]=(c[i]=='-')?pre[i-1]-a[i]:pre[i-1]+a[i];
	for(rint i=n;i>=1;i--) suf[i]=suf[i+1]+a[i];
	for(rint i=1,j;i<=n;i++)
	if(c[i]=='-')
	{	ll sum=a[i];
		for(j=i+1;j<=n&&c[j]=='+';j++) sum+=a[j];
		ans=max(ans,pre[i-1]+suf[j]-sum);
	}
	cout<<max(ans,pre[n]);
	return 0;
}


Measured memory_bytes: 2304
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <iomanip>
#include <stdlib.h>
#include <queue>

using namespace std;

const int nmax = 1e9 + 7;
typedef long long ll;

int main(){

  string S; cin >> S;

  int length = S.length();

  ll DP[length][13];

  for (int i = 0; i < length; i++){
    for (int j = 0; j < 13; j++){
      DP[i][j] = 0;
    }
  }
  

  if (S[0] == '?'){
    for (int i = 0; i <= 9; i++){
      DP[0][i] = 1;
    }
  }else{
    int A = S[0] - '0';
    DP[0][A] = 1;
  }
  
  for (int i = 1; i < length; i++){
    if (S[i] == '?'){
      for(int A = 0; A < 10; A++){
        for (int j = 0; j < 13; j++){
          DP[i][(j * 10 + A) % 13] += DP[i - 1][j];
        }
      }
    }else{
      int A = S[i] - '0';
      for (int j = 0; j < 13; j++){
        DP[i][(j * 10 + A) % 13] += DP[i - 1][j];
      }
    }

    for (int j = 0; j < 13; j++){
      DP[i][j] = DP[i][j] % nmax;
    }
  }
  cout << DP[length - 1][5] << endl;

  return 0;
}


Measured memory_bytes: 10624
#pragma region header
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cctype>
#include <assert.h>
#include <time.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#include <math.h>
#include <cstring>
#include <array>
// ===============================================================
//using系
#pragma region header
using namespace std;
using lint = long long;
using ld = long double;
using ulint = unsigned long long;
const int dx[] = { 1,0,-1,0 };
const int dy[] = { 0,1,0,-1 };
constexpr lint mod = 1000000007;
constexpr long double pi = 3.141592653589793238462643383279;
#pragma endregion
// ========================================================================
//define
#define INF (lint)10000000000000000;
#define mod (int)1000000007
#pragma region header
template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
	if (lhs > rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
	if (lhs < rhs) {
		lhs = rhs;
		return 1;
	}
	return 0;
}
#pragma endregion
#pragma endregion



int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s, t; cin >> s >> t;
	vector<string> d;
	for (int i = 0; i < (int)s.length(); i++) {
		if (i + t.length() > s.length()) break;
		string c = s;
		for (int j = 0; j < (int)t.length(); j++) {
			if (s[i + j] != '?' && t[j] != s[i + j]) goto Cyan;
			c[i + j] = t[j];
		}
		for (int j = 0; j < (int)c.length(); j++) if (c[j] == '?') c[j] = 'a';
		d.emplace_back(c);
	Cyan:;
	}
	sort(d.begin(), d.end());
	if (d.size() == 0) cout << "UNRESTORABLE" << endl;
	else cout << d[0] << endl;

	return 0;
}

Measured memory_bytes: 3644
def janken(aite):
    tokuten = 0
    kachi = 1
    if aite[0]=='r':
        tokuten += pa_p
    elif aite[0]=='s':
        tokuten += gu_r
    else:
        tokuten += choki_s
    #print(0,aite[0],tokuten,kachi)
    for i in range(1,len(aite)):
        if aite[i-1]!=aite[i] or kachi==0:
            kachi = 1
            if aite[i]=='r':
                tokuten += pa_p
            elif aite[i]=='s':
                tokuten += gu_r
            else:
                tokuten += choki_s
            #print(i,aite[i],tokuten,kachi)
        else:
            kachi=0
    return tokuten

n,k = map(int,input().split())
gu_r,choki_s,pa_p = map(int,input().split())
t = str(input())
kaisu = {}
memo = [str('') for i in range(k)]
for i in range(n):
    kaisu.setdefault(t[i],0)
    kaisu[t[i]] += 1
    #print(i%k)
    memo[i%k] += t[i]
ans = 0
for i in range(len(memo)):
    ans += janken(memo[i])
#print(kaisu)
print(ans)


Measured memory_bytes: 12664
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=25;
int n,a[maxn];
ll dfs(int l,int r,int fl,int fr)
{
	if(l+1==r) return 0;
	ll ans=0x3f3f3f3f3f3f3f3f;
	for(int k=l+1;k<r;k++)
		ans=min(ans,dfs(l,k,fl,fl+fr)+dfs(k,r,fl+fr,fr)+(ll)(fl+fr)*a[k]);
	return ans;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	printf("%lld\n",dfs(1,n,1,1)+a[1]+a[n]);
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
const int N=2e5+20;
const int M=5e2+20;
const ll inf=2e15;
ll n,x[N],L,Q;
ll d[30][N];
void init()
{
	for(ll i=1;i<=20;i++)
	{
		for(int j=1;j<=N;j++)
		{
			d[i][j]=d[i-1][d[i-1][j]];
		}
	}
}
int main()
{
	while(cin>>n)
	{
		for(int i=1;i<=n;i++)
			scanf("%I64d",&x[i]);
		cin>>L>>Q;
		for(int i=1;i<=n;i++)
		{
			int l=i+1,r=n;
			while(l<=r)
			{
				int mid=(l+r)>>1;
				if(x[mid]-x[i]<=L)
					l=mid+1;
				else
					r=mid-1;
			}
			d[0][i]=l-1;
		}
		init();
		ll u,v;
		while(Q--)
		{
			scanf("%I64d%I64d",&u,&v);
			if(u>v)
				swap(u,v);	
			ll ans=0;
			for(ll i=20;i>=0;i--)
			{
				if(d[i][u]<v)
					ans+=(1ll<<i),u=d[i][u];
			}
			ans++;
			cout<<ans<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 37504
import java.util.*;

public class Main {

    public static List<List<Integer>> switchList;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        sc.close();

        boolean isBad = false;
        char last = Character.MIN_VALUE;
        for (int i = 0; i < S.length(); i++) {
            char a = S.charAt(i);
            if (a == last) {
                isBad = true;
                break;
            }
            last = a;
        }
        if (isBad) {
            System.out.println("Bad");
        } else {
            System.out.println("Good");
        }
    }

}

Measured memory_bytes: 22608