akhauriyash/Code-Regression huggingface dataset:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


K = I()
A = LI()
A.reverse()

m,M = 2,2
for i in range(K):
    a = A[i]
    if (m+(a-1))//a > M//a:
        print(-1)
        exit()
    else:
        m = a*((m+(a-1))//a)
        M = a*(M//a)+(a-1)

print(m,M)


Measured memory_bytes: 86476
#include <cstdio>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <climits>

using namespace std;

const int len = 100010;
int n,m,a[12] = {1,3,1,2,1,2,1,1,2,1,2,1};

int main() {
    cin >> n >> m;
    if (a[n-1]!=a[m-1]) cout << "No" << endl;
     else cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>

using namespace std;

#define sz(x) (int) x.size()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end())
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x)) 
#define y1 aksjdaskdjksjfksdjf
#define left kdnvldvoiwejifejg
#define right lkdsjflksdjfdjfk
#define prev asdasfsadjkjsdfjs

const int NEED[] = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};

int n, m;
int a[15];
int dp[10500];
vector<int> ans;

int main() { 

  scanf("%d %d", &n, &m);
  for (int i = 0; i < m; i++) {
    scanf("%d", &a[i]);
  }
  sort(a, a + m);
  reverse(a, a + m);

  memset(dp, -1, sizeof(dp));
  dp[0] = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < m; j++) {
      int use = NEED[a[j]];
      if (i - use >= 0) {
        dp[i] = max(dp[i], 1 + dp[i - use]);
      }
    }
  }

  while (n) {
    // cerr << n << endl;
    for (int j = 0; j < m; j++) {
      int use = NEED[a[j]];
      if (n - use >= 0 && dp[n] == 1 + dp[n - use]) {
        n -= use;
        ans.push_back(a[j]);
        // cerr << a[j] << endl;
        break;
      }
    }
  }

  for (int x : ans) {
    printf("%d", x);
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 384
import java.util.Scanner;

class Main{
	
	public static void main(String[] args){
		
		Scanner scan = new Scanner(System.in);
		int w = scan.nextInt();
		int h = scan.nextInt();
		int x = scan.nextInt();
		int y = scan.nextInt();
		int r = scan.nextInt();
		
		if((x - r) >= 0 && (y - r) >= 0 && (w - x) >= r && (h - y) >= r){
			System.out.println("Yes");
		}else{
			System.out.println("No");
		}
		
	}
	
}

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

int main() {
    int n;
    cin >> n;
    int all_ptn = 1;
    rep(i,n) all_ptn *= 3;
    int evens = 0;
    rep(i, n) {
        int a;
        cin >> a;
        if (a%2 == 0) evens++;
    }
    int odd_ptn = 1;
    rep(i, evens) odd_ptn *= 2;
    cout << all_ptn - odd_ptn << endl;
    return 0;
}

Measured memory_bytes: 3536
import           Control.Applicative
import           Control.Monad
import           Data.List.Split



getResult :: [Int] -> Int -> Int
getResult nums count = case filter even nums of
  a | null a    -> count
    | otherwise -> getResult (map (`div` 2) a) count + 1

main :: IO ()
main = do
  n <- readLn
  print $ (^) 2 (getResult [1 .. n] 0)


Measured memory_bytes: 508
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class Main {
    public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int h = sc.nextInt();
		int w = sc.nextInt();
		int k = sc.nextInt();
		char[][] grid = new char[h][w];
		for(int i = 0; i < h; i++){
		    String s = sc.next();
		    grid[i] = s.toCharArray();
		}
		
		
		// 計算
		long result = 0;
		for(int ih = 0; ih < (1<<h); ih++){
			for(int iw = 0; iw < (1<<w); iw++){
			    long cnt = 0;
			    for(int i = 0; i < h; i++){
		            for(int j = 0; j < w; j++){
		                if(((ih>>i)&1) == 1) continue;
		                if(((iw>>j)&1) == 1) continue;
		                if(grid[i][j] == '#') cnt++;
		            }
		        }
		        if(cnt == k) result++;
			}
		}
		
		
		// 出力
		System.out.println(result);
	}
	
	public static class Scanner {
		private BufferedReader br; private StringTokenizer tok;
		public Scanner(InputStream is) throws IOException { br = new BufferedReader(new InputStreamReader(is));}
		private void getLine() throws IOException { while(!hasNext()) tok = new StringTokenizer(br.readLine());}
		private boolean hasNext() { return tok != null && tok.hasMoreTokens();}
		public String next() throws IOException { getLine(); return tok.nextToken();}
		public int nextInt() throws IOException { return Integer.parseInt(next());}
		public long nextLong() throws IOException { return Long.parseLong(next());}
		public double nextDouble() throws IOException { return Double.parseDouble(next());}
	}
}



Measured memory_bytes: 26160
import java.util.Scanner;
public class Main {

    
    	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		String s=sc.nextLine();
		long K = sc.nextLong();
		double days  = 5*Math.pow(10, 15);
		long count=0;
		for(int i=0;i<s.length();i++) {
			
			int n = Integer.parseInt(s.charAt(i)+"");
			double m = Math.pow(n, days);
			count+=m;
			if (K<=count) 
			{System.out.println(n);
				break;}
		

		}
		

	}

}


Measured memory_bytes: 22868
#include <stdio.h>
#define rep(i, n) for(int i = 0; i < n; ++i)

int main(void) {
  int n, i, j;
  scanf("%d", &n);
  char r[n][n];
  rep(i, n) rep(j, n) r[i][j] = 0;
  rep(i, n) {
    int u, k;
    scanf("%d%d", &u, &k);
    u--;
    rep(j, k) {
      int v;
      scanf("%d", &v);
      v--;
      r[u][v] = 1;
    }
  }
  rep(i, n) {
    rep(j, n - 1) printf("%d ", r[i][j]);
    printf("%d\n", r[i][n - 1]);
  }
  return 0;
}


Measured memory_bytes: 2116
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <iostream>
#include <climits>
#include <cfloat>

typedef long long ll;

using namespace std;

int main()
{
	int q[] = { 2, 3, 5 };
	int v[] = { 380, 550, 850 };
	int dq[] = { 5, 4, 3 };
	double dis[] = { 0.2, 0.15, 0.12 };
	const int MaxG = 100;
	int vv[3][MaxG];
	for (int i = 0; i < 3; ++i)
	{
		for (int j = 0; j < MaxG; ++j)
		{
			if (j % q[i] != 0)
			{
				vv[i][j] = 100000000;
				continue;
			}
			int sack = (j+q[i]-1) / q[i];
			int disSack = sack / dq[i] * dq[i];
			vv[i][j] = v[i]*sack - (int)(v[i]*disSack*dis[i] + 0.1);
		}
	}

	int dp[3+1][MaxG];
	for (int i = 0; i < 4; ++i)
		for (int j = 0; j < MaxG; ++j)
		dp[i][j] = 1000000;
	dp[0][0] = 0;

	for (int i = 0; i < 3; ++i)
		for (int j = 0; j < MaxG; ++j)
			for (int k = 0; k+j < MaxG; ++k)
				dp[i+1][j+k] = min(dp[i+1][j+k], dp[i][j] + vv[i][k]);

	int g;
	while (cin >> g && g)
		cout << dp[3][g/100] << endl;

	return 0;
}

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

signed main() {
  string T; cin >> T;
  rep(i, T.size()) if(T[i] == '?') T[i] = 'D';
  
  cout << T << endl;
}

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

int main() {
    int n, m;
    int k[30];
    int a[30][30];
    int f[30] = {0};
    int ans = 0;
    
    cin >> n >> m;
    
    for (int i = 0; i < n; i++) {
        cin >> k[i];
        
        for (int ii = 0; ii < k[i]; ii++) {
            cin >> a[i][ii];
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int ii = 0; ii < k[i]; ii++) {
            //cout << "f[" << a[i][ii] - 1 << "]=" << f[a[i][ii] - 1] << endl;
            f[a[i][ii] - 1]++;
        }
    }
    
    for (int i = 0; i < m; i++) {
        //cout << "f[" << i << "]=" << f[i] << endl;
        
        if (f[i] == n) {
            ans++;
        }
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;

int main(void) {
  string S;
  ll N, K;
  cin >> S >> K;
  N = S.length();

  ll dp[N][N][K + 1];
  REP(l, 0, N) REP(r, l, N) REP(k, 0, K + 1) dp[l][r][k] = 0;
  REP(l, 0, N) REP(k, 0, K + 1) dp[l][l][k] = 1;
  REP(l, 0, N - 1) if(S[l] == S[l + 1]) dp[l][l + 1][0] = 2;
  REP(l, 0, N - 1) REP(k, 1, K + 1) dp[l][l + 1][k] = 2;
  REP(s, 0, N) REP(l, 0, N - s) {
    ll r = l + s;
    REP(k, 0, K + 1) {
      if(l + 1 <= r - 1 && S[l] == S[r]) dp[l][r][k] = max(dp[l][r][k], dp[l + 1][r - 1][k] + 2);
      if(l + 1 <= r) dp[l][r][k] = max(dp[l][r][k], dp[l + 1][r][k]);
      if(l <= r - 1) dp[l][r][k] = max(dp[l][r][k], dp[l][r - 1][k]);
      if(k > 0 && l + 1 <= r - 1) dp[l][r][k] = max(dp[l][r][k], dp[l + 1][r - 1][k - 1] + 2);
      if(k > 0) dp[l][r][k] = max(dp[l][r][k], dp[l][r][k - 1]);
    }
  }
  cout << dp[0][N - 1][K] << endl;
}


Measured memory_bytes: 211456
#include<bits/stdc++.h>
using namespace std;
const int N=2000000;
int n,a[N+1],k,b[N+1];
int main()
{
	cin>>k>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	sort(a+1,a+n+1);
	b[1]=k-a[n]+a[1];
	for(int i=2;i<=n;i++)b[i]=b[i-1]+a[i]-a[i-1];
	//for(int i=1;i<=n;i++)cout<<b[i]<<" ";
	//cout<<endl;
	int sum=0,sum2=0x7fffffff;
	for(int i=1;i<=n;i++)
	{
		//cout<<sum2<<' ';
		sum2=min(b[i]+b[n]-b[i+1],sum2);
	}
//	cout<<endl;
//	cout<<b[n]-b[1]<<endl<<sum2<<endl;
	cout<<min(b[n]-b[1],sum2);
}

Measured memory_bytes: 5120
#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 "debug.h"
#endif

const int N = 31;

ll p[N];

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

	p[0] = 1;
	for (int i = 1; i < N; i++) p[i] = p[i - 1] * 3LL;

	int q;
	cin >> q;

	while (q--) {
		ll x1, y1, x2, y2;
		scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
		x1--, y1--, x2--, y2--;

		int at_level = 30;
		ll ans;
		while (true) {
			if (at_level == 0) {
				ans = abs(x1 - x2) + abs(y1 - y2);
				break;
			}

			ll row1 = x1 / p[at_level - 1];
			ll col1 = y1 / p[at_level - 1];
			ll row2 = x2 / p[at_level - 1];
			ll col2 = y2 / p[at_level - 1];

			if (row1 != row2 && col1 != col2) {
				ans = abs(x1 - x2) + abs(y1 - y2);
				break;
			}
			if (row1 == row2 && col1 == col2) {
				at_level--;
				continue;
			}

			if (row1 == row2 && row1 % 3 == 1 && abs(col1 - col2) > 1) {
				ans = abs(y1 - y2);
				ll rem_sum = x1 % p[at_level - 1] + x2 % p[at_level - 1];
				ll down = rem_sum + 2;
				ll up = 2LL * p[at_level - 1] - rem_sum;
				ans += min(down, up);
				break;
			}
			if (col1 == col2 && col1 % 3 == 1 && abs(row1 - row2) > 1) {
				ans = abs(x1 - x2);
				ll rem_sum = y1 % p[at_level - 1] + y2 % p[at_level - 1];
				ll down = rem_sum + 2;
				ll up = 2LL * p[at_level - 1] - rem_sum;
				ans += min(down, up);
				break;
			}

			at_level--;
		}

		printf("%lld\n", ans);
	}

	return 0;
}

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

namespace _0019
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            List<long> list = new List<long>();
            long answer = 1;
            for(int i = 1; i <= n; ++i)
            {
                list.Add(i);
            }
            for(int i = 0; i < n; ++i)
            {
                answer = answer * list[i];
            }
            Console.WriteLine(answer);
        }
    }
}



Measured memory_bytes: 13888
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define db(...) " [" << #__VA_ARGS__ << ": " << __VA_ARGS__ << "] "
using ii=long long;
const int N = 1 << 18;
ii p[N * 2];
ii hae(int a, int b)
{
    ii r = 0;
    for (a += N, b += N; a <= b; a /= 2, b /= 2) {
        if (a & 1) r = max(r, p[a++]);
        if (~b & 1) r = max(r, p[b--]);
    }
    return r;
}
void muuta(int k, ii x)
{
    k += N;
    p[k] = max(p[k], x);
    for (k /= 2; k; k /= 2) {
        p[k] = max(p[k * 2], p[k * 2 + 1]);
    }
}
int main()
{
    int n;
    cin >> n;
    vector<int> H(n);
    vector<int> A(n);
    for (int i = 0; i < n; ++i) {
        cin >> H[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> A[i];
    }
    for (int i = 0; i < n; ++i) {
        ii x = 0;
        if (H[i] != 1) {
            x = hae(1, H[i] - 1);
        }
        muuta(H[i], x + A[i]);
    }
    cout << hae(1, n) << "\n";
}


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

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    int dp[2][n] = {0};

    cin >> dp[0][0];
    for (int i = 1; i < n; ++i) {
        int a1;
        cin >> a1;
        dp[0][i] = dp[0][i-1] + a1;
    }

    cin >> dp[1][0];
    dp[1][0] += dp[0][0];

    for (int i = 1; i < n; ++i){
        int a2;
        cin >> a2;
        dp[1][i] = max(dp[1][i-1] + a2, dp[0][i] + a2);
    }
    cout << dp[1][n-1] << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

using ll = long long;
using ull = unsigned long long;
const int INF = 1e9;
const int MOD = 2019;

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

    int N = (int)S.size();
    vector<int> n(N + 1);
    int d = 1;
    for (int i = 0; i < N; i++) {
        int s = (int)(S[N - 1 - i] - '0');
        n[i + 1] = (n[i] + d * s) % 2019;
        d = (d * 10) % 2019;
    }
    map<int, int> mp;
    for (int i = 0; i < N + 1; i++) {
        mp[n[i]]++;
    }
    ll ans = 0;
    for (auto p : mp) {
        ans += ((ll)p.second * (ll)(p.second - 1)) / 2;
    }
    cout << ans << endl;
}


Measured memory_bytes: 4352
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<math.h>
using namespace std;

const int N=2e5+5;
const int M=5e5+5;
int n,k,u,v,dep[N];
int E,ot[M],ne[M],g[N];

void add(int u,int v)
{
	ot[++E]=v;
	ne[E]=g[u];
	g[u]=E;
}

void init()
{
	int i;
	scanf("%d%d",&n,&k);
	for(i=1;i<n;++i)
	{
		scanf("%d%d",&u,&v);
		add(u,v),add(v,u);
	}
}

namespace Subtask_odd
{
	int nowx,nowy;
	
	void dfs(int x,int fath)
	{
		int p,to;
		for(p=g[x];p;p=ne[p])
		{
			to=ot[p];
			if(to==nowx||to==nowy||to==fath) continue;
			dep[to]=dep[x]+1;
			dfs(to,x);
		}
	}
	
	void work()
	{
		int i,j,p,to,cnt=0,ans=n;
		for(i=1;i<=n;++i)
			for(p=g[i];p;p=ne[p])
			{
				to=ot[p];cnt=0;
				if(to>i) continue;
				nowx=to,nowy=i;
				dep[nowx]=dep[nowy]=0;
				dfs(nowx,0),dfs(nowy,0);
				for(j=1;j<=n;++j) cnt+=(dep[j]>k/2);
				ans=min(ans,cnt);
			}
		printf("%d\n",ans);
	}
}

namespace Subtask_even
{
	void dfs(int x,int fath)
	{
		int p,to;
		for(p=g[x];p;p=ne[p])
		{
			to=ot[p];
			if(to==fath) continue;
			dep[to]=dep[x]+1;
			dfs(to,x);
		}
	}
	
	void work()
	{
		int i,j,cnt=0,ans=n;
		for(i=1;i<=n;++i)
		{
			cnt=dep[i]=0;
			dfs(i,0);
			for(j=1;j<=n;++j) cnt+=(dep[j]>k/2);
			ans=min(ans,cnt);
		}
		printf("%d\n",ans);;
	}
}

int main()
{
	init();
	if(k&1) Subtask_odd::work();
	else Subtask_even::work();
	return 0;
}

Measured memory_bytes: 2432
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

S = read().rstrip().decode('utf-8')

def F(S):
    yield int(S)
    for i in range(len(S)-1):
        left = S[:i+1]
        right = S[i+1:]
        x = int(left)
        for y in F(right):
            yield x + y

answer = sum(F(S))
print(answer)


Measured memory_bytes: 3060
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<unordered_map>
#include<cstdlib>
#define LL long long
#define LD long double
using namespace std;
const int NN=20;
const int MM= +117;
int read(){
	int fl=1,x;char c;
	for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
	if(c=='-'){fl=-1;c=getchar();}
	for(x=0;c>='0'&&c<='9';c=getchar())
		x=(x<<3)+(x<<1)+c-'0';
	return x*fl;
}
void open(){
	freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
}
void close(){
	fclose(stdin);
	fclose(stdout);
}


int m,n;
unordered_map<LL,LL> dp[NN][NN];
LL bas;
LL a[NN]={};
LL id(int x,int y){
	return x*bas+y;
}
LL getdp(int l,int r,int x1,int x2){
	if(r-l+1<=2)return 0;
	LL pos=id(x1,x2);
	if(dp[l][r].find(pos)!=dp[l][r].end())return dp[l][r][pos];
	LL ans=1e18;
	for(int i=l+1;i<r;++i){
		ans=min(ans,getdp(l,i,x1,x1+x2)+getdp(i,r,x1+x2,x2)+a[i]*(x1+x2));
	}
	return dp[l][r][pos]=ans;
}
int main(){
	//open();
	n=read();
	for(int i=1;i<=n;++i)a[i]=read();
	bas=1<<(n+1);
	LL ans=a[1]+a[n]+getdp(1,n,1,1);
	printf("%lld\n",ans);
	close();
	return 0;
}

Measured memory_bytes: 11264
#include <bits/stdc++.h>
using namespace std;
#define elif else if
int main(){
  int a,b,c;
  cin>>a>>b>>c;
  if(a==b&&b==c)cout<<1<<endl;
  elif(a==b||a==c||b==c)cout<<2<<endl;
  else cout<<3<<endl;


  return 0;
}


Measured memory_bytes: 256
// Problem: C - Vacation
// Contest: AtCoder - Educational DP Contest
// URL: https://atcoder.jp/contests/dp/tasks/dp_c
// Parsed on: 2020-09-06 13:01:53
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <algorithm>
#include <cmath>
#include <iostream>
#include <numeric>
#include <string>
#include <vector>

#define fastio                        \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> a(3, vector<int>(n));
    for (int t = 0; t < n; t++) cin >> a[0][t] >> a[1][t] >> a[2][t];

    vector<vector<int>> dp(3, vector<int>(n, numeric_limits<int>::min()));

    dp[0][0] = a[0][0];
    dp[1][0] = a[1][0];
    dp[2][0] = a[2][0];

    for (int t = 1; t < n; t++) {
        for (int s = 0; s < 3; s++) {
            for (int r = 0; r < 3; r++) {
                if (s == r) continue;
                dp[s][t] = max(dp[s][t], dp[r][t - 1] + a[s][t]);
            }
        }
    }
    cout << max(dp[0][n - 1], max(dp[1][n - 1], dp[2][n - 1]));
    return 0;
}


Measured memory_bytes: 5452
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<tuple>
#include<list>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define lb lower_bound
#define pb push_back
#define mp make_pair
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define INF (1 << 30) - 1
#define LLINF (1LL << 61) - 1
// #define int ll
using namespace std;
const int MOD = 1000000007;
const int MAX = 100010;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N,M,R,r[10],A[100010],B[100010],C[100010],D[210][210];
    vector<ll> v;
    cin>>N>>M>>R;
    rep(i,R){
        cin>>r[i];
        r[i]--;
        v.pb(r[i]);
    }
    sort(v.begin(),v.end());
    rep(i,N)rep(j,N){
        if(i!=j){
            D[i][j]=LLINF;
        }else{
            D[i][j]=0;
        }
    }
    rep(i,M){
        cin>>A[i]>>B[i]>>C[i];
        A[i]--;B[i]--;
        D[A[i]][B[i]]=C[i];
        D[B[i]][A[i]]=C[i];
    }
    rep(k,N){
        rep(i,N){
            rep(j,N){
                D[i][j]=min(D[i][j],D[i][k]+D[k][j]);
            }
        }
    }
    ll ans=LLINF;
    do{
        ll ans1=0;
        rep(i,R-1){
            ans1+=D[v[i]][v[i+1]];
        }
        ans=min(ans,ans1);
    }while(next_permutation(v.begin(),v.end()));
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 2688
S = str(input())

ans = 'Yes'
for i in range(len(S)):
  if i%2==0:
    if S[i] != 'h':
      ans = 'No'
      break
  else:
    if S[i] != 'i':
      ans = 'No'
      break
if len(S) %2 != 0:
  ans = 'No'
    
print(ans)

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

using namespace std;
typedef long long ll;
#define rep(i, j, n) for (int i = j; i < n; i++)
#define out(ans) cout << ans << endl;
const long long mod = 1e9 + 7;

int main(){

  int a,b,c;cin>>a>>b>>c;
  int k;cin>>k;

  int sum=a+b+c;
  int ma=max(a,max(b,c));
  sum-=ma;

  out(sum+ma*(1<<k));

  return 0;
}


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

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

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

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

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


signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  string s,t; cin>>s>>t;
  ll a,b; cin>>a>>b;
  string u; cin>>u;
  if(s==u) a--;
  else b--;
  cout<<a<<' '<<b<<endl;
}


Measured memory_bytes: 256
package main

import (
	"fmt"
)

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

	m := map[int]int{}
	for i := 0; i < n; i++ {
		var t int
		fmt.Scan(&t)
		m[t]++
	}

	c := 0
	for k, v := range m {
		if k > v {
			c += v
		} else {
			c += v - k
		}
	}

	fmt.Println(c)

}


Measured memory_bytes: 10188
#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mk make_pair
#define all(v) v.begin(),v.end()
#define fi first
#define se second
#define vl vector<long long int>
#define vvl vector<vector<ll> > 
#define fo(i,a,b) for(int i=a;i<b;i++)
#define rof(i,a,b)  for(int i=b;i>=a;i--)
using namespace std;
ll mod=1000000007;
ll dfs(ll node,ll vis[],ll dp[],vector<ll> adj[])
{
    if(vis[node])
        return dp[node]+1;
    vis[node]=1;ll maxi=0;
    for(ll i=0;i<adj[node].size();i++)
    {
        maxi = max(maxi,dfs(adj[node][i],vis,dp,adj));
    }
    dp[node] = maxi;
    return maxi+1;
}
int main()
{
    ll n,m;cin>>n>>m;
    vector<ll> adj[n];
    fo(i,0,m)
    {
        ll x,y;cin>>x>>y;
        adj[x-1].pb(y-1);
    }
    ll dp[n+1],vis[n+1];
    memset(dp,-1,sizeof(dp));
    memset(vis,0,sizeof(vis));
    fo(i,0,n)
        if(!vis[i])
            dfs(i,vis,dp,adj);
    ll res=0;
    fo(i,0,n)
        res = max(res,dp[i]);
    cout << res;
}



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

int main(){
  int n;
  cin >> n;
  vector<vector<P>> g(n);
  rep(i,n-1) {
    int u, v, w;
    cin >> u >> v >> w;
    u--; v--;
    g[u].emplace_back(make_pair(v, w));
    g[v].emplace_back(make_pair(u, w));
  }
  vector<int> res(n,-1);
  auto dfs = [&](auto& f, int p, int u, int c)->void{
    res[u] = c;
    for (auto v : g[u]) {
      if (p == v.first) continue;
      if (res[v.first] != -1) continue;
      if (v.second & 1) f(f, u, v.first, 1-c);
      else f(f, u, v.first, c);
    }
  };
  dfs(dfs, -1, 0, 0);
  for (auto e : res) cout << e << endl;
  return 0;
}

Measured memory_bytes: 11648
def gcd(m, n)
	if m < n 
		gcd(n, m)
	elsif n == 0
		m
	else
		gcd(n, m % n)
	end 
end

$cache = {}
def inv(a)
	return $cache[a] if $cache[a]
	(1..25).each do |x|
		return $cache[a] = x if a * x % 26 == 1
	end
end

n = gets.to_i
n.times do
	code = gets.chomp
	(1..25).each do |a|
		next if gcd(a, 26) > 1
		(0..25).each do |b|
			decoded = code.each_char.map {|c|
				next c if c == " "
				x = c.ord - ?a.ord
				((x + 26 - b) * inv(a) % 26 + ?a.ord).chr
			}.join
			if decoded =~ /\bthis\b|\bthat\b/
				puts decoded
			end
		end	
	end
end

Measured memory_bytes: 8804
# -*- coding: utf-8 -*-
n, m = map(int, input().split())

l_max = 1
r_min = n
for i in range(m):
    li, ri = map(int, input().split())
    if l_max < li:
        l_max = li
    if r_min > ri:
        r_min = ri

print(r_min-l_max+1 if r_min-l_max >= 0 else 0)


Measured memory_bytes: 3060
import re,sys
t='X'
for e in sys.stdin:
 for i in'0123456789'[any([len(x)>1 and x[0]=='X' for x in re.split('[+=]',e.strip())]):]:
  l,r=e.replace(t,i).split('=')
  if sum(map(int,l.split('+')))==int(r):print(i);break
 else:print('NA')


Measured memory_bytes: 6560
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<list>
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<cstring>
#include<stack>
#include<functional>
using namespace std;

struct Human{
	int n,h,w;
	double bmi;
	void calcBMI(){
		bmi = (double)w/(h*0.01*h*0.01);
	}
	bool operator <(const Human &h)const{
		if(abs(22-bmi)==abs(22-h.bmi)) return n<h.n;
		return abs(22-bmi)<abs(22-h.bmi);
	}
};
Human h[1000000];

int main(){
	int N;
	while(cin>>N,N){
		for(int i=0;i<N;i++){
			cin>>h[i].n>>h[i].h>>h[i].w; h[i].calcBMI();
		}
		sort(h,h+N); printf("%d\n",h[0].n);
	}
	return 0;
}

Measured memory_bytes: 1192
w,h,n = map(int,input().split())
mans = [list(map(int,input().split())) for _ in range(n)]
X = [i for i in range(w + 1)]
Y = [i for i in range(h + 1)]
def flatten(nested_list):
  return [e for inner_list in nested_list for e in inner_list]
remove_X = []
remove_Y = []
for i in range(n):
  x = mans[i][0]
  y = mans[i][1]
  a = mans[i][2]
  if a == 1:
    remove_X.append(X[:x])
  elif a == 2:
    remove_X.append(X[x + 1:])
  elif a== 3:
    remove_Y.append(Y[:y])
  else:
    remove_Y.append(Y[y + 1:])
dis_X = set(flatten(remove_X))
dis_Y = set(flatten(remove_Y))
for x in dis_X:
  X.remove(x)
for y in dis_Y:
  Y.remove(y)
if len(X) == 0 or len(Y) == 0:
  print(0)
else:
  print((max(X) - min(X)) * (max(Y) - min(Y)))

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

typedef long long ll;

int main(){
  ll A,B,C,D; cin >> A >> B >> C >> D;
  ll N; cin >> N;
  
  // 2Lコスパ最強の方法
  vector<ll> v2l(4);
  v2l[0] = A * 8;
  v2l[1] = B * 4;
  v2l[2] = C * 2;
  v2l[3] = D;
  sort(v2l.begin(), v2l.end());
  
  ll v2 = v2l[0];

  vector<ll> v1l(3);
  v1l[0] = A * 4;
  v1l[1] = B * 2;
  v1l[2] = C;
  
  sort(v1l.begin(), v1l.end());
  ll v1 = v1l[0];
  
  cerr << v1 << " " << v2 << endl;
  
  ll ans = 0;
  ans += v2 * (N/2);
  ans += v1 * (N%2);
  cout << ans << endl;

}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(int)(n); ++i)

using namespace std;

int main(){
    int N, M;
    while(cin >> N >> M){
        vector<int> a(M);
        REP(i, M) cin >> a[i];
        REP(i, M) a[i]--;
        vector<int> height(M);
        vector<int> perm(N);
        REP(i, N) perm[i] = i;
        REP(i, M) swap( perm[ a[i] ], perm[ a[i] + 1 ] );

        function<int(int)> dfs = [&](int k) {
            if(k == M) {
                for(int i = 0; i < M; i++){
                    for(int j = i + 1; j < M; j++) {
                        if(height[i] == height[j]) {
                            if(abs(a[i] - a[j]) <= 1){
                                return INT_MAX;
                            }
                        }
                    }
                }
                vector<int> p(N);
                REP(i, N) p[i] = i;
                for(int h = 0; h < M; h++){
                    for(int i = 0; i < M; i++) {
                        if(height[i] == h) {
                            swap( p[ a[i] ], p[ a[i] + 1 ] );
                        }
                    }
                }
                if(perm == p) {
                    return *max_element(height.begin(), height.end()) + 1;
                } else {
                    return INT_MAX;
                }
            } else {
                int res = INT_MAX;
                for(int h = 0; h < M; h++){
                    height[k] = h;
                    res = min(res, dfs(k + 1));
                }
                return res;
            }
        };
        int res = dfs(0);
        assert(res != INT_MAX);
        cout << res << endl;
    }
    return 0;
}

Measured memory_bytes: 1204
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;

#[allow(dead_code)]
fn read_as_vec<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()

}

#[allow(dead_code)]
fn read_as_string() -> String{
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn radian_to_degree(x: f64) -> f64{
    return x * 180.0 / std::f64::consts::PI;
}

fn solve_a(a: f64, b: f64, x: f64){
    let a_x: f64 = (2.0*x)/(a*b);

    let radian = (b/a_x).atan();
    println!("{}", radian_to_degree(radian));
}

fn solve_b(a: f64, b: f64, x: f64){
    let empty = a*a*b-x;
    let b_x = (2.0 * empty) / (a * a);

    let radian = (b_x/a).atan();
    println!("{}", radian_to_degree(radian));
}

fn main(){
    let line = read_as_vec::<u64>();

    let (a, b, x) = (line[0], line[1], line[2]);

    if ((a*a*b) as f64)/2.0 >= x as f64{
        solve_a(a as f64, b as f64, x as f64);
    }else{
        solve_b(a as f64, b as f64, x as f64);
    }

 }


Measured memory_bytes: 4352
#include<bits/stdc++.h>
#define rep(X,A,B) for(int X=A;X<=B;++X)
#define tep(X,A,B) for(int X=A;X>=B;--X)
#define LL long long
const int N=100010;
const int M=200010;
const int maxn=100000;
const LL INF=1e17;
using namespace std;

int n,K;
int na=0,nb=0;
LL a[N],b[N];

void READ(){
	int x;
	scanf("%d%d",&n,&K);
	rep(i,1,n){
		scanf("%d",&x);
		if(x>=0)a[++na]=x;
		else b[++nb]=-x;
	}
	sort(a+1,a+na+1);
	sort(b+1,b+nb+1);
}

void SOLVE(){
	LL ans=INF;
	if(na>=K)ans=min(ans,a[K]);
	if(nb>=K)ans=min(ans,b[K]);
	rep(i,1,K-1){
		if(i>na||(K-i)>nb)continue;
		int j=K-i;
		ans=min(ans,min(a[i]*2+b[j],b[j]*2+a[i]));
	}
	printf("%lld\n",ans);
}

int main(){
	READ();
	SOLVE();
	return 0;
}

Measured memory_bytes: 1024
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for(int i = 0 ; i < n ; i++) a[i] = sc.nextInt();
		long[] sum = new long[n + 1];
		for(int i = 0 ; i < n ; i++) sum[i + 1] = sum[i] + a[i];
		long ans = Long.MAX_VALUE;
		for(int i = 1 ; i < n ; i++) {
			long dis = Math.abs(sum[i] - (sum[n] - sum[i]));
			ans = Math.min(ans, dis);
		}
		System.out.println(ans);
	}
}


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

signed main() {
  int N;
  cin >> N;
  
  vector<int> A(N);
  for( int i = 0; i < N; i++ ) cin >> A.at(i);
  
  if( N == 1 ){
    cout << 1 << endl;
    return 0;
  }
  
  int hantei = -1;
  //0のとき単調非減少(増えてく)、1のとき単調非増加(減ってく)
  
  int ans = 0;
  for( int i = 1; i < N; i++ ){
    if( hantei == -1 ){
      if( A.at(i) > A.at(i-1) ) hantei = 0;                     
      else if( A.at(i) < A.at(i-1) ) hantei = 1;
    }else if( A.at(i) > A.at(i-1) && hantei == 1 ){
      hantei = -1;
      ans++;
    }else if( A.at(i) < A.at(i-1) && hantei == 0 ){
      hantei = -1;
      ans++;
    }
  }
  cout << ans+1 << endl;
    
}



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

bool isRectangle(int a[]) {
  if (!(a[0] == a[1] && a[2] == a[3])) return false;
  if (!(a[4] == a[5] && a[6] == a[7])) return false;
  if (!(a[8] == a[9] && a[10] == a[11])) return false;
  return true;
}

int main() {
  int e[12];
  for (int i = 0; i < 12; i++)
    cin >> e[i];

  for (int i = 0; i < 12; i++)
    for (int j = i; j > 0; j--)
      if (e[j - 1] > e[j]) {
	int t = e[j - 1];
	e[j - 1] = e[j];
	e[j] = t;
      }

  if (isRectangle(e)) cout << "yes" << endl;
  else cout << "no" << endl;

  return 0;
}

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<string>s(n);
    vector<int>p(n);
    for(int i=0;i<n;i++)cin >> s[i] >> p[i];
    int a[n];
    for(int i=0;i<n;i++)a[i] = i;
    bool chk = false;
    while(!chk){
        chk = true;
        for(int i=0;i<n-1;i++){
            if(s[a[i]] > s[a[i+1]]){
                swap(a[i],a[i+1]);
                chk = false;
            }else if(s[a[i]] == s[a[i+1]]){
                if(p[a[i]] < p[a[i+1]]){
                    swap(a[i],a[i+1]);
                    chk = false;
                }
            }
        }
    }
    for(int i=0;i<n;i++)cout << a[i]+1<<endl;
    
}


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

vector<int> line_plus_plus(int n, int x, int y) {
  
  vector<int> ans(n-1, 0);

  for(int i=1; i<=n-1; i++) {
    for(int j=i+1;j<=n;j++) {
      int k = min(min(abs(i-j), abs(i-x)+1 + abs(y-j)), abs(i-y) + 1 + abs(x-j));
      //cout << i << ", " << j << " -> " << k << endl;
      ans[k-1] = ans[k-1] +1;
    }
  }

  return ans;
}


int main() {
  int n, x, y;

  cin >> n;
  cin >> x;
  cin >> y;

  vector<int> ans = line_plus_plus(n, x, y);

  for(int i = 0; i<ans.size();i++) {
    cout << ans[i];
    if(i != ans.size() - 1) {
      cout << endl;
    }
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int A,B,C,X,Y;
	cin >> A >> B >> C >> X >> Y;
	long long answer = 0;
	
	if(A + B > 2 * C){
		int tmp = min(X,Y);
		answer += tmp * 2 * C;
		X -= tmp;
		Y -= tmp;
	}
	if(A > 2 * C){
		int tmp = max(X,0);
		answer += tmp * 2 * C;
		X -= tmp;
		Y -= tmp;
	}
	if(B > 2 * C){
		int tmp = max(Y,0);
		answer += tmp * 2 * C;
		X -= tmp;
		Y -= tmp;
	}
	answer += max(X,0) * A;
	answer += max(Y,0) * B;
	
	cout << answer << endl;
		
	
	
	return 0;
}

Measured memory_bytes: 256
a,v=map(int,input().split())
b,w=map(int,input().split())
t=int(input())

if v<w:
    print("NO")
elif v==w:
    if a==b:
        print("YES")
    else:
        print("NO")
elif v>w:
    t0 = abs((a-b)/(v-w))
    if t0<=t:
        print("YES")
    else:
        print("NO")

Measured memory_bytes: 61808
#include <iostream>
#define R(i,n) for (int i;i<<(n);i++)
#include<algorithm>
#include<vector>
using namespace std;

int main() {
    int n,x,y,z;
    int ans=0;
 
    cin >> n;    
    vector<int>vec(n+1);
    for(int i=1;i<=100;i++){
        for(int j=1;j<=100;j++){
            for(int k=1;k<=100;k++){
                int s=i*i+j*j+k*k;
                s+=i*j+j*k+k*i;
                if (s<=n){
                    vec.at(s)++;
                }
            }
        }
    }

    for(int i=1;i<=n;i++){
        cout<<vec.at(i)<<endl;
    }
    

    return 0;


}


Measured memory_bytes: 3636
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
INF = 10**9
mod = 10**9+7

H,W = I()
cost = [l() for _ in range(10)]
A = [l() for _ in range(H)]
ans = 0
for k in range(10):
    for i in range(10):
        for j in range(10):
            cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])
for i in range(H):
    for j in range(W):
        if A[i][j] > -1:
            ans += cost[A[i][j]][1]
print(ans)

Measured memory_bytes: 10432
public class Main {

    public static void main(String[] args) {

        java.util.Scanner sc = new java.util.Scanner(System.in);
        // 数値
        int n1 = sc.nextInt();
        boolean flg = false;
        for (int i = 1; i <= n1; i++) {
            int n = sc.nextInt();
            if (n % 2 == 0) {
                if (!(n % 3 == 0 || n % 5 == 0)) {
                    flg = true;
                    break;
                }
            }
        }

        if (flg) {
            System.out.println("DENIED");
        } else {
            System.out.println("APPROVED");
        }

    }
}


Measured memory_bytes: 35672
#include <algorithm>
#include <climits>
#include <iostream>
#include <queue>
#include <stack>
#include <utility>
#include <vector>

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

#define INF 1000000000

using namespace std;

vector<vector<pair<int, long long>>> g;
vector<bool> visited;
vector<long long> dist;
queue<pair<int, long long>> q;

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

    g = vector<vector<pair<int, long long>>>(N);
    visited = vector<bool>(N, false);
    dist = vector<long long>(N, INF);

    REP(i, M) {
        int s, t;
        cin >> s >> t;

        s--;
        t--;

        int w;
        cin >> w;

        g[s].emplace_back(t, w);
        g[t].emplace_back(s, -w);
    }

    REP(i, N) {
        if (visited[i] == false) {
            q.emplace(i, 0);

            while (!q.empty()) {
                int p = q.front().first;
                q.pop();

                for (auto& e : g[p]) {
                    long long next_dist = dist[p] + e.second;
                    if (visited[e.first]) {
                        if (dist[e.first] != next_dist) {
                            cout << "No" << endl;
                            return 0;
                        }
                    } else {
                        dist[e.first] = next_dist;
                        visited[e.first] = true;
                        q.emplace(e.first, 0);
                    }
                }
            }
        }
    }

    cout << "Yes" << endl;

    return 0;
}


Measured memory_bytes: 14448
#include <iostream>
#include <string>
#include <string.h>
#include <math.h>
#include <cmath>
#include <vector>
#include <algorithm>
#define ll long long

using namespace std;

const long long mod = 1e9+7;

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

    if((a+b)&1) cout << "IMPOSSIBLE" << endl;
    else cout << (a+b)/2 << endl;
}

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

namespace ABC066A
{
	class Program
	{
		static void Main(string[] args)
		{
			int a, b, c, s;
			string[] word = Console. ReadLine(). Split(' ');

			a = int.Parse(word[0]);
			b = int.Parse(word[1]);
			c = int.Parse(word[2]);

			int x = a + b;
			int y = b + c;
			int z = c + a;

			s = 100;

			s = x;
			if (y < s) s = y;
			if (z < s) s = z;

			Console.WriteLine(s);
		}
	}
}


Measured memory_bytes: 27516
/* author   : mpily :-()
title : Competing1.cpp
time :Sun Jan 19 14:54:36 2020

*/
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,b;
	cin>>a>>b;
	if(a < b){
		while(b--)cout<<a;
	}
	else{
		while(a--)cout<<b;
	}
	cout<<"\n";
	return 0;
}

Measured memory_bytes: 256
while True:
    H, W = map(int, input().split(' '))
    if H == W == 0:
        break
    odd_row = '#'
    even_row = '.'
    for i in range(W-1):
        if i % 2 == 0:
            odd_row += '.'
            even_row += '#'
        else:
            odd_row += '#'
            even_row += '.'
    for j in range(H):
        if j % 2 == 0:
            print(odd_row)
        else:
            print(even_row)
    print('')


Measured memory_bytes: 5608
process.stdin.resume();
process.stdin.setEncoding('utf8');

var lines = []
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});

reader.on('line', (line) => {
  lines.push(line);
});

reader.on('close', () => {
 var kn = lines[0].split(' ');
 var k = Number(kn[0]);
 var n = Number(kn[1]);
 var a = lines[1].split(' ');
 a = a.map(function(str) { return Number(str)});
 
 var kyori = [];
 kyori.push(k+a[0] - a[n-1]);

 for(i=0; i<n-1; i++){
   kyori.push(a[i+1] - a[i]);
 }

 // console.log(kyori);
 var max = kyori.sort((a, b)=> b - a)[0];
 var index = kyori.indexOf(max);
 kyori.splice(index,1);
 // console.log(kyori);
 var ans = kyori.reduce(function(a, x){return a + x;});
 console.log(ans);
});


Measured memory_bytes: 39468
# -*- coding: utf-8 -*-
def main():
    n = int(input())
    abc_list = []
    for i in range(n):
        abc_list.append(list(map(int, input().split())))
    dp = [[0] * 3 for i in range(n)]
    dp[0][0] = abc_list[0][0]
    dp[0][1] = abc_list[0][1]
    dp[0][2] = abc_list[0][2]
    # print(dp)
    for i in range(1, n):
        dp[i][0] = abc_list[i][0] + max(dp[i - 1][1], dp[i - 1][2])
        dp[i][1] = abc_list[i][1] + max(dp[i - 1][0], dp[i - 1][2])
        dp[i][2] = abc_list[i][2] + max(dp[i - 1][0], dp[i - 1][1])
        # print(dp)
    print(max(dp[-1]))
        
if __name__ == "__main__":
    main()

Measured memory_bytes: 101468
#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<cstring>
#include<math.h>
#include<bitset>
#include<queue>
// #include<bits/stdc++.h>
using namespace std;
#define ll long long


int main(){
  ll N;
  cin >> N;
  ll ans=N-1;
  for(ll i=1; i*i<=N; i++){
    if(N%i == 0){
      ans = min(ans, N/i+i-2);
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
mod = 10**9+7
H,W = map(int,input().split())
A = [input() for _ in range(H)]
dp = [[0] * (W+1) for _ in range(H+1)]
dp[0][1] = 1
for w in range(W):
    for h in range(H):
        if A[h][w] == ".":
            dp[h+1][w+1] = dp[h][w+1] + dp[h+1][w]
            dp[h+1][w+1] %= mod
print(dp[H][W])


Measured memory_bytes: 51440
#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define mod 1000000007
#define endl "\n"
#define pb push_back
#define f() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int main() {
  f();
  ll n,d,count=0;
  cin>>n>>d;
  ll a[n][d];
  for(ll i=0;i<n;i++)
  {
    for(ll j=0;j<d;j++)
    {
      cin>>a[i][j];
    }
  }
  for(ll i=0;i<n;i++)
  {
    for(ll j=i+1;j<n;j++)
    {
      ll ans=0;
      for(ll k=0;k<d;k++)
      {
        ans+=(a[i][k]-a[j][k])*(a[i][k]-a[j][k]);
      }
      double d =sqrt(ans);
    ll t=sqrt(ans);
    if(d==t)
    {
count++;
    }
    }
  }
    /* double d =sqrt(ans);
    ll t=sqrt(ans);
    if(d==t)
    {
count++;
    }
  }*/
  cout<<count<<endl;
  return 0;
}


Measured memory_bytes: 256
// Problem : A - A?C
// Contest : AtCoder - AtCoder Beginner Contest 166
// URL : https://atcoder.jp/contests/abc166/tasks/abc166_a
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include<bits/stdc++.h>
#include <unordered_map>
#define int int64_t
#define double long double
#define endl "\n"
#define PI 3.141592653589793238462643383279502884
#define sp(x)   setprecision(x)
#define ceil(a,b)   (a+(b-1))/b
#define LCM(a,b)    (a*b)/__gcd(a,b)
#define all(v)  v.begin(),v.end()
#define alls(s,v)  s.begin(),s.end(),v
#define gena(arr,n,nxt)  generate(arr,arr+n, nxt)
#define genv(v,nxt)  generate(v.begin(),v.end(), nxt)
#define base ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define exit return 0;
using namespace std;
const int N=500000;
bool prime[N];
void sieve(){
    memset(prime, true, sizeof(prime));
    for (int p=2; p*p<100000000; p++)
    {
        if (prime[p] == true)
        {
            for (int i=p*p; i<100000; i += p)
                prime[i] = false;
        }
    }
}
int nxt(){int x;cin >> x;return x;}
int32_t main(){
    base
	string s;
	cin>>s;
	cout<<(s=="ABC"?"ARC":"ABC");
    exit
}


Measured memory_bytes: 3616
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
//#include "h.h"
using namespace std;

#define ll long long
#define pint pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define pm(first, second) pb(mp(first, second))
#define SPACE " "
#define fpf first.first
#define fps first.second
#define spf second.first
#define sps second.second

#define all(VECTOR) (VECTOR).begin(), (VECTOR).end()

//parent[i]:ノード番号iの親のノード番号
//親が存在しないときは-(属するグループのサイズ)を格納
//parent = vector<int>(N, -1);で初期化
vector<int> parent;
//ノードXの根を返す
int root(int X){
	if(parent[X] < 0)return X;
	return parent[X] = root(parent[X]);
}
//ノードXが属するグループのサイズ(属するノード数)を返す
int size(int X){
	return -parent[root(X)];
}
//Xの属するグループとYの属するグループを繋ぐ
//それぞれの根どうしを繋ぐ
bool connect(int X, int Y){
	//根同士をつなぐため指すノードを根にする
	X = root(X);
	Y = root(Y);
	//すでに繋がっているときは繋がずにfalseを返す
	if(X == Y){
		return false;
	}
	//大きいほうに小さいほうを繋ぎたいので逆ならスワップ
	if(size(X) < size(Y))swap(X, Y);
	//繋がれる方のサイズを更新
	parent[X] += parent[Y];
	//繋ぐ方の親を設定
	parent[Y] = X;
	return true;
}

int main(){

	int N, M;
	cin >> N >> M;
	vector<int> A(M), B(M);
	for(int i = 0; i < M; i ++){
		cin >> A[i] >> B[i];
		A[i] --;
		B[i] --;
	}

	int ans = 0;
	vector<int> CA(M - 1), CB(M - 1);
	for(int i = 0; i < M; i ++){
		parent = vector<int>(N, -1);
		for(int j = 0; j < M; j ++){
			if(j == i)continue;
			else if(j < i){
				CA[j] = A[j];
				CB[j] = B[j];
			}
			else{
				CA[j - 1] = A[j];
				CB[j - 1] = B[j];
			}
		}
		for(int j = 0; j < M - 1; j ++){
			if(root(CA[j]) != root(CB[j])){
				connect(CA[j], CB[j]);
			}
		}
		if(root(A[i]) != root(B[i]))ans ++;
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>

int main() {
  size_t N;
  int Z, W;
  scanf("%zu %d %d", &N, &Z, &W);

  std::vector<int> a(N);
  for (auto& ai: a) scanf("%d", &ai);

  if (N == 1)
    return !printf("%d\n", abs(a[0]-W));

  printf("%d\n", std::max(abs(a[N-1]-W), abs(a[N-1]-a[N-2])));
}


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

using namespace std;

char board[55][55];

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

int main() {
    int H, W;
    scanf("%d%d", &H, &W);
    for(int i = 1; i <= H; i++) {
        getchar();
        for(int j = 1; j <= W; j++) {
            scanf("%c", &board[i][j]);
        }
    }
    for(int i = 1; i <= H; i++) {
        for(int j = 1; j <= W; j++) {
            if(board[i][j] == '#') {
                bool ok = false;
                for(int k = 0; k < 4; k++) {
                    int nx = i + dx[k];
                    int ny = j + dy[k];
                    if(nx > 0 && ny > 0 && nx <= H && ny <= W && board[nx][ny] == '#') ok = true;
                }
                if(!ok) {
                    printf("No");
                    return 0;
                }
            }
        }
    }
    printf("Yes");
    return 0;
}


Measured memory_bytes: 256