akhauriyash/Code-Regression huggingface dataset:
#include <iostream>

struct Monster
{
  int hp;
  int damage;
};

int main()
{
  Monster monster[2];	// taka, aoki

  
  std::cin >> monster[0].hp >> monster[1].damage >> monster[1].hp >> monster[0].damage;
  
  bool isTakaTurn = false;
  while(monster[0].hp > 0 && monster[1].hp > 0)
  {    
    isTakaTurn = !isTakaTurn;
    int idx = isTakaTurn? 1 : 0;
    
    monster[idx].hp -= monster[idx].damage;
  }
  
  std::cout << (isTakaTurn? "Yes" : "No" ) << std::endl;
  return 0;
}

Measured memory_bytes: 3584
#include<iostream>
#include<string>

int main() {
  int N; std::string S; std::cin >> N >> S;
  for(char c: S) {
    int a = c - 'A';
    (a += N) %= 26;
    char nc = a + 'A';
    std::cout << nc;
  }
  std::cout << std::endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <fstream>
#include <cmath>
#include <random>
#include <complex>
#include <functional>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)
using namespace std;
typedef vector<ll> vec;
typedef vector<vec> mat;

const ll inf = 1LL << 60;

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

const int MAX = 100010;
const int MOD = 1000000007;

ll fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
        fac[i] = fac[i-1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll COM (int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

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

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

    COMinit();

    ll N;
    cin >> N;
    vec x(N);
    Rep (i, N) {
        cin >> x[i];
    }

    ll ans = 0, prob = 0;
    Rep (i, N-1) {
        prob += fac[N-1] * modpow(i+1, MOD-2) % MOD;
        prob %= MOD;
        ans += (x[i+1] - x[i]) * prob % MOD;
        ans %= MOD;
    }

    cout << ans << endl;
}

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

using namespace std;

typedef long long ll;
typedef long double ld;

const int M = 20020;
const int B = 1e9;

int n, q[M], p[M];
int a[M], b[M];

void read() {
  cin >> n;
  for (int i = 1; i <= n; ++i)
    cin >> q[i];
  for (int i = 1; i <= n; ++i)
    p[q[i]] = i;
}

void kill() {
  a[0] = 0, b[0] = 0;
  for (int i = 1; i <= n; ++i) {
    a[i] = a[i - 1] + 1;
    b[i] = b[i - 1] + 1;
    if (a[i] + p[i] >= b[i]) {
      b[i] = a[i] + p[i];
    } else {
      a[i] = b[i] - p[i];
    }
  }

  for (int i = 1; i <= n; ++i)
    cout << b[i] << " ";
  cout << endl;
  for (int i = 1; i <= n; ++i)
    cout << B - a[i] << " ";
  cout << endl;
}

int main() {
  cout.precision(20);
  cout << fixed;
  ios_base::sync_with_stdio(false);
  read();
  kill();
}


Measured memory_bytes: 896
#include <cstdio>

const int maxn = 550;

int n, m;
char a[maxn], b[maxn][maxn], c[maxn][maxn];

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%s", a + 1);
		for (int j = 1; j <= m; ++j) {
			if(i == 1 || i == n) {
				b[i][j] = c[i][j] = '.';
			}
			else {
				if((i & 1) && j < m || j == 1) {
					b[i][j] = '#';
					c[i][j] = '.';
				}
				else {
					b[i][j] = '.';
					c[i][j] = '#';
				}
				if(a[j] == '#') {
					b[i][j] = c[i][j] = '#';
				}
			}
		}
		puts(b[i] + 1);
	}
	puts("");
	for (int i = 1; i <= n; ++i) {
		puts(c[i] + 1);
	}
	return 0;
}

Measured memory_bytes: 1280
#include<iostream>
#include<algorithm>
using namespace std;
int main() {
 int S, h, m, s;
 cin >> S;
 
 h = S / 3600;
 m = S % 3600 / 60;
 s = S % 3600 % 60;

 cout << h << ":" << m << ":" << s << endl;
}

Measured memory_bytes: 1164
#include <iostream>
using namespace std;
int main()
{
	int D, T, S;
	cin >> D >> T >> S;
	if (D % S == 0)
		if (T >= D / S)
			cout << "Yes" << "\n";
		else
			cout << "No" << "\n";
	else
		if (T >= D / S + 1)
			cout << "Yes" << "\n";
		else
			cout << "No" << "\n";
}

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

int main(){
    int a,b;
    cin >> a >> b;
    if(a >= b*2) cout << a - b*2 << endl;
  	else cout << 0 << endl;
}

Measured memory_bytes: 256
#include <cstdio>
#define MAXN 100005
char s[MAXN];
int a[27];
int main() {
	scanf("%s", s);
	for(int i = 0; s[i] != '\0'; i++) 
		a[s[i]-'a'] ++;
	for(int i = 0; i < 26; i++) 
		if(!a[i]) {
			printf("%c", i + 'a');
			return 0;
		}
	
	printf("None\n");
	return 0;
}

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

long long N, M, S;



// to (ginka, cost)
vector<pair<long long, pair<long long, long long> > >tree[100];

long long c[200];
long long d[200];
map<long long, long long> ans;

int main(){
	cin >> N >> M >> S;
	for(long long i = 0; i < M; i++) {
		long long u;
		long long v;
		long long a;
		long long b;
		cin >> u >> v >> a >> b;
		u--;v--;
		tree[u].push_back(make_pair(v, make_pair(a, b)));
		tree[v].push_back(make_pair(u, make_pair(a, b)));
	}

	for(long long i = 0; i < N; i++) {
		cin >> c[i] >> d[i];
	}


	//cost, (point, ginka)
	priority_queue< pair<long long, pair<long long, long long> >,
		vector<pair<long long, pair<long long, long long> > >,
		greater<pair<long long, pair<long long, long long> > > > Q;

	Q.push(make_pair(0, make_pair(0, S)));

	//          point, ginka
	map<pair<long long, long long>, long long> memo;
	while(!Q.empty()) {
		long long cost = Q.top().first;
		long long point = Q.top().second.first;
		long long ginka = Q.top().second.second;

		//cout << " point " << point << "ginka " << ginka << " cost " << cost << endl;

		if(ans.count(point) == 0) {
			ans[point] = cost;
			if(ans.size() == N) {
				break;
			}
		}

		Q.pop();

		if(memo.count(make_pair(point, ginka)) > 0) {
			continue;
		}

		memo[make_pair(point, ginka)] = cost;

		for(long long i = 0; i < tree[point].size(); i++) {
			long long nextpoint = tree[point][i].first;
			long long nextginka = tree[point][i].second.first;
			long long nextcost = tree[point][i].second.second;
			//銀貨を使って次のcityにいく
			if(ginka >= nextginka) {
				Q.push(make_pair(cost + nextcost, make_pair(nextpoint, ginka-nextginka)));
			}
		}

		//金貨を銀貨に交換する
		if(ginka < 300) {
			Q.push(make_pair(cost + d[point], make_pair(point, ginka + c[point])));
		}
	}

	for(long long i = 1; i < N; i++) {
		//cout << "ans[" << i << "=" << ans[i] << endl;
		cout << ans[i] << endl;
	}
}


Measured memory_bytes: 5416
using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;

class Program
{
    static void Main(string[] args)
    {
        string[] s1 = Console.ReadLine().Split(' ');
        int a = int.Parse(s1[0]);
        int b = int.Parse(s1[1]);
        int c = int.Parse(s1[2]);
        int sum = 0;

        a = a - c;
        while (true)
        {
            a = a - (b + c);
            if(a>=0)
            {
                sum++;
            }
            else
            {
                break;
            }
        }

        Console.WriteLine(sum);
    }
}

Measured memory_bytes: 11092
s = int(input())
a = [0]*4
a[0] = s//1000 
s = s-a[0]*1000
a[1] = s//100
s = s-a[1]*100
a[2] = s//10
s = s-a[2]*10
a[3] = s
if(a[0]==a[1] or a[1]==a[2] or a[2]==a[3]):
  print("Bad")
else:
  print("Good")

Measured memory_bytes: 9144
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        long K = sc.nextLong();
        int n = S.length();
        if(n == 1){
            System.out.println(S);
        }else{
             String[] a = new String[n];
            a = S.split("");
            int[] b = new int[n];
            for(int i = 0; i < n; i++){
                b[i] = Integer.parseInt(a[i]);
            }
            int count = 0;
            int ans = 0;
            for(int i = 0; i < K; i++){
                if(b[i] != 1){
                    ans = b[i];
                    break;
                }else{
                    count ++;
                }
                if(count >= K){
                    ans = 1;
                    break;
                }
            }
            System.out.println(ans);
        }
       
    }
}


Measured memory_bytes: 22612
import sys
def S(): return sys.stdin.readline().rstrip()

N,M = map(int,S().split())
AB = []
C = []
for _ in range(M):
    AB.append(tuple(int(i) for i in S().split()))
    C.append(sum(1<<(int(i)-1) for i in S().split()))

dp = [10**8+1]*(1<<N)
dp[0] = 0

for i in range(1<<N):
    for j in range(M):
        a,b = AB[j]
        c = C[j]
        m = i|c
        dp[m] = min(dp[m],dp[i]+a)

if dp[-1] == 10**8+1:
    print(-1)
else:
    print(dp[-1])

Measured memory_bytes: 42732
#include <bits/stdc++.h>
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define mid ((x + y) / 2)
#define left (ind * 2)
#define right (ind * 2 + 1)
#define mp make_pair
#define timer ((double)clock() / CLOCKS_PER_SEC)
#define endl "\n"
#define spc " "
#define d1(x) cerr<<#x<<":"<<x<<endl
#define d2(x, y) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<endl
#define d3(x, y, z) cerr<<#x<<":"<<x<<" "<<#y<<":"<<y<<" "<<#z<<":"<<z<<endl
#define fast_io() ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;

typedef long long int lli;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<double, double> dd;

const int N = (int)(1e6 + 5);
const int LOG = (int)(20);

lli n, ar[N], ans;

int main() {
	fast_io();
	// freopen("inp.in", "r", stdin);

	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> ar[i];
	for(int i = 1; i <= n; i++) {
		if(ar[i] % 2 == 0)
			ans += ar[i] / 2;
		else {
			ans += ar[i] / 2;
			if(ar[i + 1] > 0)
				ar[i + 1]--, ans++;
		}
	}
	cout << ans;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep2(i, a, n) for(ll i = a; i < (ll)(n); i++)
#define memi cout << endl
#define kono(n) cout << fixed << setprecision(n)
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define hina cout << ‘ ‘
const ll mei = (ll)1e9 + 7;

int main(){
  ll k = 0;
  string s, t;
  cin >> s >> t;
  rep(i, 3)
    if(s[i] == t[i])
      k++;
  cout << k;
  memi;
}

Measured memory_bytes: 256
#include<iostream>
#define MOD 1000000007
using namespace std;
int main(){
  long long n,c[26]={0},ans=1;
  cin>>n;
  char s;
  for(int i=0;i<n;i++){
    cin>>s;
    c[s-'a']++;
  }
  for(int i=0;i<26;i++)if(c[i])ans=ans*(c[i]+1)%MOD;
  cout<<ans-1<<endl;
  return 0;
}

Measured memory_bytes: 256
A, B, K = map(int, input().split())

for i in range(K):
    if i%2 == 0:
        if A%2 == 1:
            A -= 1
        A //= 2
        B += A
    else:
        if B%2 == 1:
            B -= 1
        B //= 2
        A += B

print(A, B)


Measured memory_bytes: 2940
import collections

n = int(input())
data = [input() for _ in range(n)]

counter_ = collections.Counter(data)

max_ = max(list(counter_.values()))

ans = []
for c_name in counter_:
  if counter_[c_name] == max_:
    ans.append(c_name)

ans = sorted(ans)
for a in ans:
  print(a)


Measured memory_bytes: 35572
#include<iostream>
#include<vector>
using namespace std;
typedef long long li;
#define repa(i,a,n) for(int i=(a);i<(n);i++)
#define rep(i,n) for(int i=0;i<(n);i++)
#define df 0
template<class T> void print(const T& t){ cout << t << "\n"; }
template<class T, class... Ts> void print(const T& t, const Ts&... ts) { cout << t; if (sizeof...(ts)) cout << " "; print(ts...); }

int main(){
  int n; cin >>n;
  vector<int> c(n-1),s(n-1),f(n-1);
  rep(i,n-1){
    cin >>c[i] >>s[i] >>f[i];
  }
  rep(j,n){
    int t=0;
    repa(i,j,n-1){
      //      if(df)print(s[i],f[i]);
      if(t<s[i])t=s[i];
      if(t%f[i])t=(t/f[i]+1)*f[i];
      t+=c[i];
    }
    print(t);
  }
}


Measured memory_bytes: 3592
from itertools import product
N,M=map(int,input().split())
x,y,z = [0]*N, [0]*N, [0]*N
for i in range(N):
  x[i],y[i],z[i] = map(int,input().split())

prod= product([1,-1],repeat=3)
ans=0
for p in prod:
  s=[(p[0]*x[i]+p[1]*y[i]+p[2]*z[i]) for i in range(N)]
  s.sort(reverse=True)
  tmp=sum(s[:M])
  ans=max(ans,tmp)
print(ans)

Measured memory_bytes: 9232
import Control.Applicative
import Control.Monad
import Data.Set as Set

main = do
    n <- read <$> getLine
    list <- replicateM n getLine
    putStrLn $ solve list

solve :: [String] -> String
solve list | Nothing == (fsolve list) = "No"
           | otherwise = "Yes"

fsolve :: [String] -> Maybe (String, Set.Set String)
fsolve list = Prelude.foldl (\acc elem -> acc >>= shiritori elem) (Just (initword,initset)) (tail list)
    where initword = head list
          initset = Set.fromList [initword]

shiritori :: String ->  (String, Set String) -> Maybe (String, Set String)
shiritori wd (lastwd, s)  | Set.member wd s = Nothing
                          | (head wd) /= (head (reverse lastwd)) = Nothing
                          | otherwise = Just (wd, Set.insert wd s)



Measured memory_bytes: 636
#include <cstdio>
#include <iostream>

using namespace std;

int main(void)
{
	int n;
	string s;

	cin >> n;
	cin >> s;

	int ans = 0;

	for(int i = 0; i < n; ++i){
		if(s[i] != 'A'){
			continue;
		}else{
			if(s.substr(i, 3) == "ABC"){
				++ans;
			}
		}
	}

	cout << ans << endl;

	return 0;
}



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

int main(){
    double x1,x2,y1,y2;
    cin >> x1 >> y1 >> x2 >> y2;
    double r;
    r=sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
    printf("%.12lf\n",r);
    return 0;
}


Measured memory_bytes: 3216
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pcc pair<char,char>
#define vi vector <int>
#define vl vector <ll>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d",x)
#define plld(x) printf("%lld",x)
#define pds(x) printf("%d ",x)
#define pllds(x) printf("%lld ",x)
#define pdn(x) printf("%d\n",x)
#define plldn(x) printf("%lld\n",x)
#define INF 2e9
#define INFLL 4e18
#define spn setprecision
#define fr(x,a,b,c) for(int x = a; x <= b; x+=c)
using namespace std;
ll multiply(ll num1, ll num2, ll mod) { // with mod > 1e9
	ll ans = 0;
	num1 %= mod;
	num2 %= mod;
	while (num2) {
		if (num2&1) {
			ans += num1;
			ans %= mod;
		}
		num1 *= 2;
		num1 %= mod;
		num2 /= 2;
	}
	return ans;
}
ll powmod2(ll base,ll exponent,ll mod){ // with mod > 1e9
	ll ans = 1;
	while (exponent) {
		if (exponent&1) {
			ans = multiply(ans, base, mod);
		}
		base = multiply(base, base, mod);
		exponent /= 2;
	}
	return ans;
}
ll powmod(ll base,ll exponent,ll mod){ // with mod < 1e9
	ll ans=1;
	while(exponent){
		if(exponent&1)ans=(ans*base)%mod;
		base=(base*base)%mod;
		exponent/=2;
	}
	return ans;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b,a%b);
}
const int upperlimit = 1e6+100;
const int mod = 1e9+7;
int ti[upperlimit];
int ci[upperlimit];
int main() {
	int n,t,ans=INF;
	sd(n);sd(t);
	for(int i = 1; i <= n; i++){
		sd(ci[i]);sd(ti[i]);
		if(ti[i]<=t) ans=min(ans,ci[i]);
	}
	if(ans==INF){
		printf("TLE");
		return 0;
	}
	pd(ans);
	return 0;
}

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

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

using namespace std;

int main(){
	for(int M,T,P,R;scanf("%d%d%d%d",&M,&T,&P,&R),M;){
		int AC[50]={},penalty[50]={},submit[50][10]={};
		rep(_,R){
			int m,t,p,j; scanf("%d%d%d%d",&m,&t,&p,&j); t--; p--;
			if(j==0){
				AC[t]++;
				penalty[t]+=m+20*submit[t][p];
			}
			submit[t][p]++;
		}

		pair<pair<int,int>,int> tmp[50];
		rep(i,T) tmp[i]=make_pair(make_pair(-AC[i],penalty[i]),-i);
		sort(tmp,tmp+T);
		rep(i,T) printf("%d%c",-tmp[i].second+1,i<T-1?tmp[i].first<tmp[i+1].first?',':'=':'\n');
	}

	return 0;
}

Measured memory_bytes: 1032
N, K = map(int, input().split())
h = [int(i) for i in input().split()]
INF = 10**9

c = [INF] * N
c[0] = 0

for i in range(N):
  tmp = []
  for j in range(1, min(K, i)+1):
    c[i] = min(c[i-j] + abs(h[i] - h[i-j]), c[i])
print(c[-1])

Measured memory_bytes: 52320
#include<bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i,n) for(int i=0;i<n;++i)
#define all(v) v.begin(), v.end()
#define PI 3.141592653589793238462643383279
#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))
typedef long long int ll;
typedef unsigned long long ull;
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 pair<ll,ll> P;
const long long MOD = 1e9+7;
const ll INF = 1LL << 60;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};

int main(){
    string n;
    cin >> n;
    ll ans = 0;

    for(int i = 0; i < n.size(); i++){
        string s(1,n[i]);
        ans += stoi(s);
    }

    if(ans % 9 == 0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }

}

Measured memory_bytes: 3724
#include <algorithm>
#include <array>
#include <climits> // INT_MAX, LONG_MAX, LLONG_MAX, UINT_MAX, ULONG_MAX, ULLONG_MAX
#include <cmath>
#include <cstdint>
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

#define ALL(x) (x).begin(), (x).end()
#define INF 1e9
#define LOG(x) cout << #x << " = " << (x) << endl
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)

using namespace std;

vector<int> A;

int count(long long r, int i) {
    if (i == (int)A.size()) {
        return r % 2 == 0 ? 1 : 0;
    }

    int c = 0;
    int ai = A[i];
    c += count(r * (ai - 1), i + 1);
    c += count(r * (ai + 0), i + 1);
    c += count(r * (ai + 1), i + 1);

    return c;
}

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

    REP(i, N) {
        int ai;
        cin >> ai;
        A.push_back(ai);
    }

    cout << count(1ll, 0) << endl;
    
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;
class Program
{
    static void Main()
    {
        var a = ReadLine().Split().Select(int.Parse).ToArray();
        var b = new int[6];
        b[0] = Abs(a[1] - a[0]) + Abs(a[2] - a[1]);
        b[1] = Abs(a[2] - a[0]) + Abs(a[1] - a[2]);
        b[2] = Abs(a[0] - a[1]) + Abs(a[2] - a[0]);
        b[3] = Abs(a[2] - a[1]) + Abs(a[0] - a[2]);
        b[4] = Abs(a[0] - a[2]) + Abs(a[1] - a[0]);
        b[5] = Abs(a[1] - a[2]) + Abs(a[0] - a[1]);
        WriteLine(b.Min());
    }
}


Measured memory_bytes: 13396
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
#include <cstdio>
#include <complex>
#include <cstring>
 
using namespace std;
 
typedef long long LL;
 
const int N = 5000 + 5;
const int M = 200 + 5;
const int INF = 1000000000 + 5;
 
int n, m;
int x[N];
int a[M];
LL tag[N << 2];
LL maxv[N << 2];
vector<pair<int, int> > st[M];

void push(int x) {
    if (tag[x]) {
        tag[2*x] += tag[x];
        maxv[2*x] += tag[x];
        tag[2*x+1] += tag[x];
        maxv[2*x+1] += tag[x];
        tag[x] = 0;
    }
}

void modify(int t, int l, int r, int a, int b, LL v)
{
    if (b < l || r < a) return;
    if (a <= l && r <= b) {
        tag[t] += v;
        maxv[t] += v;
        return;
    }
    push(t);
    int mid = (l + r) >> 1;
    modify(t << 1, l, mid, a, b, v);
    modify(t << 1 | 1, mid + 1, r, a, b, v);
    maxv[t] = max(maxv[t << 1], maxv[t << 1 | 1]);
}
 
LL query(int t, int l, int r, int a, int b)
{
    if (b < l || r < a) return 0;
    if (a <= l && r <= b) {
        return maxv[t];
    }
    push(t);
    int mid = (l + r) >> 1;
    return max(query(t << 1, l, mid, a, b), query(t << 1 | 1, mid + 1, r, a, b));
}
 
void solve()
{
    cin >> n >> m;
    for(int i = 0; i < n - 1; ++ i) {
        scanf("%d", x + i);
    }
 
    long long ans = 0;
    for(int j = 0; j < m; ++ j) {
        st[j].push_back(make_pair(INF, -1));
    }
 
    for(int i = 0; i < n; ++ i) {
        long long tmp = 0;
        for(int j = 0; j < m; ++ j) {
            scanf("%d", a + j);
            tmp += a[j];
        }
        ans = max(ans, tmp);
 
        for(int j = 0; j < m; ++ j) {
            while (a[j] >= st[j].back().first) {
                int r = st[j].back().second;
                int v = st[j].back().first;
                st[j].pop_back();
                int l = st[j].back().second + 1;
                modify(1, 0, n - 1, l, r, -v);
            }
            modify(1, 0, n - 1, st[j].back().second + 1, i, a[j]);
            st[j].push_back(make_pair(a[j], i));
        }
 
        if (i > 0) {
            modify(1, 0, n - 1, 0, i - 1, -x[i - 1]);
        }
        ans = max(ans, query(1, 0, n - 1, 0, i));
    }
    cout << ans << endl;
}
 
int main()
{
    solve();
    return 0;
}

Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<functional>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<tuple>
#include<stack>
#include<queue>
#include<deque>
#include<sstream>
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<bitset>
#include<time.h>
#include<cstdlib>
#include<cassert>
#define ll long long
#define fi first
#define se second
using namespace std;

//int n,m;
string s;
                   
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(10);
  cout<<fixed;
#ifdef LOCAL_DEFINE
    freopen("in", "r", stdin); 
    freopen("out","w",stdout);
#endif
  cin>>s;
  if((int)s.length()<4){
    cout<<"No"<<endl;
    return 0;
  }
  if(s.substr(0,4)=="YAKI"){
    cout<<"Yes"<<endl;
  }else {
    cout<<"No"<<endl;
  }
#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
  return 0;
}

Measured memory_bytes: 256
N = gets.to_i
P = gets.split.map(&:to_i)
Q = gets.split.map(&:to_i)

i = 0
pindex = 0
qindex = 0

(1..N).to_a.permutation(N) do |perm|
  pindex = i if perm == P
  qindex = i if perm == Q

  i += 1
end

puts (pindex - qindex).abs


Measured memory_bytes: 2172
#include <bits/stdc++.h>
#define ll long long int
#define ld double
#define f first
#define s second
#define pb push_back
#define mk make_pair
#define MOD 1000000007
#define fo(i,a,b) for(i=a;i<b;i++)
#define foe(i,a,b) for(i=a;i<=b;i++)
#define boost ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
int main()
{
	boost;
	ll a, b, i;
	cin >> a >> b;
	ll g = __gcd(a, b);
	ll ans = 0;
	for(i = 2; i <= sqrt(g); i++){
		if(g % i == 0)
		ans++;
		while(g % i == 0)
		g /= i;
	}
	if(g > 1)
	ans++;
	cout << ans + 1;
}


Measured memory_bytes: 256
# import sys
# input = sys.stdin.readline
# import re
import collections
import bisect
import math
import fractions
import collections
import itertools
from functools import reduce

def main():
    n = int(input())
    h = list(input_list())
    count = 0
    while True:
        if list(set(h)) == [0]:
            break
        flag = False
        count += 1
        for i, v in enumerate(h):
            if v != 0:
                flag = True
                h[i] -= 1
            else:
                if flag:
                    break
    print(count)

def minus(numbers):
    for i, n in enumerate(numbers):
        if n == 0:
            break
        numbers[i] -= 1
    return numbers


def input_list():
    return list(map(int, input().split()))


def input_list_str():
    return list(map(str, input().split()))


if __name__ == '__main__':
    main()



Measured memory_bytes: 77492
#pragma region
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <iomanip>
#include <cstdint>
#include <cstdlib>

using namespace std;
typedef long long ll;
//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))
#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))
#define rrep(i, s) for (int(i) = (s) - 1; (i) >= 0; --(i))
#define all(x) x.begin(),x.end()
#pragma endregion


int main()
{
	int x; cin >> x;
	int res = (x / 500)*1000;
	x %= 500;
	res += (x / 5) * 5;
	cout << res << endl;
}

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

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

   cout << floor((t + 0.5) / a) * b << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define REPR(i,n) for(ll i = n;i >= 0;--i)
#define FOR(i,m,n) for(ll i = m, i##_len=(n);i <i##_len; ++i)
#define all(x) (x).begin(),(x).end()
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; }
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const int INF = 1e9;
const ll LLINF = 1e16;

ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}


int main(void)
{
    int h,w;
    cin >> h >> w;
    vector<vector<bool>> field(h,vector<bool>(w,0));

    REP(i,h){
        string line;
        cin >> line;
        REP(j,w){
            if(line[j] == '#'){
                field[i][j] = true;
            }
        }
    }
    vector<vector<int>> score(h,vector<int>(w,0));
    REP(i,h){
        int left = 0;
        bool flag = true;
        vector<pair<int,int>> region;
        REP(j,w){
            if(!field[i][j] && flag){
                left = j;
            }
            else if(field[i][j] && !flag){
                region.push_back(pair<int,int>(left,j-1));
            }
            else if(j == w - 1 && !flag){
                region.push_back(pair<int,int>(left,j));
            }
            flag = field[i][j];
        }

        REP(j,region.size()){
            for(int k = region[j].first; k <= region[j].second;k++){
                score[i][k] += region[j].second - region[j].first ;
            } 
        }
    }
    REP(i,w){
        int top = 0;
        bool flag = true;
        vector<pair<int,int>> region;
        REP(j,h){
            if(!field[j][i] && flag){
                top = j;
            }
            else if(field[j][i] && !flag){
                region.push_back(pair<int,int>(top,j-1));
            }
            else if(j == h - 1 && !flag){
                region.push_back(pair<int,int>(top,j));
            }
            flag = field[j][i];
        }
        REP(j,region.size()){
            for(int k = region[j].first; k <= region[j].second;k++){
                score[k][i] += region[j].second - region[j].first ;
            } 
        }
    }

    int max = 0;
    REP(i,h){
        REP(j,w){
            if(score[i][j] + 1 > max && !field[i][j]){
                max = score[i][j] + 1;
            }
        }
    }

    cout << max << endl;


    return 0;
}

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


int A[1000];

int main(){
	int n,ans=0;
	cin >> n;
	for(int i=0;i<n;i++){
		cin >> A[i];
	}
	
	aa:;
	int cnt=0;
	for(int i=0;i<n;i++){
		if(A[i]%2==0) cnt++;
	}
	if(cnt==n){
		ans++;
		for(int i=0;i<n;i++){
			A[i]/=2;
		}
		goto aa;
	}
	
	cout << ans << endl;
	return 0;
}

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

class Myon
{
    public Myon() { }
    public static int Main()
    {
        new Myon().calc();
        return 0;
    }


    void calc()
    {
        Scanner cin = new Scanner();
        while (true)
        {
            int N = cin.nextInt();
            
            char[][] c = new char[10][];
            for (int i = 1; i < 9; i++)
            {
                c[i] = new char[3];
            }
            c[9] = new char[4];
            c[7] = new char[4];
            for (int i = 0; i < 8; i++)
            {
                for (int j = 0; j < 3; j++)
                {
                    int add = 0;
                    if (i > 5) add++;
                    c[i + 2][j] = (char)('a' + (i * 3 + j + add));
                }
            }
            c[1] = new char[5];
            c[7][3] = 's';
            c[9][3] = 'z';
            c[1][0] = '.';
            c[1][1] = ',';
            c[1][2] = '!';
            c[1][3] = '?';
            c[1][4] = ' ';

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

                int pre = 0;
                int count = 0;
                string st = cin.next();
                foreach (var item in st)
                {
                    if (item == '0')
                    {
                        if (count == 0) continue;
                        count--;
                        Console.Write(c[pre][count % c[pre].Length]);
                        pre = count = 0;
                    }
                    else
                    {
                        pre = (int)(item - '0');
                        count++;
                    }
                }
                Console.WriteLine();
            }
            break;
        }

    }
}




class Scanner
{
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner()
    {
        s = new string[0];
        i = 0;
    }

    public string next()
    {
        if (i < s.Length) return s[i++];
        do
        {
            s = Console.ReadLine().Split(cs, StringSplitOptions.RemoveEmptyEntries);
        } while ((s.Length == 1 && s[0] == "") || s.Length == 0);
        i = 0;
        return s[i++];
    }

    public int nextInt()
    {
        return int.Parse(next());
    }

    public long nextLong()
    {
        return long.Parse(next());
    }

    public double nextDouble()
    {
        return double.Parse(next());
    }

}

Measured memory_bytes: 5584
N, Y = map(int, input().split())
for x in range(N+1):
  for y in range(N-x+1):
    z = N -x -y
    if 10000*x + 5000*y + 1000*z == Y:
      print(x, y, z)
      exit()
print("-1 -1 -1")

Measured memory_bytes: 3060
#include<bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std ;

int main(){
	int n,a,b;
	cin>>n>>a>>b;
	if(n*a>=b)
		cout<<b<<" ";
	else 
		cout<<n*a; 
	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const ll MOD=pow(10,9)+7;
const ll INF=(1LL<<62);
const int dx[4]={0,1,0,-1};
const int dy[4]={1,0,-1,0};
const int ddx[8]={1,0,-1,-1,-1,0,1,1};
const int ddy[8]={1,1,1,0,-1,-1,-1,0};
void init(){
}
int main(){
    string s,ans;cin>>s;
    ll w;cin>>w;
    for (int i = 0; i < s.size(); i+=w)
    {
        ans.push_back(s[i]);
    }
    
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string.h>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <math.h>
#include <algorithm>
#include <numeric>

using namespace std;

// マクロ&定数 ============================================================
typedef unsigned int uint;
typedef long long ll;
//typedef pair<int, int> P;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<double> vdouble;
typedef vector<bool> vbool;

typedef vector<vector<int>> vvint;
typedef vector<vector<ll>> vvll;
typedef vector<vector<double>> vvdouble;
typedef vector<vector<bool>> vvbool;

const int INF = 1e9 + 1;
const ll LLINF = 1e17 + 1;
const int DX[9] = { 0,0,1,-1, 1, 1, -1, -1, 0 }; // 4;４近傍
const int DY[9] = { 1,-1,0,0, 1, -1, 1, -1, 0 }; // 8:８近傍 9:(0,0)を含む
const ll MOD = 1e9 + 7; //10^9 + 7
const double PI = 3.14159265358979323846264338327950288;
//========================================================================


int main() {

	//==================================
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(30);
	//==================================

	ll S;
	cin >> S;
	
	ll tmp = ll(1e9);

	if (S == tmp * tmp) {
		cout << "0 0 " << tmp << " " << "1 " << 0 << " " << tmp ;
	}
	else {
		cout << "0 0 " << tmp << " " << "1 " << tmp - S % tmp << " " << S / tmp + 1;
	}



}


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

//const long double PIL = 3.141592653589793238462643383279502884L;
//const double PI = 3.14159265358979323846;

#define sz(a) (int)((a).size())
#define all(c) (c).begin(), (c).end()
#define debug(v) {for (auto z : v) {cerr << z << ' ';} cerr << endl;}

using ll = long long;
using ii = pair<int,int>;
using vi = vector<int>;
using vll = vector<long long>;
using vii = vector<pair<int,int>>;

const ll MOD = 1e9 + 7;
const ll INV = -1e18;
const int N = 2e5 + 5;

ll a[N], dp[N][3];

int main() {
	//~ ios::sync_with_stdio(0);
	//~ cin.tie(0);
	int n; scanf("%d", &n);
	for (int i = 0; i < n; i++) scanf("%lld", &a[i]);

	dp[0][0] = a[0];
	dp[0][1] = INV;
	dp[0][2] = INV;
	dp[1][0] = INV;
	dp[1][1] = a[1];
	dp[1][2] = INV;
	for (int i = 2; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			if (dp[i-2][j] == INV) dp[i][j] = INV;
			else dp[i][j] = dp[i-2][j] + a[i];
		}
		if (i == 2) dp[i][2] = a[i];
		else {
			for (int j = 1; j < 3; j++) {
				if (dp[i-3][j-1] != INV)
					dp[i][j] = max(dp[i][j], dp[i-3][j-1] + a[i]);
			}
		}
	}

	ll ans = 0;
	if (n % 2 == 0) {
		ans = max(dp[n-1][1], dp[n-2][0]);
	}
	else {
		ans = max(dp[n-1][2], dp[n-2][1]);
		ans = max(ans, dp[n-3][0]);
	}
	printf("%lld\n", ans);
}


Measured memory_bytes: 10028
#include <bits/stdc++.h>
using namespace std;
int dis[100005],vis[100005],n;
queue<int>q;
int main()
{
	cin>>n;
	for(int i=1;i<n;i++)dis[i]=i,vis[i]=1,q.push(i);
	dis[0]=n,vis[0]=1,q.push(0);
	while(!q.empty())
	{
		int x=q.front();
		q.pop();
		int v=x*10%n;
		if(dis[v]>dis[x])
		{
			dis[v]=dis[x];
			if(!vis[v])vis[v]=1,q.push(v);
		}
		v=(x+1)%n;
		if(dis[v]>dis[x]+1)
		{
			dis[v]=dis[x]+1;
			if(!vis[v])vis[v]=1,q.push(v);
		}
		vis[x]=0;
	}
	cout<<dis[0]<<endl;
	return 0;
}

Measured memory_bytes: 1408
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <string>
#include <cmath>
#include <iostream>
#include <stack>
#include <queue>

#define ll long long int
#define all(x) x.begin(), x.end()
#define MOD 998244353

using namespace std;


void solve()
{
    ll n, k;
    cin >> n >> k;

    vector<int> a(n + 1);
    set<int> S;
    vector<int> pos;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    int i = 1;
    ll count = 0;
    while (true)
    {
        if (S.find(i) != S.end())
        {
            break;
        }
        S.insert(i);
        pos.push_back(i);
        i = a[i];
        count++;
        if (count == k)
        {
            cout << i << endl;
            return;
        }
    }

    vector<int> ans;
    int j;
    for (j = 0; j < pos.size(); j++)
    {
        if (pos[j] == i)
        {
            break;
        }
    }

    for (; j < pos.size(); j++)
    {
        ans.push_back(pos[j]);
    }

    cout << ans[(k - count) % ans.size()] << endl;

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

    int T = 1;
    // cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}



Measured memory_bytes: 12184
import java.util.*;

class Main {
        public static void main(String args[]) {
                try (Scanner sc = new Scanner(System.in)) {
                        int W = sc.nextInt(), H = sc.nextInt(), N = sc.nextInt();
                        int Hmax = H, Hmin = 0, Wmax = W, Wmin = 0;
                        for (int i = 0; i < N; i++) {
                                int x = sc.nextInt(), y = sc.nextInt(), a = sc.nextInt();
                                if (a == 1) {
                                        Wmin = Math.max(x, Wmin);
                                } else if(a == 2) {
                                        Wmax = Math.min(x, Wmax);
                                } else if(a == 3) {
                                        Hmin = Math.max(y, Hmin);
                                } else {
                                        Hmax = Math.min(y, Hmax);
                                }
                        }
                        System.out.println(Math.max(0, (Hmax - Hmin)) * Math.max(0, (Wmax - Wmin)));
                }
        }
}

Measured memory_bytes: 10320
#include<bits/stdc++.h>
#define rep(i, n) for (long long i = 0; i < (int)(n); i++)
#define put(i) cout<<fixed<<i<<endl
using namespace std;
using ll = long long;

int main(){
    ll n, m; cin >> n >> m;
    ll ans = 0;
    vector<ll> x(m), l(m-1);
    rep(i,m) cin >> x[i];

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

    for(long long i = 0; i < m-1; i++){
        l[i] = x[i+1] - x[i];
    }

    sort(l.begin(), l.end(), greater<ll>());

    for(long long i = n-1; i < m; i++) ans += l[i];

    put(ans);
}

Measured memory_bytes: 1792
from collections import Counter,defaultdict,deque
import sys
import bisect
import math
import itertools
import string
import queue
import copy
# import numpy as np
# import scipy
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7

def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])
def sortx(x,n,k):
    if k == 0:x.sort(key=lambda y:y[1,n])
    else:x.sort(reversed=True, key=lambda y:y[1,n])

def graphm():
    n,m=inpm()
    g=[[] for _ in range(n)]
    for _ in range(m):
        a,b,w=inpm()
        a-=1
        b-=1
        g[a].append((w,b))
        g[b].append((w,a))
    return n,m,g

def prim(n,g):
    edgelist = []
    used = [False for _ in range(n)]
    for edge in g[0]:
        heappush( edgelist, edge)
    used[0] = True
    res = 0 

    while len(edgelist)>0:
        minedge = heappop(edgelist)
        if used[minedge[1]]:
            continue
        v = minedge[1]
        used[v] = True
        for edge in g[v]:
            if not used[edge[1]]:
                heappush( edgelist, edge)
        res += minedge[0]
    return res

def main():
    n=inp()
    xy=[]
    for index in range(n):
        x,y = inpm()
        xy.append((x,y,index))
        
    g=[[] for _ in range(n)]
    xy.sort()
    for i in range(n-1):
        j = i+1
        w = min(abs(xy[i][0]-xy[j][0]),abs(xy[i][1]-xy[j][1]))
        a = xy[i][2]
        b = xy[j][2]
        g[a].append((w,b))
        g[b].append((w,a))
    xy.sort(key=lambda y:y[1])
    for i in range(n-1):
        j = i+1
        w = min(abs(xy[i][0]-xy[j][0]),abs(xy[i][1]-xy[j][1]))
        a = xy[i][2]
        b = xy[j][2]
        g[a].append((w,b))
        g[b].append((w,a))
    print( prim(n,g) )

if __name__ == "__main__":
    main()

Measured memory_bytes: 112984
// Author: Vamsi Krishna Reddy Satti
// With love for Competitive Programming!
 
// #pragma GCC optimize ("Ofast,unroll-loops,-ffloat-store")
// #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")

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

string to_string(const string& s) { return '"' + s + '"'; }
void debug_out() { cout << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cout << " " << to_string(H);
    debug_out(T...);
}
#ifdef LOCAL
    #define debug(...) cout << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
    #define debug(...) 3
#endif
 
#define cin_exception cin.exceptions(cin.failbit);
#define cout_precision cout.setf(ios::fixed); cout.precision(15);
#define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
using ld = long double; using vi = vector<int>;
using ll = int_fast64_t; using ull = uint_fast64_t;
using vl = vector<ll>; using vul = vector<ull>;

// -----------------------------------------------------------------------------

const int N = 2e3 + 5;
int cn[N];

void solve() {
    int n, x, y;
    cin >> n >> x >> y;
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            int d = j - i;
            d = min(d, abs(i - x) + 1 + abs(y - j));
            d = min(d, abs(i - y) + 1 + abs(x - j));
            ++cn[d];
        }
    }
    for (int i = 1; i < n; ++i) {
        cout << cn[i] << '\n';
    }
}

// -----------------------------------------------------------------------------

int main() {
    fast_io;
#ifdef LOCAL
    cin_exception;
#endif
    int t = 1;
    // cin >> t;
    // preprocess();
    for (int i = 1; i <= t; ++i) {
        solve();
    }
}


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

const string YES = "Yes";
const string NO = "No";

void solve(std::vector<std::vector<long long>> c) {
    vector<ll> a(3);
    vector<ll> b(3);
    rep(i, 3) { b[i] = c[0][i] - a[0]; }
    rep(i, 3) { a[i] = c[i][0] - b[0]; }
    rep(i, 3) {
        rep(j, 3) {
            if (c[i][j] != a[i] + b[j]) {
                cout << NO << endl;
                return;
            }
        }
    }
    cout << YES << endl;
}

int main() {
    std::vector<std::vector<long long>> c(3, std::vector<long long>(3));
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            scanf("%lld", &c[i][j]);
        }
    }
    solve(std::move(c));
    return 0;
}


Measured memory_bytes: 3684
#include <iostream>
#include <string>
#include <algorithm>
#include <utility>
#include <iomanip>
#include <functional>
#include <queue>
#include <stack>
#include <map>
#include <vector>
#include <cmath>
#define ll long long
#define INF 10000000000000000
#define MOD 998244353
using namespace std;


int main(){
    string s;
    cin >> s ;
    int ans=0;
    for(int i=0; i<4; i++){
        if(s[i]=='+'){
            ans++;
        }else{
            ans--;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <algorithm>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(x) (x).begin(), (x).end()
#define PB(x) push_back(x)
#define MP(x,y) make_pair(x,y)
using namespace std;
typedef long long ll;

int h[100000];

int main() {

    int n,m;
    cin >> n >> m;
    vector<int> p(m);
    vector<int> y(m);
    rep(i,m)    cin >> p.at(i) >> y.at(i);


    vector<tuple<int,int,int>> ans;
    vector<tuple<int,int,int>> x;
    rep(i,m)    x.PB(make_tuple(y[i],p[i],i));
    sort(all(x));

    rep(i,m) {
        h[get<1>(x[i])]++;
        ans.PB(make_tuple(get<2>(x[i]),get<1>(x[i]),h[get<1>(x[i])]));
    }
    sort(all(ans));


    rep(i,m) {
        printf("%06d%06d\n",get<1>(ans[i]),get<2>(ans[i]));
    }
  
 return 0;
}

Measured memory_bytes: 5108
function warshall(){
   for(var k=0;k<n;k++){
      for(var i=0;i<n;i++){
         for(var j=0;j<n;j++){
            C[i][j]=Math.min(C[i][j], C[i][k]+C[k][j]);
         }
      }
   }
}
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var Arr=(input.trim()).split("\n");
while(true){
   var n=10;
   var m=Arr.shift()-0;
   if(m==0)break;
   var C=[];
   for(var i=0;i<n;i++){
      C[i]=[];
      for(var j=0;j<n;j++){
         C[i][j]=(i===j)?0:Infinity;
      }
   }
   var max=0;
   for(var i=0;i<m;i++){
      var A=(Arr.shift()).split(" ").map(Number);
      max=Math.max(max,A[0],A[1]);
      C[A[0]][A[1]]=A[2];
      C[A[1]][A[0]]=A[2];
   }
   warshall();
   var min=["",Infinity];
   for(var i=max;i>=0;i--){
      var arr=C[i].slice(0,max+1);
      var sum=arr.reduce(function(a,b){return a+b;});
      min[1]=Math.min(min[1],sum);
      if(min[1]==sum)min=[i,sum];
   }
   console.log(min.join(" "));
}

Measured memory_bytes: 8584
#include<bits/stdc++.h>
#define int long long
#define for0(i, n) for(int i = 0; i < (n); i++)
#define for1(i, n) for(int i = 1; i <= (n);i++)
#define mp make_pair
#define all(x) x.begin(),x.end()
#define puts(x) cout << x << "\n"
#define endwith return
constexpr int mod = 1000000007;
using namespace std;
int input() { int t; cin >> t; return t; }
int d, c[30], l[30];
signed main() {
	cin >> d;
	for1(i, 26)cin >> c[i];
	for1(i, d) {
		int p = 0, k = -mod;
		for1(j, 26)if (k < c[j] * (i - l[j])) {
			k = c[j] * (i - l[j]);
			p = j;
		}
		puts(p);
		l[p] = i;
	}
}

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

using namespace std;

const int maxn = 1e5 + 9;
long long a, b, q, s[maxn], t[maxn];

int lower_bound(long long *arr, int size, long long x) {
	int start = 0, end = size;
	while (end > start) {
		int mid = (start + end) / 2;
		if (arr[mid] >= x) {
			end = mid;
		} else {
			start = mid + 1;
		}
	}
	return end;
}

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

	cin >> a >> b >> q;
	for (int i = 0; i < a; i++) {
		cin >> s[i];
	}
	for (int i = 0; i < b; i++) {
		cin >> t[i];
	}
	for (int i = 0; i < q; i++) {
		long long num;
		cin >> num;
		int sp = lower_bound(s, a, num), tp = lower_bound(t, b, num);
		vector<long long> scan, tcan;
		for (int i = 0; i < 2; i++) {
			if (0 <= sp - i && sp - i < a) {
				scan.push_back(sp - i);
			}
			if (0 <= sp + i && sp + i < a) {
				scan.push_back(sp + i);
			}
			if (0 <= tp - i && tp - i < b) {
				tcan.push_back(tp - i);
			}
			if (0 <= tp + i && tp + i < b) {
				tcan.push_back(tp + i);
			}
		}
		long long ans = 1e18;
		for (auto sc : scan) {
			for (auto tc : tcan) {
				//cerr << sc << ' ' << tc << '\n';
				long long ss = s[sc], tt = t[tc];
				if (max(ss, tt) <= num) {
					ans = min(ans, num - min(ss, tt));
				} else if (num <= min(ss, tt)) {
					ans = min(ans * 1LL, max(ss * 1LL, tt * 1LL) - num * 1LL);
				} else {
					ans = min(ans, min(abs(ss * 1LL - num * 1LL), abs(tt * 1LL - num * 1LL)) * 2LL + max(abs(ss * 1LL - num * 1LL), abs(tt * 1LL - num * 1LL)));
				}
			}
		}
		cout << ans << '\n';
	}

	return 0;
}


Measured memory_bytes: 2944