akhauriyash/Code-Regression huggingface dataset:
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE TypeSynonymInstances #-}

import Control.Applicative
import Control.DeepSeq
import Control.Monad
import Control.Monad.ST
import qualified Data.Array as A
import qualified Data.Array.IArray as IA
import qualified Data.Array.IO as AI
import qualified Data.Array.MArray as MA
import qualified Data.Array.ST as STA
import qualified Data.Array.Unboxed as AU
import Data.Bits
import qualified Data.ByteString.Char8 as BS
import Data.Char
import qualified Data.Graph as G
import Data.Int
import qualified Data.IntMap as IM
import qualified Data.IntSet as IS
import Data.List
import qualified Data.Map.Strict as M
import Data.Maybe
import Data.Ord
import qualified Data.Sequence as SQ
import qualified Data.Set as S
import Data.Time
import qualified Data.Tree as T
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as VM
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM

class Printable a where
  format :: a -> String

instance Printable Int where
  format = show

instance Printable Integer where
  format = show

instance Printable Double where
  format = show

instance Printable Float where
  format = show

instance Printable Char where
  format = show

instance Printable String where
  format x = x

instance Printable Bool where
  format = show

put :: Printable a => a -> IO ()
put = putStr . format

putLn :: Printable a => a -> IO ()
putLn = putStrLn . format

putList :: Printable a => [a] -> IO ()
putList [a] = put a
putList (a:as) = do
  put a
  putStr " "
  putList as

readInt :: IO [Int]
readInt = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine

readInts :: Int -> IO [[Int]]
readInts n = replicateM n readInt

readInteger :: IO [Integer]
readInteger = map (fst . fromJust . BS.readInteger) . BS.words <$> BS.getLine

readIntegers :: Int -> IO [[Integer]]
readIntegers n = replicateM n readInteger

readString :: IO [String]
readString = map BS.unpack . BS.words <$> BS.getLine

readStrings :: Int -> IO [[String]]
readStrings n = replicateM n <$> readString

toPair :: [a] -> (a, a)
toPair [x, y] = (x, y)

count :: Eq a => a -> [a] -> Int
count a as = length $ filter (== a) as

main = do
  s <- getLine
  let s' = take 4 s ++ take 2 (drop 5 s) ++ drop 8 s
   in if read s' <= 20190430
        then putLn "Heisei"
        else putLn "TBD"

Measured memory_bytes: 508
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <numeric>
#include <ctime>
#include <complex>
#include <bitset>
#include <random>

using namespace std;

typedef long long ll;
typedef long double ld;

#define int ll
#define double ld
#define loop(i, n) for(int i = 0; i < (int)n; ++i)
#define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
#define F first
#define S second
#define pb push_back
#define pi pair <int, int>
#define all(x) begin(x), end(x)
#define ti tuple <int, int, int>
#define Point Vect
#define mkt make_tuple
#define no {cout << "-1\n"; return;}

void solve() {
    int n, k;
    cin >> n >> k;
    vector <int> a(n);
    loop(i, n) {
        cin >> a[i];
        if (i >= k)
            cout << (a[i] > a[i - k] ? "Yes" : "No") << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //int t; cin >> t; loop(i, t)
    solve();
    return 0;
}

Measured memory_bytes: 4764
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
#define watch(x) cout << (#x) << " is " << (x) << endl
#define pb push_back
const int N=1e9+1;


int32_t main()
{

    
    IOS;
    
    string s,t;
    cin>>s>>t;
   
    int n=s.length();
    int m=t.length();

    int C[n+1][m+1];
    int B[n+1][m+1];
    for(int i=0;i<=m;i++)
    {
    	C[0][i]=0;
    }
    for(int i=0;i<=n;i++)
    {
    	C[i][0]=0;
    }

    for(int i=1;i<=n;i++)
    {
    	for(int j=1;j<=m;j++)
    	{
    		if(char(t[j-1])==char(s[i-1]))
    		{
    			C[i][j]=C[i-1][j-1]+1;
    			B[i][j]='D';	
       		}
    		else
    		{
    			C[i][j]=max(C[i-1][j],C[i][j-1]);
    			if(C[i-1][j]<C[i][j-1])
    			{
    				B[i][j]='L';
    			}
    			else
    			{
    				B[i][j]='U';
    			}
    		}
    		
    	}

    }

    // cout<<C[n][m]<<endl;

    
    int i=n,j=m;
    string str="";

    while(1)
    {
    	if(i==0 || j==0)
		break;
		if(B[i][j]=='D')
		{
			str=t[j-1]+str;
			i--,j--;
		}
		else if(B[i][j]=='L')
		{
			j--;
		}
		else
			i--;
    }

    cout<<str<<endl;
    return 0;
   }

Measured memory_bytes: 140928
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define endl "\n"
#define pii pair<int, int>
#define fi first
#define se second
#define vi vector<int>
#define pb push_back
#define make_pair mp
#define MAX (long long )1e18
#define INF (int)1e9+7
#define K 26
#define rep(i,a,b) for(int i = a; i<b; i++)
#define ll long long 





int32_t main(){
	string s;
	cin >> s;
	if(s == "ABC"){
		cout << "ARC\n";
	}else{
		cout << "ABC\n"; 
	}
	return 0;
}

Measured memory_bytes: 3548
import java.util.Scanner;


	public class Main {
		

		public static void main(String[] args) {

			Scanner sc = new Scanner(System.in);
			
			int n = sc.nextInt();
			int p = sc.nextInt();
			int e = 0;
			int o = 0;
			long ret = 0;
			
			for(int i=0;i<n;i++) {
				int j = sc.nextInt();
				if(j%2==0) {
					e++;
				}else {
					o++;
				}
			}
			
			int c[][] = new int [2005][2005];

	       
	        
	        c[0][0]=1;
	        for(int i=0;i<2003;i++) {
	            for(int j=0;j<2003;j++) {
	                long tmp = c[i][j];
	                c[i+1][j]+=tmp;
	                c[i+1][j+1]+=tmp;
	            }
	        }
			
			
			
			long odd = 0;
			if(o==0||o==1) {
				odd=1;
			}else {
				for(int i=0;i<=o;i+=2) {
					odd += c[o][i];
				}
			}

			
			
			if(p==0) {
				ret = (long)pow(2, e)*odd;
			}else {
				ret = (long)pow(2, e+o)-(long)pow(2, e)*odd;
			}

			System.out.println(ret);
			
		}
		
		
		static long pow(int x,int y) {
			int count = 1;
			long ret = x;
			for(;count<y;) {
				ret *= x;
				count++;
			}
			if(y==0) {
				ret = 1;
				return ret;
			}
			return ret;
		}
	}


Measured memory_bytes: 53972
#include <iostream>
#include <vector>

long long pow(long long a,long long b,long long mod){
    if(b==0){
        return 1;
    }else{
        if(b%2==0){
            return pow((a*a)%mod,b/2,mod);
        }else{
            return (pow((a*a)%mod,b/2,mod)*a)%mod;
        }
    }
}

int main(){
    using namespace std;
    int N,K;
    cin>>N>>K;

    long long ans=0;
    long long mod=1000000007;
    long long a;
    vector<long long> m(K+1);
    for(int i=1;i<=K;i++){
        a=K/i;
        m[i]=pow(a,N,mod);
    }
    for(int i=K/2;i>=1;i--){
        for(int j=2*i;j<=K;j+=i){
            m[i]-=m[j];
        }
    }

    for(int i=1;i<=K;i++){
        ans+=i*m[i];
        ans%=mod;
    }

    cout<<ans<<endl;

    return 0;
}

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

using namespace std;

int main(){
    int N,ans=0,anss=0,avl=0;
    cin >> N;
    vector<int> X(N);
    for(int i=0;i<N;i++){
        cin >> X[i];
        avl += X[i];
    }
    avl /= N;

    sort(X.begin(),X.end());

    for(int i=0;i<N;i++){
        ans += (X[i]-avl)*(X[i]-avl);
    }

    for(int i=0;i<N;i++){
        anss += (X[i]-avl-1)*(X[i]-avl-1);
    }

    cout << min(ans,anss) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)n;i++)
typedef long long ll;
ll gcd(ll x,ll y){
    if (y == 0) return x;
    return gcd(y, x%y);
}
ll lcm(ll x,ll y){
    return x*y/gcd(x,y);
}
int main(void){
    // Your code here!
    int n;
    ll m;cin>>n>>m;
    vector<ll> a(n);
    rep(i,n){
        int x;cin>>x;
        a[i]=x/2;
    }
    ll buf=0,buf2=a[0];
    while(buf2>0){
        if(buf2%2!=0){
            buf=a[0]/buf2;
            break;
        }
        else{
            buf2/=2;
        }
    }
    ll l=a[0];
    rep(i,n){
        if((a[i]/buf)%2==0){
            cout<<0<<endl;
            return 0;
        }
        l=lcm(l,a[i]);
    }
    ll res=m/l;
    res++;
    res/=2;
    cout<<res<<endl;
}

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

int main(void){
	int N;
	int ans = 1e9+7;
	cin >> N;
	vector<int> W(N);
	int sum = 0;
	for(int i=0;i<N;i++){
		cin >> W[i];
		sum += W[i];
	}
	int b[N];
	b[0]=W[0];
	for(int i=1;i<N;i++){
		b[i]= W[i]+b[i-1];
	}
	for(int i=0;i<N-1;i++){
		ans = min(ans,abs(sum-b[i]*2));
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
#define Mod 1000000007
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
#define INF 1000000000000
 
 
 
struct edge{ll from,to,cost; };
edge es[5050];
ll d[2525];
ll V,E;
 
ll ttt=0;
 
void bellmanford(ll s){
    for(ll i=0;i<V;i++) d[i]=INF;
    d[s]=0;
    ll cnt=0;
    while(true){
        bool update=false;
        cnt++;
        for(int i=0;i<E;i++){
            edge e=es[i];
            if(d[e.from]!=INF && d[e.to]>d[e.from]+e.cost){
                d[e.to]=d[e.from]+e.cost;
                update=true;
                if(cnt>V) {
                    d[e.to]=-INF;
                    if(e.to==V-1) {
                        cout<<-1<<endl;
                        ttt=-1;
                        return;
                    }
                }
                if(cnt>3*V) return;
            }
        }
        if(!update) break;
    }
}
 
int main(){
    ll i,j;
    ll n,m,p;
    cin>>n>>m>>p;
    V=n;
    E=m;
 
    for(i=0;i<m;i++){
        ll a,b,c;
        cin>>a>>b>>c;
        a--;
        b--;
        es[i]={a,b,p-c};
    }
    bellmanford(0);
    
    if(ttt!=-1) cout<<max(0ll,-d[n-1])<<endl;
 
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#define MAX  10000
using namespace std;

int n;

void countingSort(short A[], short B[], int k)
{
    int C[k+1];
    for(int i = 0; i <= k; i++){
        C[i] = 0;
    }
    for (int j = 1; j <= n; j++){
        C[A[j]] += 1;
    }
    for (int i = 1; i <= k; i++){
        C[i] += C[i-1];
    }

    for (int j = 1; j <= n; j++ ){
        B[C[A[j]]] = A[j];
        C[A[j]]--;
        
    }
    
}

int main()
{
    int k = MAX;
    
    cin >> n;
    short A[n+1], B[n+1];
    
    for (int i = 1; i <= n; i++){
        cin >> A[i];
    }

    countingSort(A, B, k);
    for (int i = 1; i <= n; i++){
        if(i > 1) cout << " ";
        cout << B[i];
        
    }
    cout << endl;
    
    return 0;
}

Measured memory_bytes: 9008
#include<stdio.h>
int main(void)
{
  int n;
  scanf("%d",&n);
  int i,j;
  for(i=1;i<=9;i++)
    for(j=1;j<=9;j++)
      if(n==i*j){
        printf("Yes\n");
        return 0;
      }
  printf("No\n");
  return 0;
}

Measured memory_bytes: 128
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(int(readline()) for _ in range(N))

    ans = 0
    for i in range(N):
        if i==N-1:
            ans += A[i] // 2
        else:
            ans += A[i]//2
            A[i] %= 2
            if A[i]==1 and A[i+1]>0:
                ans += 1
                A[i] = 0
                A[i+1] -= 1
    print(ans)


if __name__ == '__main__':
    main()


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

class Main{
	public static void main(String[] args){
		solve();
	}
	public static void solve(){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		HashMap<String, Integer> map = new HashMap<String, Integer>();
		for(int a=0;a<n;a++){
			String s = sc.next();
			String t = sc.next();
			if(s.charAt(0)=='i'){
				map.put(t, 1);
			}
			else{
				if(map.containsKey(t)){
					System.out.println("yes");
				}
				else{
					System.out.println("no");
				}
			}
		}
	}
}



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

//#define int long long
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<n;++i)
#define exrep(i, a, b) for(ll i = a; i < b; i++)
#define out(x) cout << x << endl
#define EPS (1e-7)
#define gearup ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef long double ld;
typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<char> vc;
typedef vector<bool> vb;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<pair<int,int> > vpii;
typedef vector<vector<int> > vvi;
typedef vector<vector<char> > vvc;
typedef vector<vector<bool> > vvb;
typedef vector<vector<double> > vvd;
typedef vector<vector<string> > vvs;
typedef vector<ll> vl;
typedef vector<vector<ll> > vvl;
typedef vector<vector<vector<ll> > > vvvl;
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
//cout<<fixed<<setprecision(10);

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T> void debug(T v){rep(i,v.size()) cout<<v[i]<<" ";cout<<endl;}
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

struct Edge {
    long long to;
    long long cost;
};
using Graph = vector<vector<Edge> >;
using P = pair<long long, int>;
Graph G;

void dijkstra(const Graph &G, int sv, vl &dis, vl &prev) {
    int N = G.size();
    dis.resize(N, INF);
    priority_queue<P, vector<P>, greater<P> > pq;  // (仮の最短距離, 頂点)で昇順ソート
    dis[sv] = 0;
    pq.emplace(dis[sv], sv);
    while (!pq.empty()) {
        P p = pq.top();
        pq.pop();
        int v = p.second;
        if (dis[v] < p.first) {  // 最小値を取り出し、それが最短距離で無ければ無視
            continue;
        }
        for (auto &e : G[v]) {
            if (dis[e.to] > dis[v] + e.cost) {  // 最短距離候補なら追加
                dis[e.to] = dis[v] + e.cost;
                prev[e.to] = v;
                pq.emplace(dis[e.to], e.to);
            }
        }
    }
}

signed main()
{   
    gearup;
    int n,m; cin >> n >> m;
    G.resize(n);
    rep(i,m){
        int a,b; cin >> a >> b;
        a--;b--;
        G[a].push_back({b,1});
        G[b].push_back({a,1});
    }
    vl dist;
    vl prev(n);
    dijkstra(G,0,dist,prev); //ノード0からスタート

    out("Yes");
    rep1(i,n)out(prev[i]+1);

    return 0;
}


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

int ans[4];

int main(){
	int t,s;
	for(int i = 0;i < 4;i++){
		cin >> t >> s;
		int tei;
		switch(t){
		case 1:
			tei = 6000;
			break;
		case 2:
			tei = 4000;
			break;
		case 3:
			tei = 3000;
			break;
		case 4:
			tei = 2000;
			break;
		}
		ans[i] = tei*s;
	}
	for(int i = 0;i < 4;i++){
		cout << ans[i] << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
class UnionFind():
	def __init__(self, n):
		self.n = n
		self.root = [-1]*(n+1)
		self.rank = [0]*(n+1)

	def find(self, x):
		if(self.root[x] < 0):
			return x
		else:
			self.root[x] = self.find(self.root[x])
			return self.root[x]
			
	def unite(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if(x == y):
			return 0
		elif(self.rank[x] > self.rank[y]):
			self.root[x] += self.root[y]
			self.root[y] = x
		else:
			self.root[y] += self.root[x]
			self.root[x] = y
			if(self.rank[x] == self.rank[y]):
				self.rank[y] += 1

	def isSame(self, x, y):
		return self.find(x) == self.find(y)

	def size(self, x):
		return -self.root[self.find(x)]

def solve():
	n,q,*l = map(int,open(0).read().split())
	uf = UnionFind(n)
	for c,x,y in zip(*[iter(l)]*3):
		if c:
			print(0 + uf.isSame(x,y))
		else:
			uf.unite(x,y)
            
if __name__=="__main__":
	solve()


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

int main() {
  int N, H;
  cin >> N >> H;
  
  vector<int> a(N), b(N);
  for (int i = 0; i < N; i++) {
    cin >> a[i] >> b[i];
  }
  
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  


  
  // aの攻撃はa[N-1]，bの攻撃はa[N-1]より大きいものに限って大きい順に使う
  
  int damage = 0;
  int count = 0;
  
  for (int i = N-1; i >= 0; i--){
    if (b[i] < a[N-1]) break;
    damage += b[i];
    count++;
    if (damage >= H) {
      cout << count << endl;
      return 0;
    }
  } 
  
  count += (H-damage + a[N-1] - 1) / a[N-1];
  
  cout << count << endl;


}

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

int main(){
    int m,f,r;
    cin>>m>>f>>r;
    while(m!=-1||f!=-1||r!=-1){
        if(m==-1||f==-1){
            cout<<'F'<<endl;
        }
        else if(m+f>=80){
            cout<<'A'<<endl;
        }
        else if(m+f>=65){
            cout<<'B'<<endl;
        }
        else if(m+f>=50){
            cout<<'C'<<endl;
        }
        else if(m+f>=30&&r>=50){
            cout<<'C'<<endl;
        }
        else if(m+f>=30&&r<50){
            cout<<'D'<<endl;
        }
        else{
            cout<<'F'<<endl;
        }
        cin>>m>>f>>r;
    }
}


Measured memory_bytes: 3080
fun main(args: Array<String>) {
    var (h, w) = readLine()!!.split(" ").map { it.toInt() }
    while(h != 0 || w != 0) {
        if (h != 0 && w != 0) {
            val wide1 = "#".times(w)
            val wide2 = "#" + ".".times(w-2) + "#"
            println(wide1)
            for (i in 0 until h-2) {
                println(wide2)
            }
            println(wide1)
        }
        println("")
        val (h2, w2) = readLine()!!.split(" ").map { it.toInt() }
        h = h2
        w = w2
    }
}

private operator fun String.times(num: Int): String {
    var s = ""
    for (i in 0 until num) s += this
    return s
}



Measured memory_bytes: 32616
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#include <iomanip>
#include <map>
#include <bitset>
#include <cstdio>
#include <set>
#include <stack>
#include <queue>
#include <cassert>
#include <numeric>
#define rep(i,n) Rep(i,0,n)
#define Rep(i,k,n) for(int i=k ; i<n ; i++)
#define rep1(i,n) for(int i=1 ; i<=n ; i++)
#define Rep1(i,k,n) for(int i=k ; i<=n ; i++)
#define vi vector<int>
#define vii vector<vector<int>>
#define mii map<int,int>
#define Sort(v) sort(v.begin(),v.end())
#define Reverse(v) reverse(v.begin(),v.end())
#define ALL(a)  (a).begin(),(a).end()
#define pb push_back
//#define int ll
typedef long long ll;

const int md = 1000000007;
const int INF = 1<<30;
using namespace std;

double inverse(int x){
    return (1.0)/x;
}


int main(){
    int k; cin >> k;
    int a = k/2;
    cout << a*(k-a) << endl;
}


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

using namespace std;
typedef long long ll;
#define rep(i, s, e) for (int(i) = (s); (i) <= (e); ++(i))
#define all(x) x.begin(),x.end()


int main()
{
	string S, T; cin >> S >> T;
	vector<int> alpS(26, -1), alpT(26,-1);
	int len = S.size();
	vector<int> sChecker(len), tChecker(len);
	int sIndex = 0, tIndex = 0;
	rep(i, 0, len - 1)
	{
		if (alpS[S[i] - 'a'] == -1)
		{
			alpS[S[i] - 'a'] = sIndex;
			sChecker[i] = sIndex;
			++sIndex;
		}
		else
		{
			sChecker[i] = alpS[S[i] - 'a'];
		}
		if (alpT[T[i] - 'a'] == -1)
		{
			alpT[T[i] - 'a'] = tIndex;
			tChecker[i] = tIndex;
			++tIndex;
		}
		else
		{
			tChecker[i] = alpT[T[i] - 'a'];
		}
	}
	if (sChecker == tChecker)cout << "Yes" << endl;
	else cout << "No" << endl;
}

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

using namespace std;

int a[10000000];

int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	sort(a+1,a+n+1);
	a[0]=-1;
	int sum=0;
	for(int i=1;i<=n;i++)
	{
		if(a[i-1]!=a[i]) sum++;
	}
	cout<<sum;
	return 0;
}

Measured memory_bytes: 256
/*
  Author: @yash_31
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
#include <functional>
#define ll long long int
#define eb emplace_back
#define fatafat ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MOD 1000000007
#define ft first
#define sd second
#define mkpr make_pair
#define deb(x) std::cout<<#x<<":"<<x<<endl;
#define whole(x) (x).begin(),(x).end()
#define revwhole(x) (x).rbegin(),(x).rend()
#define endl "\n"
#define fbo find_by_order
#define ook order_of_key
#define init0(x) memset(x,0,sizeof(x));

using namespace std; 
using namespace __gnu_pbds;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update> gharKaSet;
 
const int maxlimit=2e5+2;
const ll inf=1e18;
//TTBDC

int main()
{
  fatafat
  int n;
  ll wt;
  cin>>n>>wt;
  vector<pair<ll,ll>> arr(n+1);
  for(int i=1;i<=n;i++){
    cin>>arr[i].ft>>arr[i].sd;    
  }
  sort(whole(arr));
  ll dp[n+1][wt+1];
  for(int i=0;i<=n;i++){
    for(int j=0;j<=wt;j++){
      if(i==0 || j==0){dp[i][j]=0;}
      else {
        dp[i][j]=dp[i-1][j];
        if(j-arr[i].ft>=0){
          dp[i][j]=max(dp[i][j],dp[i-1][j-arr[i].ft]+arr[i].sd);
        }
      }
    }
  }
  cout<<dp[n][wt];
  return 0;
}

Measured memory_bytes: 82444
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define ll long long

using namespace std;

inline ll read() {
    ll x = 0, f = 1; char ch = getchar();
    for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
    return x * f;
}

void write(ll x) {
    if(x < 0) {putchar('-'); write(-x); return ;}
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
    return ;
}

ll n, x, ans;

void dfs(ll a, ll b) {
    if(!(a % b)) {
        ans += (a << 1) - b;
        return ;
    }
    ans += a / b * b << 1;
    dfs(b, a % b);
    return ;
}

int main() {
    ans = n = read(); x = read();
    if(x >= n - x) dfs(x, n - x);
    else dfs(n - x, x);
    write(ans);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long int n;
  cin  >> n;
  long long int sum=0;
  for(long long int i=1;i<=n;i++){
    if(i%3==0||i%5==0){
      continue;
    }else{
      sum+=i;
    }
  }
  cout << sum << endl;
}

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

using namespace std;

#define YES cout << "YES" << endl;
#define NO  cout << "NO"  << endl;
#define Yes cout << "Yes" << endl;
#define No  cout << "No"  << endl;
 
#define INF INT_MAX
#define MOD 1000000007
#define PI  acos(-1)

using ll  = long long;
using ull = unsigned long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

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

bool IsPrime(ll num) {
    if (num < 2) {
        return false;
    } else if (num == 2) {
        return true;
    } else if (num % 2 == 0) {
        return false;
    }

    double sqrtNum = sqrt(num);
    for (ll i = 3; i <= sqrtNum; i+=2) {
        if (num % i == 0) {
            return false;
        }
    }

    return true;
}

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

    ll Q;
    cin >> Q;

    vector<ll> a(100000, 0);
    for (ll i = 0; i <= 100000; i++) {
        if (IsPrime(i) && IsPrime((i+1)/2)) {
            a[i] = 1;
        } else {
            a[i] = 0;
        }
    }

    vector<ll> s(100001, 0);
    for (ll i = 0; i <= 100001; i++) {
        s[i+1] = s[i] + a[i];
    }

    rep (i, Q) {
        ll l, r;
        cin >> l >> r;
        cout << s[r+1] - s[l] << endl;
    }

    return 0;
}

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

using namespace std;
using ll = long long;
// #define int ll
using PII = pair<ll, ll>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()

template<typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template<typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template<typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }

template<typename T> vector<T> make_v(size_t a) { return vector<T>(a); }
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts) {
    return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type
fill_v(T &t, const V &v) { t=v; }
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t, const V &v ) { for(auto &e:t) fill_v(e,v); }

template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a) {
    out<<'('<<a.first<<','<<a.second<<')'; return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
    out<<'[';
    for(const T &i: a) out<<i<<',';
    out<<']';
    return out;
}
template<class T>
ostream &operator <<(ostream& out, const set<T>& a) {
    out<<'{';
    for(const T &i: a) out<<i<<',';
    out<<'}';
    return out;
}
template<class T, class S>
ostream &operator <<(ostream& out, const map<T,S>& a) {
    out<<'{';
    for(auto &i: a) out<<i<<',';
    out<<'}';
    return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; // DRUL
const int INF = 1<<30;
const ll LLINF = 1LL<<60;
const ll MOD = 1000000007;

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

    ll h, w;
    cin >> h >> w;
    vector<string> a(h), b(h);
    REP(i, h) cin >> a[i];
    REP(i, h) cin >> b[i];

    ll ret = 0;
    REP(i, h) REP(j, w) {
        if(a[i][j] != b[i][j]) ret++;
    }
    cout << ret << endl;

    return 0;
}



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

int main(){
	int a, b, c, k;
	string str;
	while(1){
		k = 1;
		getline( cin, str );
		if( str.size() == 0 ){
			break;
		}
		sscanf( str.c_str(), "%d %d", &a, &b );
		c = a + b;
		while( c/10 > 0 ){
			c /= 10;
			k++;
		}
		printf("%d\n", k );
	}
	return 0;
}

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

int main() {
  int n;string s;cin>>n>>s;
  int ans=0;
  for(int i=1;i<n;i++){
    vector<int> l(26),r(26);
    rep(j,i)l[s[j]-'a']++;
    for(int j=i;j<n;j++)r[s[j]-'a']++;
    int cnt=0;
    rep(i,26){
      if(l[i]>0&&r[i]>0)cnt++;
    }
    ans=max(ans,cnt);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 3652
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <utility>
#include <vector>

using std::cout;
using std::cin;
using std::string;


int main()
{
  int a,b,c;
  cin >> a >> b >> c;
  int tmp = b / a;
  c = tmp < c ? tmp : c;
  std::cout << c << "\n";
  return 0;
}


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

signed main() {
    int N;
    cin >> N;

    vector<int> V(N);
    vector<int> C(N);
    for (int& x : V) cin >> x;
    for (int& x : C) cin >> x;

    int ans = 0;
    for (int i = 0; i < N; i++) {
        int t = V[i] - C[i];
        ans += t * (t > 0);
    }
    cout << ans << endl;
}


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

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

    int K[N],P[N];
    for (int i =0; i<N ;i++) {
        cin >> K[i];
        cin >> P[i];
    }

    for (int i=0; i<N ;i++) {
        if (K[i] < P[i]) {
            cout << K[i] << endl;
        } else if (K[i] % P[i] == 0) {
            cout << P[i] << endl;
        } else {
            cout << K[i] % P[i] << endl;
        }
    }

    return 0;
}



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

using namespace std;
const int maxn = 1e5 + 5;
int f[maxn], h[maxn], n;

int dp(int i)
{
    if (i > n) return 1e9;
    if (i == n) return 0;
    if (f[i] != -1) return f[i];
    f[i] = dp(i + 1) + abs(h[i] - h[i+1]);
    f[i] = min(f[i], dp(i + 2) + abs(h[i] - h[i+2]));
    return f[i];
}

int main()
{
    #ifdef NTMA 
        freopen("abc.inp", "r", stdin);
    #endif
    memset(f, 255, sizeof(f));
    cin >> n;
    for(int i=1; i<=n; ++i) cin >> h[i];
    cout << dp(1) << endl;
}

Measured memory_bytes: 4096
n, m = list(map(int, input().split()))

i = n
while i*i <= m:
    if m%i == 0:
        print(m//i)
        exit()
    i += 1
j = m//i
while j > 0:
    if m%j == 0:
        print(j)
        exit()
    j -= 1

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn], b[maxn], vis[maxn];
int n, m, ans;
int main() 
{
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) 
		scanf("%d", &a[i]);
	sort(a + 1, a + n + 1, greater<int>());
	for(int k = 30; k; --k)
	{
		for(int i = 1, j = n; i < j; )
		{
			if(a[i] + a[j] == (1 << k))
			{
				++ans;
				vis[i] = vis[j] = k;
				++i; 
				--j;
			}
			else if(a[i] + a[j] < (1 << k))
				--j;
			else
				++i;
		}
		m = 0;
		for(int i = 1; i <= n; ++i)
			if(vis[i] != k)
				b[++m] = a[i];
		n = m;
		for(int i = 1; i <= n; ++i)
			a[i] = b[i];
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 6052
#include<iomanip>
#include<iostream>
using namespace std;
    
int main()
{
  const double Pi=3.14159265359;
  double a;
  cin>>a;
  cout<<fixed<<setprecision(5)<<Pi*a*a<<" "<<2.0*a*Pi<<endl;
  return 0;
}

Measured memory_bytes: 3260
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define ALL(v) v.begin(), v.end()
typedef long long ll;
using namespace std;
int main(){
    int H,W; cin >> H >> W;
    vector<string> S(H);
    rep(i,H) cin >> S[i];

    int L[2005][2005];
    int R[2005][2005];
    int D[2005][2005];
    int U[2005][2005];

    rep(i,H){
        rep(j,W){
            if(S[i][j] == '#') L[i][j] = 0;
            else{
                if(j == 0) L[i][j] = 1;
                else L[i][j] = L[i][j-1] + 1;
            }
        }
    }

    rep(i,H){
        for(int j = W-1; j>=0;j--){
            if(S[i][j] == '#') R[i][j] = 0;
            else{
                if(j == W-1) R[i][j] = 1;
                else R[i][j] = R[i][j+1] + 1;
            }
        }
    }

    for(int i = H-1; i>=0;i--){
        rep(j,W){
            if(S[i][j] == '#') D[i][j] = 0;
            else{
                if(i == H-1) D[i][j] = 1;
                else D[i][j] = D[i+1][j] + 1;
            }
        }
    }

    rep(i,H){
        rep(j,W){
            if(S[i][j] == '#') U[i][j] = 0;
            else{
                if(i == 0) U[i][j] = 1;
                else U[i][j] = U[i-1][j] + 1;
            }
        }
    }

    int ans = 0;
    rep(i,H){
        rep(j,W){
            int tmp = L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3;
            ans = max(ans,tmp);
        }
    }

    cout << ans <<endl;
}


Measured memory_bytes: 67200
#include <bits/stdc++.h>
#include <math.h>
#include <cmath>

using namespace std;
using ll =long long;

bool is_int_lround(double x){
  return std::lround(x)==x;
}
int ketasuu(int x){
  int n=0;
  while(x>0){
    x /=10 ;
    n ++;
  }
  return n;
}
ll gcd11(ll x, ll y){
  long long a= max(x,y), b=min(x,y), c=a%b;
  while( c!=0){
    a =b;
    b =c;
    c = a%b;
  }
  return b;
}

int abs(int x, int y){
  if(x>=y){
    return x-y;
  }
  else if(y>x){
    return y-x;
  }
}
int main(){
  ll h;
  cin>>h;
  ll ans =0;
  ll bai=1;
  while(h >=1){
    h/=2 ;
    ans +=bai;
    bai *=2;
    
  }
  cout <<ans <<endl;
}



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

int n, option;

ll cur[2], res[2];

int main() {
    cin.sync_with_stdio(0); cin.tie(0);
    cin >> n;
    vector<ll> a(n);
    for (auto& i : a) cin >> i;
    
    // Which is going to be negative
    for (int i = 0; i < n; ++i) {
        cur[0] += a[i], cur[1] += a[i];
        if (!(i % 2) && cur[0] >= 0) {
            res[0] += cur[0] + 1;
            cur[0] = -1;
        } else if (i % 2 && cur[0] <= 0) {
            res[0] += abs(cur[0] - 1);
            cur[0] = 1;
        }

        if (i % 2 && cur[1] >= 0) {
            res[1] += cur[1] + 1;
            cur[1] = -1;
        } else if (!(i % 2) && cur[1] <= 0) {
            res[1] += abs(cur[1] - 1);
            cur[1] = 1;
        }
    }

    cout << min(res[0], res[1]);
}


Measured memory_bytes: 3936
#-*- coding:utf-8 -*-
N = int(input())
M = str(N)

if N % 1111 == 0:
    print("Yes")
elif (M[0] == M[1] )and (M[1] == M[2]):
    print("Yes")
elif (M[1] == M[2] )and (M[2] == M[3]):
    print("Yes")
else :
    print("No")

Measured memory_bytes: 3064
use std::io;
fn main() {
    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    let n: i64 = buf.trim().parse().unwrap();
    let offset = '0'.to_digit(10).unwrap();
    let sn: i64 = format!("{}", n).chars().map(|c| (c.to_digit(10).unwrap() - offset) as i64).sum();
    println!("{}", if n % sn == 0 {"Yes"} else {"No"});
}


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

int main()
{
  std::vector<int> hills;
  int temp;
  while(std::cin >> temp) {
    hills.push_back(temp);
  }
  std::sort(hills.begin(), hills.end());

  auto it = hills.rbegin();
  for(int i = 0; i < 3; ++i) {
    std::cout << *it << std::endl;
    it++;
  }
}

Measured memory_bytes: 3144
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1000000007;
const double PI=3.14159265358979;
const ll INF= pow(10,18);
typedef pair<ll,ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
string abc="abcdefghijklmnopqrstuvwxyz";
string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main() {
  vvl vec(3,vl(3,0));
  rep(i,3){
    rep(j,3){
      cin >> vec[i][j];
    }
  }
  bool a=true;
  rep(i,3){
    rep(j,3){
      if(vec[0][j]-vec[i][j]!=vec[0][0]-vec[i][0]){
        a=false;
      }
    }
  }
  rep(i,3){
    rep(j,3){
      if(vec[i][0]-vec[i][j]!=vec[0][0]-vec[0][j]){
        a=false;
      }
    }
  }
  if(a){
    cout << "Yes" << endl;
  }
  else
    cout << "No" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define pll pair<ll,ll>
#define pii pair<int,int>
#define rep(i,n) for(int i=0;i<n;i++)
#define sz(x) ((ll)(x).size())
#define pb push_back
#define mp make_pair
#define bit(n) (1LL<<(n))
#define F first
#define S second
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll INF = 1LL<<60;
const ll mod = (int)1e9 + 7;

int f;
int s;
 
queue<int> q;
int df[100010];
int ds[100010];
vector<vector<int>> edge(100010);
 
void dfs(){
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(auto x:edge[now]){
            if(df[x]==0){
                df[x]=df[now]+1;
                q.push(x);
            }
        }
    }
}
void dss(){
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(auto x:edge[now]){
            if(ds[x]==0){
                ds[x]=ds[now]+1;
                q.push(x);
            }
        }
    }
}

int main() {
    int n,u,v;
    cin >> n >> u >> v;
    u--;
    v--;
    rep(i,n-1){
        int x,y;
        cin >> x >> y;
        x--;
        y--;
        edge[x].pb(y);
        edge[y].pb(x);
    }
    fill(df,df+100010,0);
    fill(ds,ds+100010,0);
    q.push(u);
  	df[u]=1;
    dfs();
    q.push(v);
  	ds[v]=1;
    dss();
    int mx=0;
    rep(i,n){
        if(df[i]<=ds[i])chmax(mx,ds[i]-2);
      	cerr << df[i] << ' ' << ds[i] << endl;
    }
    cout << mx;
}

/*



 */



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

int64_t A, B, C, D;
map<int64_t, int64_t> memo;

int64_t f(int64_t x)
{
    if (x == 0)
        return 0;
    if (x == 1)
        return D;

    if (memo.count(x))
    {
        return memo.at(x);
    }

    int64_t res = (x < INT64_MAX / D) ? x * D : INT64_MAX;
    res = min(res, f(x / 2) + A + D * (x - (x / 2) * 2));
    if (x % 2 != 0)
    {
        res = min(res, f(x / 2 + 1) + A + D * ((x / 2 + 1) * 2 - x));
    }
    res = min(res, f(x / 3) + B + D * (x - (x / 3) * 3));
    if (x % 3 != 0)
    {
        res = min(res, f(x / 3 + 1) + B + D * ((x / 3 + 1) * 3 - x));
    }
    res = min(res, f(x / 5) + C + D * (x - (x / 5) * 5));
    if (x % 5 != 0)
    {
        res = min(res, f(x / 5 + 1) + C + D * ((x / 5 + 1) * 5 - x));
    }
    memo[x] = res;
    return res;
}

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

    for (int t = 0; t < T; t++)
    {
        int64_t N;
        cin >> N >> A >> B >> C >> D;
        memo = map<int64_t, int64_t>();
        cout << f(N) << endl;
    }
}

Measured memory_bytes: 4388
#include<iostream>
#include<cstring>
int check(char*a,int s,int e)
{
	char b[100];
	int m=0,i;
	for(i=e;i>=0;i--)
	{
		b[m]=a[i];
		m++;
	}
	 m=0;
	for(i=s;i<=e;i++)
	{
		if(a[i]!=b[m])
		return 0;
		
		m++;
	}
	return 1;
}
using namespace std;
int main()
{
	int n,a1,b,c;
	char a[100];
	cin>>a;
	n=strlen(a);
	a1=check(a,0,n-1);
	int x=(n-1)/2;
	x=x-1;
	b=check(a,0,x);
	int y=(n+3)/2;
	y=y-1;
	c=check(a,y,n-1);
	if(a1==1 && b==1 && c==1)
	cout<<"Yes";
	else
	cout<<"No";
	return 0;
	
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC target("sse4")
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
#define MP make_pair
#define PB push_back
#define X first
#define Y second

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ITER(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define Aint(a) a.begin(), a.end()
#define SZ(a) (int)((a).size())
#define FIint(a, value) memset(a, value, sizeof(a))
#define debug(a) cout << #a << " = " << a << endl;

const double PI = acos(-1.0);
const LL INF = 1000 * 1000 * 1000 + 7;
const LL LINF = (LL)INF * INF;

const int mod = 1000 * 1000 * 1000 + 7;
const int MAX = 1107;

string s;
int cnt[256];
int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
	cin >> s;
	for(auto x : s)
	{
		cnt[x]++;
	}
	LL ans = 1;
	for(int i = 0; i < 256; i++)
	{
		ans *= (cnt[i] + 1);
		ans %= mod;
	}
	ans--;
	if(ans < 0)
		ans += mod;
	cout << ans;
    return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;

#define REP(i, n) for(ll i = 0; i < n; i++)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOR(i, m, n) for(ll i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
#define  DESC std::greater<int>() //sort 3rd arg

int main()
{
	int x, y;
	cin >> x >> y;

	for (int i = 0; i <= x;i++) {
		if (i * 2 + (x - i) * 4 == y) {
			cout << "Yes" << endl;
			return 0;
		}
	}

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



Measured memory_bytes: 3624
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
const long long INF = 1LL << 60;
typedef pair<int, int> P;

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int main()
{
    int H, W;
    cin >> H >> W;
    vector<string> s(H);

    rep(i, H) cin >> s[i];

    vector<vector<int>> dis(H, vector<int>(W, -1));
    queue<P> que;
    que.push({0, 0});
    dis[0][0] = 0;
    while (!que.empty()) {
        int x = que.front().first, y = que.front().second;
        que.pop();
        if (x == W - 1 && y == H - 1) break;
        rep(i, 4) {
            int tx = dx[i] + x, ty = dy[i] + y;
            if (tx >= W || tx < 0 || ty >= H || ty < 0 || s[ty][tx] == '#' || dis[ty][tx] != -1) continue;
            dis[ty][tx] = dis[y][x] + 1;
            que.push({tx, ty});
        }
    }

    int b = 0;
    rep(i, H) {
        rep(j, W) {
            if (s[i][j] == '#') b++;
        }
    }

    int ans = H * W - b - 1;
    if (dis[H - 1][W - 1] == -1) ans = -1;
    else ans -= dis[H - 1][W - 1];
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
using namespace std;
using ll = long long;
using vi = vector<int>;
using pii = pair<ll, ll>;
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  string x;
  while (cin >> x) {
    int a = 0, b = 0;
    for (int i = 0; i < x.length() - 2; i++) {
      if (x.substr(i, 3) == "JOI")
        a++;
      else if (x.substr(i, 3) == "IOI")
        b++;
    }
    cout << a << endl << b << endl;
  }
}


Measured memory_bytes: 3192
#include <stdio.h>
#include <string.h>

int main(void){
    char weather[3][7]={"Sunny","Cloudy","Rainy"};
    char s[7];
    scanf("%s", s);
    int i;
    for(i=0;i<3;i++){
        if(strcmp(weather[i],s)==0){
            printf("%s\n",weather[(i+1)%3]);
        }
    }
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define INF 1e9+7
#define rep(i,n) for(ll i=0;i<n;i++)
#define pii pair<int,int>
#define pll pair<ll,ll>
const int maxn = 1000000;
ll mod = INF;
ll n;
ll ans=0;

int main(){
    cin >> n;
    ans=1;
    rep(i,n){
        ans=(ans*10)%mod;
    }

    ll sub1=1;
    ll sub2=1;
    ll sub3=1;

    rep(i,n){
        sub1=(sub1*9)%mod;
    }

    sub2=sub1;

    rep(i,n){
        sub3=(sub3*8)%mod;
    }

    ans=ans-sub1-sub2+sub3;

    while(ans<0)ans+=mod;

    cout << ans<<endl;

    return 0;
}

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

bool used[5005][5005];
map<int,int> mp;

int main(){
  int N;
  cin>>N;
  vector<int> A(N);
  for(int i=0;i<N;i++) cin>>A[i];

  sort(A.begin(),A.end());

  for(int i=0;i<N;i++) mp[A[i]]=i+1;
  int ans=0;
  for(int i=0;i<N;i++){
      for(int j=i+1;j<N;j++){
          if(used[i][j]) continue;
          used[i][j]=1;
          int diff=A[j]-A[i];
          int now=A[j];
          int res=1;
          int pre=j;
          while(mp.count(now+diff)){
              int tar=mp[now+diff]-1;
              res++;
              now+=diff;
              used[pre][tar]=1;
              pre=tar;
          }
          ans=max(ans,res);
      }
  }


  cout<<ans+1<<endl;

  return 0;
}



Measured memory_bytes: 27460
#include <bits/stdc++.h>
#include <iostream>
#include<math.h>
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
int main()
{
    int64_t N, M;
    cin >> N >> M;
    vector<int64_t>vec(M);
    for (int64_t i=0; i<M; i++) {
        cin >> vec.at(i);
    }

    sort(vec.begin(), vec.end());

    if (N >= M) {
        cout << 0 << endl;
    } else {
        int64_t sum = 0;
        vector<int64_t>abs_;
        int64_t hikaku = vec[0];
        for (int64_t i=1; i<M; i++) {
            int64_t idoukyori = abs(vec[i] - hikaku);
            abs_.emplace_back(idoukyori);
            hikaku = vec[i];
            sum += idoukyori;
        }

        sort(abs_.begin(), abs_.end(), greater<int64_t>());
        int64_t i=0;
        // なるべく長い移動距離をパスするようにコマを置く
        while (N > 1) {
            sum -= abs_[i];
            i++;
            N -= 1;
        }

        cout << sum << endl;
    }
    return 0;
}

Measured memory_bytes: 5044
n,a,b,c=map(int,input().split())
l=[int(input())for _ in range(n)]
ans = 12345678901234

for i in range(4**n):
    aa=0
    bb=0
    cc=0
    cnt = 0
    for j in range(n):
        flag = ((i//(4**j))%4)
        if flag == 0:
            aa += l[j]
            cnt += 1
        if flag == 1:
            bb += l[j]
            cnt += 1          
        if flag == 2:
            cc += l[j]
            cnt += 1
    if aa==0 or bb==0 or cc == 0:
        continue
    aans = abs(aa-a)+abs(bb-b)+abs(cc-c)+10*(cnt-3)
    ans = min(ans,aans)
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<int> &o) {
    int a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
//const ll mod = 1e10;

typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;

map<ll, int> factorize(ll n) {
    map<ll, int> res;

    for (ll i = 2; i * i <= n; i++) {
        if (n % i != 0) {
            continue;
        }
        res[i] = 0;
        while (n % i == 0) {
            n /= i;
            res[i]++;
        }
    }

    if (n != 1) res[n] = 1;
    return res;
}


int main() {
    ll n, p;
    cin >> n >> p;

    auto f = factorize(p);

    ll ans = 1;
    for (auto &e : f) {
        ll c = e.second / n;
        rep(_, c) {
            ans *= e.first;
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 3604
#include<stdio.h>
long long Mod = 1000000007, Inv[4010000], F[4010000], InvF[4010000], D[2010][2010];
long long Comb(int a, int b){
    return F[a]*InvF[b]%Mod*InvF[a-b]%Mod;
}
int n, K;
int main(){
    int i, j;
    scanf("%d%d",&n,&K);
    if(K==1){
        printf("1\n");
        return 0;
    }
    Inv[1]=F[0]=InvF[0]=1;
    for(i=2;i<=n*K;i++){
        Inv[i] = Inv[Mod%i] * (Mod-Mod/i)%Mod;
    }
    for(i=1;i<=n*K;i++){
        F[i]=F[i-1]*i%Mod;
        InvF[i]=InvF[i-1]*Inv[i]%Mod;
    }
    for(i=0;i<=n;i++){
        for(j=i;j<=n;j++){
            if(i==0&&j==0)D[i][j]=1;
            if(i) D[i][j] = D[i-1][j];
            if(j>i) D[i][j] = (D[i][j] + D[i][j-1]* Comb(n*K - (n-i) - (n-j)*(K-1) - 1, K-2))%Mod;
        }
    }
    printf("%lld\n",D[n][n]*F[n]%Mod);
}

Measured memory_bytes: 116608
#!/usr/bin/env python3
#AGC35 A

import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))


n = I()
a = LI()
if sum(a) == 0:
    print('Yes')
elif n % 3 != 0:
    print('No')
else:
    b = list(Counter(a).items())
    b.sort(key = itemgetter(0))
    if len(b) == 2:
        if b[0][0] == 0 and b[0][1] == n//3 and b[1][1] == n//3*2:
            print('Yes')
            quit()
    elif len(b) == 3:
        if b[0][0]^b[1][0]^b[2][0] == 0:
            if b[0][1] == n//3 and b[1][1] == n//3 and b[2][1] == n//3:
                print('Yes')
                quit()
    print('No')


Measured memory_bytes: 60140
#include <iostream>
#include <algorithm>
#include <string>
#include <functional>
#include <math.h>
#include <map>
using namespace std;

int main() {
	int n;
	int a[2][100];
	cin >> n;
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}
	int ans = 0, count = 0;
	for (int i = 0; i < n; i++) {
		count = 0;
		for (int j = 0; j <= i; j++) {
			count += a[0][j];
		}
		for (int u = i; u < n; u++) {
			count += a[1][u];
		}
		ans = max(ans, count);
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256