akhauriyash/Code-Regression huggingface dataset:
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <valarray>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <iomanip>
#include <map>
#include <set>
#include <list>
#include <limits>
#include <numeric>
#include <utility>
#include <deque>
#include <unordered_set>
#include <unordered_map>
#include <regex>
#include <array>
#include <bitset>
#include <complex>
#include <tuple>
#include <random>

using namespace std;
using ll = long long;
const int INF = 1e9;
const ll MOD = 1e9 + 7;

int main()
{
  ll a, b, k;
  cin >> a >> b >> k;
  if (a <= k)
  {
    k -= a;
    a = 0;
    if (b <= k)
    {
      k -= b;
      b = 0;
    }
    else
      b -= k;
  }
  else
    a -= k;

  cout << a << ' ' << b << endl;

  return 0;
}


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

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define x first
#define y second

#ifdef LOCAL
#include "/Users/swad/Desktop/CP/debug.h"
#endif

// const int N = int(1e5) + 10;
// const int MOD = int(1e9) + 7;

int n, m;
vector<vector<int>> adj;
vector<int> dp1, dp2;

void dfs1(int at, int p) {
	dp1[at] = 1;
	for (int to : adj[at]) if (to != p) {
		dfs1(to, at);
		dp1[at] = (ll)dp1[at] * dp1[to] % m;
	}
	++dp1[at] %= m;
}

void dfs2(int at, int p, int carry) {
	dp2[at] = (ll)(dp1[at] + m - 1) * carry % m;

	if (p) adj[at].erase(find(adj[at].begin(), adj[at].end(), p));
	int sz = adj[at].size();

	vector<int> pref(sz + 2), suff(sz + 2);
	pref[0] = suff[sz + 1] = 1;
	for (int i = 0; i < sz; i++) pref[i + 1] = (ll)pref[i] * dp1[adj[at][i]] % m;
	for (int i = sz - 1; ~i; i--) suff[i + 1] = (ll)suff[i + 2] * dp1[adj[at][i]] % m;

	for (int i = 0; i < sz; i++) dfs2(adj[at][i], at, ((ll)pref[i] * suff[i + 2] % m * carry % m + 1) % m);
}

int main() {
	#ifdef LOCAL
	freopen("in", "r", stdin);
	freopen("out", "w", stdout);
	#endif

	scanf("%d %d", &n, &m);
	adj.resize(n + 1);
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	dp1.resize(n + 1); dfs1(1, 0);
	dp2.resize(n + 1); dfs2(1, 0, 1);

	for (int i = 1; i <= n; i++) printf("%d\n", dp2[i]);

	return 0;
}

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

using namespace std;

typedef long long I64;

const int NMAX = 100;

int N;
int v[2*NMAX+2][NMAX+2];
int used[NMAX+2];
int ans[NMAX+2];
int a[5], b[5];

int main()
{
    for( int i = 1;  i <= 3;  ++i ) {
        for( int j = 1;  j <= 3;  ++j ) cin >> v[i][j];
    }
    b[1] = v[1][1];
    a[2] = v[2][1] - b[1];
    a[3] = v[3][1] - b[1];
    b[2] = v[1][2] - a[1];
    b[3] = v[1][3] - a[1];
    for( int i = 1;  i <= 3;   ++i ) for( int j = 1;  j <= 3;  ++j ) {
        if( a[i] + b[j] != v[i][j] ) {
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
    return 0;
}


Measured memory_bytes: 256
N,M= map(int,input().split())

x = []
y = []
for i in range(M):
  xi, yi = input().split()
  x.append(int(xi))
  y.append(int(yi))

L=[]
for i in range(N):
  L.append(1)
R=[1]
for i in range(N-1):
  R.append(0)
#print(R) 

#print('     ','R',R,'L',L) 
for i in range(M):
  if R[x[i]-1]==1 and L[x[i]-1]==1:
    R[x[i]-1]=0
    L[x[i]-1]=0
    R[y[i]-1]=1
    L[y[i]-1]=L[y[i]-1]+1
  elif R[x[i]-1]==1 and L[x[i]-1]>=1:
    L[x[i]-1]=L[x[i]-1]-1
    R[y[i]-1]=1
    L[y[i]-1]=L[y[i]-1]+1
  elif R[x[i]-1]==0 and L[x[i]-1]>=1:
    L[x[i]-1]=L[x[i]-1]-1
    L[y[i]-1]=L[y[i]-1]+1
  #print(i+1,x[i],y[i],'R',R,'L',L) 
    

print(R.count(1))


Measured memory_bytes: 12556
N = int(input())
N_2 = N//2

v = list(map(int, input().split()))
v_odd = [v[2*i+1] for i in range(N_2)]
v_evn = [v[2*i] for i in range(N_2)]

lst_odd = [0] * 100001
lst_evn = [0] * 100001

for vi in v_odd:
  lst_odd[vi] += 1
  
for vi in v_evn:
  lst_evn[vi] += 1
  
tpl_odd = [(lst_odd[i+1], i+1) for i in range(100000)]
tpl_evn = [(lst_evn[i+1], i+1) for i in range(100000)]

tpl_odd.sort(reverse=True)
tpl_evn.sort(reverse=True)
if tpl_odd[0][1] != tpl_evn[0][1]:
  print(N - tpl_odd[0][0] - tpl_evn[0][0])
else:
  print(N - max(tpl_odd[1][0]+tpl_evn[0][0], tpl_odd[0][0]+tpl_evn[1][0]))
  



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

public class Main{
    static StringTokenizer st;
    static BufferedReader br;  
    static PrintWriter out;
 
    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
 
        int A = nextInt();
        int B = nextInt();
        int H = nextInt();
        int M = nextInt();
        
        double M_Angle = M * 360/60;
        double H_Angle = H * 360/12 + (double)M * 30/60;
        double M_Angle1 = M_Angle * Math.PI / 180;
        double H_Angle1 = H_Angle * Math.PI / 180;

        double xM = B * Math.sin(M_Angle1);
        double yM = B * Math.cos(M_Angle1);
        double xH = A * Math.sin(H_Angle1);
        double yH = A * Math.cos(H_Angle1);

        double ans = Math.sqrt((xM-xH)*(xM-xH) + (yM-yH)*(yM-yH));
       
        System.out.println(ans);
    }
    
      
    public static int nextInt() throws IOException {
        return Integer.parseInt(next());
    }
    public static long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    public static double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    static String next() throws IOException {
        while (st == null || !st.hasMoreTokens())
            st = new StringTokenizer(br.readLine().trim());
        return st.nextToken();
    }
}

Measured memory_bytes: 33112
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		char[] c = sc.next().toCharArray();
		int n = c.length;
		int a, b;
		a = b = 0;
		for (int i = 0; i < n; i++) {
			if (c[i] == 'A') {
				a = i;
				break;
			}
		}
		for (int i = n - 1; 0 <= i; i--) {
			if (c[i] == 'Z') {
				b = i;
				break;
			}
		}
		System.out.println(b - a + 1);
	}
}


Measured memory_bytes: 27488
#include<stdio.h>
     
    int main(){
     
      int n,i;
      int a;
      int max=0;
      int min=1000000000;
      scanf("%d",&n);
      for(i=0;i<n;i++){
        scanf("%d",&a);
        if(max<a)max=a;
        if(min>a)min=a;
      }
      
      printf("%d\n",max-min);
     
      return 0;
    }

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

#define ll long long int
#define llu long long unsigned int
#define pii pair<int,int>
#define PII pair<ll,ll>

const ll MAX=1e18+100;
const ll sz=2097252;
const ll mod=1e9+7;

ll dp[21][sz];

ll n, ara[21][21],tar;

ll cholo(ll id,ll mask)
{
    if(mask>=tar) return 1ll;
    ll &ret=dp[id][mask];
    if(~ret) return ret;

    ll tot=0;

    for(ll i=0;i<n;i++){
        if(ara[id][i]==1 && (((bool)(mask & (1<<i)))==0)){
            tot=(tot + cholo(id+1,(mask | (1<<i)))) % mod;
        }
    }

    return (ret=tot);
}

int main()
{
    ll m,p,q,i,j,k;
    cin>>n;
    for(i=0;i<n;i++){
        for(j=0;j<n;j++) cin>>ara[i][j];
    }

    memset(dp,-1,sizeof dp);
    tar=(1<<n)-1;

    ll ans=cholo(0,0);
    cout<<ans<<'\n';
}


Measured memory_bytes: 347676
import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
input = sys.stdin.buffer.readline
def inputS(): return input().rstrip().decode()
readlines = sys.stdin.buffer.readlines  

def is_prime(n):
  if n == 1:
    return False
  
  for k in range(2, int(n**0.5)+1):
    if n % k == 0:
      return False
  return True

X = int(input())

while True:
  if is_prime(X):
    print(X)
    exit()
  X += 1
  

Measured memory_bytes: 3060
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <numeric>
#include <queue>
#include <stack>
#include <map> 
#include <set>
#include <string>
#include <functional>
#include <list>
#include <random>
#include <time.h>
#include <iomanip>
#include <assert.h>
#include <numeric>
#define int long long
#define ll long long
#define double long double
#define mod 1000000007
#define MAXN (int)1e+5 * 2+1
#define LL_MAX 9223372036854775807	//ない環境用
#define LL_HALFMAX 9223372036854775807 / 2	//ない環境用
#define MIN -(9223372036854775807 / 2)
#define INF 9223372036854775807 / 2
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define mp make_pair


using namespace std;

std::mt19937 mt((int)time(0));

int dx[4] = { 0, 1, 0, -1 }; // x軸方向への変位
int dy[4] = { 1, 0, -1, 0 }; // y軸方向への変位

using Weight = int;
using Flow = int;
struct Edge {
	int src, dst;
	Weight weight;
	Flow cap;
	Edge() : src(0), dst(0), weight(0) {}
	Edge(int s, int d, Weight w) : src(s), dst(d), weight(w) {}
};
using Edges = std::vector<Edge>;
using Graph = std::vector<Edges>;
using Array = std::vector<Weight>;
using Matrix = std::vector<Array>;

void add_edge(Graph &g, int a, int b, Weight w = 1) {
	g[a].emplace_back(a, b, w);
	g[b].emplace_back(b, a, w);
}
void add_arc(Graph &g, int a, int b, Weight w = 1) { g[a].emplace_back(a, b, w); }

struct uf_tree {
	std::vector<int> parent;
	int __size;
	uf_tree(int size_) : parent(size_, -1), __size(size_) {}
	void unite(int x, int y) {
		if ((x = find(x)) != (y = find(y))) {
			if (parent[y] < parent[x]) std::swap(x, y);
			parent[x] += parent[y];
			parent[y] = x;
			__size--;
		}
	}
	bool is_same(int x, int y) { return find(x) == find(y); }
	int find(int x) { return parent[x] < 0 ? x : parent[x] = find(parent[x]); }
	int size(int x) { return -parent[find(x)]; }
	int size() { return __size; }
};



//!!!問題をちゃんと読む!!!
//!!!問題をちゃんと読め!!!
//!!!問題は読みましたか？!!!

class rest {
public:
	string S;
	int P;
	int Num;
public:
	rest(string s, int p, int num) {
		S = s;
		P = p;
		Num = num;
	}
	bool operator<(const rest &another) const
	{
		if (S != another.S)return S < another.S;
		return P > another.P;

	};
};

int imos[1000000];

signed main() {
	string s;
	int len;
	cin >> s;
	len = s.length();
	int win = 0;
	for (auto c : s) {
		if (c == 'o') {
			win++;
		}
	}
	if (win + (15 - len) >= 8) {
		cout << "YES\n";

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


	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,k,n) for(int i=k;i<n;i++)
int main (){
    int a,b,c;
    cin >> a >> b >> c;
    int ma = max({a,b,c});
    int ans;
    if((ma*3-a-b-c)%2 == 1){
        ans = (ma * 3 - a - b - c + 3) / 2;
    }else{
        ans = (ma * 3 - a - b - c) / 2;
    }
    cout << ans << endl;;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
        double PI = Math.PI;
     	double r = sc.nextDouble();
		
     	double A = PI*r*r;
		double P = 2*PI*r;
		
		System.out.printf("%5.5f %5.5f ",A,P);
     	
	sc.close();
	}
}

Measured memory_bytes: 28072
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())
k=int(input())
if max(k,b-a,c-a,d-a,e-a,c-b,d-b,e-b,d-c,e-c,e-d)==k:
  print("Yay!")
else:
  print(":(")

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

typedef long long ll;
const ll INF = 1010000000000000017LL;
const ll MOD = 1000000007LL;

#define REP(i, n) for(ll i = 0 ; i < n; i++)

//#define DEBUG(fmt, ...)
#define DEBUG(fmt, ...) fprintf(stderr, fmt "\n", ##__VA_ARGS__)

int main(){
    std::cout<<std::fixed<<std::setprecision(10);
    ll N;
    string S;
    cin >> N >> S;

    REP(i, S.size() ){
        char c = S[i];

        char n = c-'A';

        n = (n+N)%26;
        S[i] = (char)('A'+n);
    }

    cout << S << endl;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

class Program
{
    static void Main(string[] args)
    {
        string n = Console.ReadLine();
        if (n[0] == n[1] && n[1] == n[2]) Console.WriteLine("Yes");
        else if (n[1] == n[2] && n[2] == n[3]) Console.WriteLine("Yes");
        else Console.WriteLine("No");
    }
}

Measured memory_bytes: 11092
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-8;
const ll mod=1e9+7;
const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};

ll n,k;
vl a,b;

int main(){
	cin>>n>>k;
	a=b=vl(n);
	for(auto &i:a){
		cin>>i;
		i--;
	}
	for(auto &i:b) cin>>i;
	ll res=-INF;
	for(int i=0;i<n;i++){
		vl c;
		ll x=i,t=0;
		do{
			x=a[x];
			t+=b[x];
			c.push_back(t);
		}while(x!=i);
		ll m=c.size(),tmp=-INF;
		for(int j=0;j<min(m,k);j++) tmp=max(tmp,c[j]+max(0LL,(k-j-1)/m*c[m-1]));
		res=max(res,tmp);
	}
	cout<<res<<endl;
}

Measured memory_bytes: 3792
#include<bits/stdc++.h>
using namespace std;
#define all(vec) vec.begin(),vec.end()
typedef long long int ll;
typedef pair<ll,ll> P;
const ll MOD=1000000007;
const ll INF=1000000010;
const ll LINF=4000000000000000010LL;
const int MAX=310;
const double EPS=1e-3;
int dx[4]={0,1,0,1};
int dy[4]={0,0,1,1};
vector<P> v;
ll dp[5010][5010];
int main(){
	int n;cin>>n;
	for(int i=0;i<n;i++){
		ll h,p;cin>>h>>p;
		v.push_back(P(p+h,p));
	}
	sort(all(v));
	for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)dp[i][j]=LINF;
	dp[0][0]=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
			if(dp[i][j]<=v[i].first-v[i].second){
				dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+v[i].second);
			}
		}
	}
	int ans=0;
	for(int i=0;i<=n;i++){
		if(dp[n][i]!=LINF){
			ans=i;
		}
	}
	cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 196224
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll a, b, c, d;
  cin >> a >> b >> c >> d;
  ll ans;
  ans = max(a*d, a*c);
  ans = max(ans, b*c);
  ans = max(ans, b*d);
  cout << ans << endl;
}

Measured memory_bytes: 3648
def Cramer(a11, a12, a13, a21, a22, a23):
	den = a11 * a22 - a12 * a21
	return (a13 * a22 - a12 * a23) / den, (a11 * a23 - a13 * a21) / den

while True:
	try:
		x1, y1, x2, y2, x3, y3, xp, yp = [eval(item) for item in input().split()]
		u, v = Cramer(x3 - x1, x2 - x1, xp - x1, y3 - y1, y2 - y1, yp - y1)
		print('YES' if u >= 0.0 and v >= 0.0 and u + v <= 1.0 else 'NO')
	except EOFError:
		break

Measured memory_bytes: 7408
import java.util.Scanner;
class Main{
public static void main (String[] args){
Scanner scan = new Scanner(System.in);
int S=scan.nextInt();
int M=S/60;
int s=S%60;
int h=M/60;
int m=M%60;
System.out.println(h+":"+m+":"+s);
}
}

Measured memory_bytes: 26164
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        // write your code here
        Scanner scanner = new Scanner(System.in);
        String S = scanner.next();
        int p1 = 0, p2 = 0;
        if (S.length() == 1) {
            System.out.println(0);
            return;
        }

        if (S.charAt(0) == '0') p1 ++;
        if (S.charAt(0) == '1') p2 ++;
        for (int i = 1; i < S.length(); i ++) {
            if (i % 2 == 1) {
                if (S.charAt(i) == '1') {
                    p1 ++;
                } else {
                    p2 ++;
                }
            } else {
                if (S.charAt(i) == '0') {
                    p1 ++;
                } else {
                    p2 ++;
                }
            }
        }

        System.out.println(Math.min(p1, p2));
    }
}


Measured memory_bytes: 26264
#include <iostream>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>
#define rep(i,cc,n) for(int i=cc;i<=n;++i)
#define drep(i,cc,n) for(int i=cc;i>=n;--i)
typedef long long ll;
using namespace std;
int main(){
    ll w,a,b;
    cin>>w>>a>>b;
    ll left,right;
    if(b>a){
        left = a;
        right = b;
    }
    else{
        left = b;
        right = a;
    }

    if(left+w>right) cout<<"0"<<endl;
    else cout<<right-(left+w)<<endl;
    return 0;
}

Measured memory_bytes: 256
import numpy as np

n = int(input())
x = np.asarray(input().split(), dtype=np.int64)

p = np.mean(x)

p = (p+0.5).astype(np.int64)

ans = 0
for i in range(len(x)):
    ans += (x[i] - p) ** 2

print(ans)


Measured memory_bytes: 12484
class UnionFind:
    def __init__(self, n):
        self.p = [-1]*n
        # union by rank
        self.r = [1]*n
 
    def find(self, x):
        if self.p[x] < 0:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]
 
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
 
        if rx != ry:
            if self.r[rx] > self.r[ry]:
                rx, ry = ry, rx
            if self.r[rx] == self.r[ry]:
                self.r[ry] += 1
            self.p[ry] += self.p[rx]
            self.p[rx] = ry
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def count_member(self, x):
        return -self.p[self.find(x)]
n,m=map(int,input().split())
p=list(map(int,input().split()))
uf=UnionFind(n+1)
for i in range(m):
  x,y=map(int,input().split())
  uf.union(x,y)
ans=0
for i in range(n):
  if uf.same(p[i],i+1):
    ans+=1
print(ans)

Measured memory_bytes: 13812
n,m = map(int, input().split())
imos = [0]*(n+2)

for _ in range(m):
    l,r = map(int, input().split())
    imos[l]+=1
    imos[r+1]-=1

curr_cnt = 0
ans = 0
for i in range(n+1):
    curr_cnt += imos[i]
    if curr_cnt == m: ans += 1

print(ans)

Measured memory_bytes: 79276
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<string>
#include<utility>
#include<array>
#include<set>
#define EPS (1e-7)
using namespace std;






int main() {


	int N, ans=0;
	cin >> N;

	vector<int> a(N);

	for (auto i = 0; i < N; i++)
	{
		cin >> a[i];
		ans += a[i] - 1;
	}


	cout << ans << endl;


	return 0;
}

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

int sum_digit(int n){
  int sum=0;
  while (n>0){
    sum +=n%10;
    n = n/10;
  }
  return sum;
}

int main(){
  int n;
  cin >> n ;
  int ans = 1<<20;
  for (int a=1; a<n; a++){
    int b = n-a;
    int s = 0;
    s=sum_digit(a)+sum_digit(b);
    ans = ans > s ? s:ans;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000

int dp[20100];

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int H, N;
    cin >> H >> N;
    int A[1010], B[1010];
    rep(i, N) cin >> A[i] >> B[i];
    rep(i, 20100) dp[i] = INF/2;
    dp[0] = 0;
    rep(i, H) {
        rep(j, N) {
            dp[i + A[j]] = min(dp[i + A[j]], dp[i] + B[j]);
        }
    }
    int ans = INF;
    REP(i, H, 20010) ans = min(ans, dp[i]);
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pint = pair<int,int>;
ll mod = 1000000007,mod2 = 998244353;

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

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL<<60;
ll gcd(ll a,ll b){
    if(b == 0) return a;
    else return gcd(b,a%b);
}

vector<pair<ll,ll>> soinsuu(ll n){
    vector<pair<ll,ll>> ans;
    for (ll i = 2; i*i <= n; ++i) {
        if(n %i != 0) continue;
        int cnt = 0;
        while(n % i == 0){
            n /= i;
            cnt++;
        }
        ans.push_back({i,cnt});
    }
    if(n != 1) ans.push_back({n,1});
    return ans;
}

int main() {
    ll n,ans = 0;
    cin >> n;
    vector<pair<ll,ll>> v = soinsuu(n);
    for(auto i : v){
        int tmp = 1;
        while(i.second >= tmp){
            i.second -= tmp;
            tmp++;
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3632
import sys

def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def S(): return sys.stdin.readline().rstrip()

N,M,K = map(int,S().split())
A = LI()
A.reverse()
B = LI()
C = A+B

# 尺取り法
a = 0
b = N-1
# [a,b]について検証
r = sum(A)
ans = 0
while a <= N:
    if r > K:
        r -= C[a]
        a += 1
    else:
        ans = max(ans,b-a+1)
        b += 1
        if b < len(C):
            r += C[b]
        else:
            break

print(ans)

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

int main() {
  long N;
  cin>>N;
  long  mod=1e9+7;
  vector<long> a(N);
  vector<long> s(N);
  for(int i=0;i<N;i++){
    cin>>a[i];
    }
    s[0]=a[0];
    for(int i=1;i<N;i++){
      s[i]=s[i-1]+a[i];
      s[i]%=mod;

    }
  long ans=0;

for(int i=0;i<N;i++){
  long tmp = s[N-1]-s[i];
  if(tmp<0) tmp+=mod;
  ans+=a[i]*(tmp);
  ans%=mod;

}

cout<<ans<<endl;
}


Measured memory_bytes: 6432
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <map>
#include <cstdlib>
using namespace std;
int main()
{
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if (abs(a - c) <= d || abs(a - b) <= d && abs(b - c) <= d)
    {
        cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
import java.util.*;

class Main implements Runnable{
    private HashMap<Integer, List<Integer>> graph;
    private int time;
    public static void main(String[] args) throws Exception {
        new Thread(null, new Main(), "",  16 * 1024 * 1024).start();
    }

    @Override
    public void run() {
        Scanner scanner = new Scanner(System.in);
        int V = scanner.nextInt();
        int E = scanner.nextInt();

        graph = new HashMap<>(V);
        for(int i = 0; i < V; ++i){
            graph.put(i, new ArrayList<>());
        }

        for(int i = 0; i < E; ++i){
            int s = scanner.nextInt();
            int t = scanner.nextInt();

            graph.get(s).add(t);
            graph.get(t).add(s);
        }

        boolean[] visited = new boolean[V];
        int[] disc = new int[V];
        int[] low = new int[V];
        int[] parent = new int[V];
        boolean[] AP = new boolean[V];

        time = 0;

        Arrays.fill(parent, -1);

        for(int i = 0; i < V; ++i){
            if(!visited[i]){
                APUtil(i, disc, low, parent, visited, AP);
            }
        }

        for(int i = 0; i < V; ++i){
            if(AP[i]){
                System.out.println(i);
            }
        }
    }

    private void APUtil(int u, int[] disc, int[] low, int[] parent, boolean[] visited, boolean[] AP){
        if(visited[u]){
            return;
        }

        int children = 0;

        visited[u] = true;

        disc[u] = low[u] = ++time;

        for(Integer v : graph.get(u)){
            if(!visited[v]){
                ++children;
                parent[v] = u;
                APUtil(v, disc, low, parent, visited, AP);

                low[u] = Math.min(low[u], low[v]);

                if(parent[u] == -1 && children > 1){
                    AP[u] = true;
                }

                if(parent[u] != -1 && low[v] >= disc[u]){
                    AP[u] = true;
                }
            }
            else if(v != parent[u]){
                low[u] = Math.min(low[u], disc[v]);
            }
        }
    }

}

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

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define ALL(v) v.begin(),v.end()
#define FOR(i, j, k) for(ll i=j;i<k;i++)
#define DUMP(i, v)for(ll i=0;i<v.size();i++)cout<<v[i]<<" "

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<ll, ll> P;
typedef long double ld;
struct Edge{ll from, to, cost;};
struct node{ll cost, to;
  bool friend operator>(node a, node b){
    return a.cost>b.cost;
  }
};

ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

ll modpow(ll a, ll n, ll mod){
  ll res=1;
  while(n>0){
    if(n&1) res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll modinv(ll a, ll mod){
  return modpow(a, mod-2, mod);
}

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

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}

ll N, Ma, Mb;
llvec a,b,c;
ll dp[41][401][401];
ll v[41][401][401];

ll dpf(ll n, ll A, ll B){
  if(v[n][A][B]==1){
    return dp[n][A][B];
  }else{
    v[n][A][B]=1;
    if(n==0){
      if(A==0 and B==0){
        dp[n][A][B]=0;
      }
    }else{
      dp[n][A][B] = dpf(n-1, A, B);
      if(A-a[n-1]>=0 and B-b[n-1]>=0){
        dp[n][A][B] = min(dpf(n-1, A-a[n-1], B-b[n-1])+c[n-1], dp[n][A][B]);
      }
    }
    return dp[n][A][B];
  }
}


/**************************************
** A main function starts from here  **
***************************************/
int main(){
  cin >> N >> Ma >> Mb;
  a = llvec(N);
  b = llvec(N);
  c = llvec(N);
  
  rep(i, N){
    cin >> a[i] >> b[i] >> c[i];
  }
  fill(dp[0][0],dp[41][0] ,1000000000LL);
  ll i=1;
  ll ans = 1e12;
  while(i*Ma<401 and i*Mb<401){
    ans = min(ans, dpf(N, i*Ma, i*Mb));
    i++;
  }
  if(ans==1000000000LL)cout << "-1";
  else cout << ans;
  //cout << dp[2][3][5];
  
  return 0;
}


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

string K = "keyence";

int main() {
  string S;
  cin >> S;

  if (S == K) {
    cout << "YES" << endl;
    return 0;
  }

  string l = "", r = "";
  string R = S;
  reverse(R.begin(), R.end());
  for (int i = 0; i <= K.size(); i++) {
    l = S.substr(0, i);
    //cout << "i:" << i << ":" << l << endl;
    for (int j = K.size(); j > i; j--) {
      r = R.substr(0, j - i);
      reverse(r.begin(), r.end());
      //cout << "j:" << j << ":" << r << endl;
      if (l + r == K) {
        cout << "YES" << endl;
        return 0;
      }
    }
    //cout << "---" << endl;
  }

  cout << "NO" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>

using namespace std;

int main(){
    const int MAX_a = 100000;
    int n;
    scanf("%d", &n);
    int a[n];
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    int score[MAX_a+1]={0};
    for(int i = 0; i < n; i++)
    {
        score[a[i]-1]++;
        score[a[i]]++;
        score[a[i]+1]++;
    }
    int ma = 0;
    for(int i = 0; i < MAX_a + 1; i++)
    {
        if (ma <= score[i]) ma = score[i];
    }
    printf("%d\n", ma);
    
}

Measured memory_bytes: 1024
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include <cstdint>
#include <utility>
#include <tuple>
#include <map>    
#include <queue> 
#include <set>  
#include <stack> 
#include <deque>  
#include <unordered_map> 
#include <unordered_set> 
#include <bitset>

using namespace std;

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

	vector<int> p(n);
	for (int i = 0; i < n; i++) {
		cin >> p.at(i);
	}

	int count = 0;
	for (int i = 1; i <= n - 2; i++) {
		if (p.at(i) > p.at(i - 1) && p.at(i) < p.at(i + 1)) {
			count++;
		}
		else if (p.at(i) < p.at(i - 1) && p.at(i) > p.at(i + 1)) {
			count++;
		}
	}

	cout << count << endl;
}

Measured memory_bytes: 256
using System;

namespace ABC100_2
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] a = Console.ReadLine().Split();
            int D = Int32.Parse(a[0]);
            int N = Int32.Parse(a[1]);
            if (N == 100) N++;
            Console.WriteLine(Math.Pow(100, D) * N);
        }
    }
}

Measured memory_bytes: 11092
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <cstdio>
#include <cmath>
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;
typedef pair<int, int> P;

int h, w, m;
int py[300000], px[300000];
P cy[300000];	//(count, y), 降順
P cx[300000];	//(count, x), 降順
set<P> dict;	//点集合

signed main() {
	int i, j;
	
	cin >> h >> w >> m;
	
	rep(i, h) { cy[i] = P(0, i); }
	rep(i, w) { cx[i] = P(0, i); }
	
	rep(i, m) {
		cin >> py[i] >> px[i];
		py[i]--; px[i]--;
		cy[py[i]].first++;
		cx[px[i]].first++;
		dict.insert(P(py[i], px[i]));
	}
	sort(cy, cy + h, greater<P>());
	sort(cx, cx + w, greater<P>());
	
	int y, x;
	int ans = 0;
	rep(i, h) {
		rep(j, w) {
			y = cy[i].second;
			x = cx[j].second;
			
			if (dict.find(P(y, x)) != dict.end()) {
				ans = max(ans, cy[i].first + cx[j].first - 1);
			}
			else {
				ans = max(ans, cy[i].first + cx[j].first);
				break;
			}
		}
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 24724
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main
{
    public static void main(String[] args)
    {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(1, in, out);
        out.close();
    }

    static class Task
    {
        public void solve(int testNumber, Scanner in, PrintWriter out)
        {
            int N = in.nextInt();
            int nums[] = CPUtils.readIntArray(N, in);
            int min = nums[0];
            int count = 1;
            for (int i = 1; i < N; i++)
            {
                if (min >= nums[i]) count++;
                min = Math.min(min, nums[i]);
            }
            out.print(count);
        }

    }

    static class CPUtils
    {
        public static int[] readIntArray(int size, Scanner in)
        {
            int[] array = new int[size];
            for (int i = 0; i < size; i++)
            {
                array[i] = in.nextInt();
            }
            return array;
        }

    }
}



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

using ll = long long;
constexpr ll inf = 1e18;

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

    ll ans = inf;
    int mid_l = 1, mid_r = 1;
    auto should_extend = [&] (int l, int r, int m) {
                             const ll x1 = abs(sum[r] - sum[m + 1] - (sum[m + 1] - sum[l]));
                             const ll x2 = abs(sum[r] - sum[m] - (sum[m] - sum[l]));
                             return x1 <= x2;
                         };
    for(int mid = 2; mid + 1 <= n; ++mid) {
        mid_r = max(mid_r, mid + 1);
        while(mid_l + 1 != mid && should_extend(0, mid, mid_l)) mid_l++;
        while(mid_r + 1 != n && should_extend(mid, n, mid_r)) mid_r++;
        ll mini = min({sum[mid_l], sum[mid] - sum[mid_l], sum[mid_r] - sum[mid], sum[n] - sum[mid_r]});
        ll maxi = max({sum[mid_l], sum[mid] - sum[mid_l], sum[mid_r] - sum[mid], sum[n] - sum[mid_r]});
        ans = min(ans, maxi - mini);
    }

    cout << ans << endl;
}


Measured memory_bytes: 3328
#include<iostream>
#include<stdio.h>
#include<cctype>
#include<string>
using namespace std;
int sum[126] = {};

int main() {
	int j = 0;
	int num=0;
	char ch;
	char w = 97;
	while (cin>>ch) {

		if(ch=='\n'){break;}
			if (ch >= 65 && ch <= 90) {
				num = ch - 'A';
				sum[num]++;
			}
			else if (ch >= 97 && ch <= 122) {
				num = ch - 'a';
				sum[num]++;
			}
			
	}
	for (int a = 0; a < 26; a++) {

		cout << w << " : " << sum[a] << endl;
		w++;
	}
	return 0;
}


Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int xs, ys, xt, yt; cin >> xs >> ys >> xt >> yt;
    int N; cin >> N;
    vector<int> X(N+2), Y(N+2), R(N+2);
    for (int i = 0; i < N; i++) cin >> X[i] >> Y[i] >> R[i];
    X[N] = xs, Y[N] = ys; R[N] = 0;
    X[N+1] = xt, Y[N+1] = yt, R[N+1] = 0;
    vector<vector<double>> cost(N+2, vector<double>(N+2));
    for (int i = 0; i < N+2; i++) {
        for (int j = 0; j < N+2; j++) {
            cost[i][j] = max(0.0, sqrt(pow(X[i]-X[j],2)+pow(Y[i]-Y[j],2))-R[i]-R[j]);
        }
    }
    vector<double> dist(N+2, 1e20); dist[N] = 0;
    using P = pair<double, int>;
    priority_queue<P, vector<P>, greater<P>> Q;
    Q.push(make_pair(0, N));
    while (!Q.empty()) {
        P p = Q.top();
        Q.pop();
        if (p.first != dist[p.second]) continue;
        if (p.second == N+1) {
            cout << fixed << setprecision(16) << p.first << endl;
            break;
        }
        for (int i = 0; i < N+2; i++) {
            double d = p.first + cost[p.second][i];
            if (d < dist[i]) {
                dist[i] = d;
                Q.push(make_pair(d, i));
            }
        }
    }
    return 0;
}


Measured memory_bytes: 14192
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7




S = sys.stdin.readline().rstrip()


n = 'N' in S
w = 'W' in S
s = 'S' in S
e = 'E' in S

ok = (w and e or not w and not e) and (n and s or not n and not s)
if ok:
    print('Yes')
else:
    print('No')



Measured memory_bytes: 22140
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a) for(int i=0;i<(a);i++)
const ll MOD=1000000007;
// const ll MOD=998244353;

vector<vector<int>> G(101010);
int N,K;

ll dfs(int v,int p){
  ll res=1;
  int col=(p==-1)?K-1:K-2;
  if(K<G[v].size()){
    return 0;
  }
  for(int u:G[v]){
    if(u==p) continue;
    (res*=col--)%=MOD;
    (res*=dfs(u,v))%=MOD;
  }
  return res;
}

int main(){
  cin>>N>>K;
  rep(i,N-1){
    int A,B; cin>>A>>B; A--,B--;
    G[A].push_back(B);
    G[B].push_back(A);
  }

  cout<<K*dfs(0,-1)%MOD<<endl;
  return 0;
}


Measured memory_bytes: 11648
from sys import stdin
N = int(stdin.readline().rstrip())
A = [int(_) for _ in stdin.readline().rstrip().split()]
minus = []
for i in range(N):
  if A[i] < 0:
    minus.append(A[i])
abs_A = [abs(i) for i in A]
if len(minus) % 2 == 0:
  print(sum(abs_A))
else:
  print(sum(abs_A)-min(abs_A)*2)

Measured memory_bytes: 14252
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<climits>
#include<string>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<algorithm>

#define ll long long
#define sz 105

using namespace std;

int main()
{
    ll n,m,a,b,frq[sz];

    scanf("%lld %lld",&n,&m);

    memset(frq,0,sizeof(frq));

    while(m--)
    {
        scanf("%lld %lld",&a,&b);

        frq[a]++;
        frq[b]++;
    }

    for(ll i=1;i<=n;i++)
    {
        printf("%lld\n",frq[i]);
    }

    return (0);
}




Measured memory_bytes: 256
n, x, y = map(int, input().split())

def dist(i, j):
  return min(j - i, abs(i-x) + abs(j-y) + 1)

distList = [0] * (n-1)

for i in range(1, n):
  for j in range(i+1, n+1):
    distList[dist(i,j)-1] += 1

for distItem in distList:
  print(distItem)

Measured memory_bytes: 3444
#include <bits/stdc++.h>
#define ll long long
#define fort(i,n) for (int i = 1; i <= n; ++i)
#define pi pair<int,int>
#define pb push_back
#define sz size()
#define er erase
#define fr first
#define sc second
#define rc(x) return cout << x, 0
using namespace std;

ll n,cnt;

void bt (ll x, int a, int b, int c)
{
    if (x>n) return;
    if (a+b+c==3) ++cnt;
    bt(10*x+3, 1, b, c);
    bt(10*x+5, a, 1, c);
    bt(10*x+7, a, b, 1);
}

int32_t main()
{
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin >> n;
    bt (0,0,0,0);
    cout << cnt;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>

using std::cin;
using std::cout;
using std::vector;



int main(int argc, char* argv[])
{
  std::ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int N; cin >> N;
  std::string S; cin >> S;

  vector<int> Ds;
  vector<int> Ms;
  vector<int> Cs;

  for (int i = 0; i < N; ++i)
  {
    switch (S[i])
    {
      case 'D': Ds.push_back(i); break;
      case 'M': Ms.push_back(i); break;
      case 'C': Cs.push_back(i); break;
    }
  }

  int Q;
  cin >> Q;

  using ll = long long;
  while (Q--)
  {
    int k; cin >> k;

    ll D = 0;
    ll DM = 0;
    ll M = 0;

    ll res = 0;

    for (int i = 0; i < N; ++i)
    {
      if (i >= k)
      {
        switch (S[i-k])
        {
          case 'D':
            DM -= M;
            --D;
            break;
          case 'M':
            --M;
            break;
        }
      }

      switch (S[i])
      {
        case 'D':
          ++D;
          break;
        case 'M':
          ++M;
          DM += D;
          break;
        case 'C':
          res += DM;
          break;
      }
    }

    cout << res << "\n";
  }

  return 0;
}


Measured memory_bytes: 8344
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
using P   = pair<ll, ll>;
using mat = vector<vector<ll>>;

void IOS() { ios::sync_with_stdio(false), cin.tie(0); }

template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
    fill((T *)array, (T *)(array + N), val);
}

const ll INF = 1e16;
const ll MOD = 1e9 + 7;
// int dx[4]    = {1, 0, -1, 0};
// int dy[4]    = {0, 1, 0, -1};
// ll pas[5001][5002];

signed main() {
    IOS();
    ll n;
    cin >> n;
    vector<ll> a(n), b(n);
    ll suma = 0, sumb = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        suma += a[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> b[i];
        sumb += b[i];
        a[i] -= b[i];
    }
    if (suma < sumb) {
        cout << -1 << endl;
        return 0;
    }
    sort(a.begin(), a.end());
    ll sum = 0;
    ll ans = 0;
    if (a[0] >= 0) {
        cout << 0 << endl;
        return 0;
    }
    for (int i = 0; a[i] < 0; ++i) {
        sum += a[i];
        ans++;
    }
    for (int i = n - 1; sum < 0; --i) {
        sum += a[i];
        ans++;
    }
    cout << ans << endl;

    return 0;
}

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

#define         ll      long long int

int main( )
{
    ll n, i, a, two = 0, d;

    cin >> n;
    for (i = 0; i < n; i++)
    {
        cin >> d;
        while (d % 2 == 0)
        {
            d /= 2;
            two++;
        }
    }
    cout << two << "\n";
    return 0;
}


Measured memory_bytes: 256
#ifdef HIRO
#include "../stdc++.h"
#define d(f_, ...) printf((f_), ##__VA_ARGS__)
#else
#include <bits/stdc++.h>
#define d(f_, ...)
#endif

using namespace std;
typedef long long ll;

char maze[20][21];
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

typedef pair<int, int> P;
const int INF = 100000000;

int bfs(int n, int m, int sx, int sy, int gx, int gy) {
  queue<P> que;
  int d[n][m];
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) {
      d[i][j] = INF;
    }
  }
  que.push(P(sx, sy));
  d[sx][sy] = 0;

  while(que.size()) {
    P p = que.front();
    que.pop();
    if(p.first == gx && p.second == gy)
      break;
    for(int i = 0; i < 4; i++) {
      int nx = p.first + dx[i];
      int ny = p.second + dy[i];
      if(nx >= 0 && nx < n && ny >= 0 && ny < m && maze[nx][ny] != '#' && d[nx][ny] == INF) {
        que.push(P(nx, ny));
        d[nx][ny] = d[p.first][p.second] + 1;
      }
    }
  }
  return d[gx][gy];
}

int main() {
#ifdef HIRO
  ifstream cin("input.txt");
  std::cin.rdbuf(cin.rdbuf());
#endif

  int h, w;
  cin >> h >> w;
  for(int i = 0; i < h; i++) {
    cin >> maze[i];
  }
  int max = 0;
  for(int i = 0; i < h * w - 1; i++) {
    for(int j = i + 1; j < h * w; j++) {
      int sx = i / w;
      int sy = i % w;
      if(maze[sx][sy] == '#') continue;
      int gx = j / w;
      int gy = j % w;
      if(maze[gx][gy] == '#') continue;
      int r = bfs(h, w, sx, sy, gx, gy);
      if(r > max) max = r;
    }
  }
  cout << max;
  return 0;
}



Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <string>
#include <iostream>
#include <algorithm>
#include <map>
#include <iterator>
#include <functional>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <fstream>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <cmath>
#include <list>
#include <sstream>

#define rep(i,m,n) for(ll i = (m); i < (n); i++)
#define rep0(i, n) for(ll i = (0); i < (n); i++)
#define repd(i,m,n) for(ll i=(m); i > (n); i--)
#define iter(el, arr) for(auto& el : arr)
#define FOR(i,a,b) for(ll i = (a); i < (b); ++i)
#define RFOR(i,b,a) for(ll i = (b) - 1; i >= (a); --i)
#define REPEAT(i) FOR(counter1234,0,i)
#define ALL(a) a.begin(), a.end()

#define ld long double
#define ll long long
#define ull unsigned ll
#define pii pair<ll,ll>
#define pll pair<ll,ll>
#define plli pair<pll,ll>
#define MP make_pair
#define SZ(a) ll((a).size())
#define X first
#define Y second

#define endl '\n'
#define PB push_back
#define has(i, m) (m.find(i) != m.end())

#define vi vector<int>
#define vll vector<ll>
#define vch vector<char>
#define vvi vector<vi>
#define vvll vector<vll>
#define vpii vector<pii>
#define vpll vector<pll>
#define vb vector<bool>
#define vvb vector<vb>
#define pdd pair<ld, ld>
#define vpll vector<pll>
#define vpdd vector<pdd>
#define pq priority_queue
#define mod 1000000007
using namespace std;

const ll INF = 1e18;
const ll MAXN = 100001;

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

int main()
{
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	//freopen("In.txt", "r", stdin);

	ll n, k;
	cin >> n >> k;
	vll a(n);
	FOR(i, 0, n)
		cin >> a[i];

	ll ma = a[0];
	FOR(i, 1, n)
		ma = max(ma, a[i]);

	FOR(i,0,n)
		if (a[i] == k)
		{
			cout<< "POSSIBLE";
			return 0;
		}

	ll g = a[0];
	FOR(i, 1, n)
		g = gcd(g, a[i]);

	if (k%g == 0 && k <= ma)
		cout << "POSSIBLE";
	else
		cout<< "IMPOSSIBLE";





	return 0;
}
//don't forget about MAXN, INF and mod

Measured memory_bytes: 1024
/*
author: Apoorv Singh
*/

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

typedef vector <long long> vi;
typedef pair <long long, long long> pii;
#define pb push_back   
#define all(c) c.begin(), c.end()
#define watch(x) cout << (#x) << " " << (x) << endl;
#define FOR(i, a, b) for (long long i = a; i < b; ++i)
#define FORR(i, a, b) for (long long i = a; i > b; --i)
#define um unordered_map
#define F first
#define S second
#define int long long
#define inf LLONG_MAX
#define endl "\n"

int modulo = 1e9 + 7;

template <class X>

void printarr(X arr[], int n)
{
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << endl;
}

int fpow(int a, int n)
{
    int ans = 1;
    while (n)
    {
        if (n&1)
            ans = (ans * a)%modulo;
        a = (a*a)%modulo;
        n = n >> 1;
    }
    return ans;
}

/*
const int M = 1e6 + 10;
int composite[M] = {0};

void sieve()
{
    FOR(i,2,M)
    {
        if (!composite[i])
        {
            for (int j = 2*i; j < M; j += i)
                composite[j] = max(composite[j], i);
        }
    }
}
*/

const int M = 1e4 + 10;
int c[M], ptr = 0, visited[M] = {0};
vector <pii> graph[M]; 

void bfs(int source)
{
    queue <int> q;
    q.push(source);
    while (!q.empty())
    {
        source = q.front(); q.pop();
        visited[source] = c[ptr]; ++ptr;
        for (pii a : graph[source])
        {
            int vertex = a.S;
            if (!visited[vertex]) q.push(vertex);
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n; cin >> n;
    int number[n+1] = {0}, degree[n+1] = {0};
    pii edges[n];
    FOR(i,0,n-1)
    {
        int a,b; cin >> a >> b;
        ++degree[a]; ++degree[b];
        edges[i] = {a,b};
    }
    FOR(i,0,n) cin >> c[i];
    sort(c, c+n, greater <int>());
    pii arr[n+1];
    FOR(i,1,n+1) arr[i] = {degree[i], i};
    FOR(i,0,n)
    {
        int a,b; tie(a,b) = edges[i];
        graph[a].pb({degree[b], b}); graph[b].pb({degree[a], a});
    }
    FOR(i,1,n+1) sort(all(graph[i]));
    sort(arr+1, arr+n+1, greater <pii>());
    int source = arr[1].F;
    bfs(source);
    int ans = 0;
    FOR(i,0,n)
    {
        int a,b; tie(a,b) = edges[i];
        ans += min(visited[a], visited[b]);
    }
    cout << ans << endl;
    FOR(i,1,n+1) cout << visited[i] << ' ';
    return 0;
}

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
#define Hello ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define endl '\n'
int solve(int n, int k)
{
    string s = "";
    while(n)
    {
        s += to_string(n % k);
        n /= k;
    }
    return s.size();
}
int main()
{
    Hello
    int n, k;
    cin >> n >> k;
    cout << solve(n, k);
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
 
int gcd(int a, int b) {
  if( b == 0 ) return a;
  return gcd( b, a % b );
}
 
int main() {
  for(int a, b; cin >> a >> b; ) {
    int g = gcd(a,b);
    cout << g << " " << a / g * b << endl;
  }
}


Measured memory_bytes: 2988
#include<iostream>
#include<cstdio>
#include<map>
#include<algorithm>
#define maxn 20
#define ll long long
#define mod 1000000007
using namespace std;
int n,m,q,x,y,cnt=0,tim=0;
int node[maxn<<1],lid[maxn<<1],rid[maxn<<1];
ll ans,val[maxn<<1],dlt[1<<maxn],f[10][1<<maxn];
map<int,int>fa,id;
int find(int x){
	return fa.count(x)?fa[x]=find(fa[x]):x;
}
ll ksm(ll x,ll i){
	ll res=1;
	for(;i;i>>=1,x=x*x%mod)
		if(i&1)res=res*x%mod;
	return res;
}
int main(){
	scanf("%d%d",&n,&q);
	for(register int i=1;i<=q;i++){
		scanf("%d%d",&x,&y);
		if(x>y)swap(x,y);
		x--;
		node[++cnt]=x;
		node[++cnt]=y;
		int fx=find(x),fy=find(y);
		if(fx>fy)swap(fx,fy);
		if(fx!=fy)fa[fy]=fx;
	}
	node[++cnt]=0;
	sort(node+1,node+cnt+1);
	cnt=unique(node+1,node+cnt+1)-node-1;
	ans=1;
	for(register int i=1,lst=0;i<=cnt;lst=node[i],i++){
		int now=node[i];
		id[now]=fa.count(now)?id[find(now)]:tim++;
		lid[i]=id[lst];
		rid[i]=id[now];
		if(!now){
			ans=ans*ksm(9,mod-2)%mod;
			val[i]=1;
		}
		else{
			ll res=(ksm(10,now-lst)-1)*ksm(9,mod-2)%mod;
			ans=ans*res%mod;
			val[i]=(res+1)*ksm(res,mod-2)%mod;
		}
	}
	if(node[cnt]<n)ans=ans*ksm(10,n-node[cnt])%mod;
	m=(1<<tim);
	for(register int i=0;i<m;i++){
		dlt[i]=1;
		for(register int j=2;j<=cnt;j++){
			if(((i>>lid[j])&1)&&((i>>rid[j])&1))dlt[i]=dlt[i]*val[j]%mod;
		}
		f[0][i]=dlt[i];
	}
	for(register int i=0;i<8;i++){
		for(register int j=0;j<m;j++){
			for(register int k=j;k<m;k=(k+1)|j){
				f[i+1][k]=(f[i+1][k]+f[i][j]*dlt[j^k]%mod)%mod;
			}
		}
	}
	printf("%lld",ans*f[8][m-1]%mod);
	return 0;
}

Measured memory_bytes: 19200