akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#define ll long long
#define ln printf("\n")
#define out(a) printf("%d",a)
const int N=1e5+50;
using namespace std;
int n;
char s[N],last;
map<string,int>cnt;
int read()
{
	int s=0,t=1; char c;
	while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();}
	while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();}
	return s*t;
}
ll readl()
{
	ll s=0,t=1; char c;
	while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();}
	while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();}
	return s*t;
}
int main()
{
	n=read();
	for (int i=1;i<=n;i++){
	  scanf("%s",s);
	  if (i==1) {
	    cnt[s]++; last=s[strlen(s)-1];
		continue;
	  }
	  if (cnt[s]) {
	  	puts("No");
	  	return 0;
	  }
	  if (s[0]!=last) {
	  	puts("No"); //cout<<last;
	  	return 0;
	  }
	  cnt[s]++; last=s[strlen(s)-1];
	}
	puts("Yes");
	return 0;
}

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

int main(){
    int n, a, b;
    int c[6]={};
    for (int i=0; i<6; i++) {
        cin >> c[i];
    }
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> a >> b;
        if (a==c[0]) {
            if (b==c[1]) {
                cout << c[2] << endl;
            } else if (b==c[2]) {
                cout << c[4] << endl;
            } else if (b==c[3]) {
                cout << c[1] << endl;
            } else if (b==c[4]) {
                cout << c[3] << endl;
            }
        } else if (a==c[1]) {
            if (b==c[0]) {
                cout << c[3] << endl;
            } else if (b==c[2]) {
                cout << c[0] << endl;
            } else if (b==c[3]) {
                cout << c[5] << endl;
            } else if (b==c[5]) {
                cout << c[2] << endl;
            }
        } else if (a==c[2]) {
            if (b==c[0]) {
                cout << c[1] << endl;
            } else if (b==c[1]) {
                cout << c[5] << endl;
            } else if (b==c[4]) {
                cout << c[0] << endl;
            } else if (b==c[5]) {
                cout << c[4] << endl;
            }
        } else if (a==c[3]) {
            if (b==c[0]) {
                cout << c[4] << endl;
            } else if (b==c[1]) {
                cout << c[0] << endl;
            } else if (b==c[4]) {
                cout << c[5] << endl;
            } else if (b==c[5]) {
                cout << c[1] << endl;
            }
        } else if (a==c[4]) {
            if (b==c[0]) {
                cout << c[2] << endl;
            } else if (b==c[2]) {
                cout << c[5] << endl;
            } else if (b==c[3]) {
                cout << c[0] << endl;
            } else if (b==c[5]) {
                cout << c[3] << endl;
            }
        } else if (a==c[5]) {
            if (b==c[1]) {
                cout << c[3] << endl;
            } else if (b==c[2]) {
                cout << c[1] << endl;
            } else if (b==c[3]) {
                cout << c[4] << endl;
            } else if (b==c[4]) {
                cout << c[2] << endl;
            }
        } 
    }
    return 0;
}


Measured memory_bytes: 3032
#pragma GCC optimize("O3", "unroll-loops")
//#pragma GCC target("avx2")
#pragma optimize("fast-math")

#include <bits/stdc++.h>
#include <stdio.h>

using namespace std;
#define endl '\n'
#define ull unsigned long long
#define si short int
#define ll long long
#define ld long double
#define pb push_back
#define pii pair<int, int>
#define pdd pair<double, double>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define piii pair<pair<int, int>, int>
#define all(vec) (vec).begin(), (vec).end()
#define piiii pair<pair<int, int>, pair<int, int>>


ll gcd(ll a, ll b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

ll gcdex(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll xx, yy;
    ll gc = gcdex(b, a % b, yy, xx);
    x = xx;
    y = yy - (a / b) * xx;
    return gc;
}

ll dp[300][300];

void solve() {
    int n;
    cin>>n;
    while(n!=0){
        if(n%10==7) {
            cout<<"Yes";
            return;
        }
        n/=10;
    }
    cout<<"No";
}

void testcases(int n) {
    n = 1 - n;
    if (!n) cin >> n;
    for (int i = 0; i < n; i++) {
        solve();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    //freopen("C:\\Users\\Maximus\\CLionProjects\\Codeforces\\BestTeam\\output.txt", "r", stdin);
    //f=fopen("C:\\Users\\Maximus\\CLionProjects\\Codeforces\\BestTeam\\output.txt", "w");
    //freopen("C:\\Users\\Maximus\\CLionProjects\\Codeforces\\BestTeam\\output.txt", "w", stdout);

    unsigned int beg_time = clock();
    testcases(0);
    // 0 - no t, 1 - with t

    unsigned int end_time = clock();
    //cout << endl << endl << end_time - beg_time;
    return 0;
}

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

using namespace std;

#ifdef SG
	#include <debug.h>
#else
	#define show(...)
	#define debug(...)
	#define deepen(...)
	#define timer(...)
#endif

#define ARG4(_1,_2,_3,_4,...) _4

#define forn3(i,l,r) for (int i = int(l); i < int(r); ++i)
#define forn2(i,n) forn3 (i, 0, n)
#define forn(...) ARG4(__VA_ARGS__, forn3, forn2) (__VA_ARGS__)

#define ford3(i,l,r) for (int i = int(r) - 1; i >= int(l); --i)
#define ford2(i,n) ford3 (i, 0, n)
#define ford(...) ARG4(__VA_ARGS__, ford3, ford2) (__VA_ARGS__)

#define ve vector
#define pa pair
#define tu tuple
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define fs first
#define sc second
#define all(a) (a).begin(), (a).end()
#define sz(a) ((int)(a).size())

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef unsigned char uc;
typedef pa<int, int> pii;
typedef pa<int, ll> pil;
typedef pa<ll, int> pli;
typedef pa<ll, ll> pll;
typedef ve<int> vi;

const ld pi = 3.1415926535897932384626433832795l;

template<typename T> inline auto sqr (T x) -> decltype(x * x) {return x * x;}
template<typename T1, typename T2> inline bool umx (T1& a, T2 b) {if (a < b) {a = b; return 1;} return 0;}
template<typename T1, typename T2> inline bool umn (T1& a, T2 b) {if (b < a) {a = b; return 1;} return 0;}

const int N = 100100;
vi a[N];
int n;

int d[N];

int calc(int v, int pr) {
	d[v] = 0;
	vi ord;
	forn(i, sz(a[v])) {
		int to = a[v][i];
		if (to == pr)
			continue;
		ord.pb(calc(to, v));
	}
	sort(all(ord));
	ford(i, sz(ord)) {
		umx(d[v], ord[i] + sz(ord) - i);
	}
	return d[v];
}

int main () {
	cout.setf(ios::showpoint | ios::fixed);
	cout.precision(20);
#ifdef SG
	freopen((problemname + ".in").c_str(), "r", stdin);
//	freopen((problemname + ".out").c_str(), "w", stdout);
#endif
	cin >> n;
	forn(i, n - 1) {
		int u;
		scanf("%d", &u);
		u--;
		a[u].pb(i + 1);
	}	
	cout << calc(0, -1) << endl;
	return 0;
}


Measured memory_bytes: 18560
import sys

def f(x):
  cnt = 0
  while x%2 == 0:
    x /= 2
    cnt += 1
  return cnt

def gcd(x, y):
  if y:
    return gcd(y, x%y)
  else:
    return x

def lcm(x, y):
  return (x * y) // gcd(x, y)


n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [i//2 for i in a]

t = f(a[0])
for i in range(n):
  if f(a[i]) != t:
    print(0)
    sys.exit()
  a[i] >>= t
m >>= t

l = 1
for i in range(n):
  l = lcm(l, a[i])
  if l > m:
    print(0)
    sys.exit()

m //= l
ans = (m+1) // 2
print(ans)

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

#define REP(i,num) for(int i=0;i<(num);++i)

using namespace std;
using ll = long long;

template<typename T=int>
T in(){T x; cin >> x; return (x);}

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

  ll N=in<ll>();
  array<ll,5> a;
  for(auto& x:a) x=in<ll>();
  
  ll need=1+((N-1)/(*min_element(a.begin(),a.end())));
  
  cout << 4+need << endl;
  
  return 0;
}

Measured memory_bytes: 256
//* aman*/
#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define pii         pair<int,int>
#define vi          vector<int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define dl          double
#define hell        1000000007
#define endl        '\n'
#define rep(i,a,b) for(int i=a;i<b;i++)
#define lb lower_bound
#define ub upper_bound
#define bs          binary_search
#define ios         ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
int main(){
	ios;
	int n;cin>>n;
	bitset<5000000> bit;
	bit.set(0);
	vector<int> v(n);
	int sum=0;
	for(int i=0;i<n;i++){
		cin>>v[i];
		bit=bit|(bit<<v[i]);
		sum+=v[i];
	}
	set<int> si;
	for(int i=0;i<=sum;i++){
		if(bit[i]){
			si.insert(i);
		}
	}
	cout<<*si.lower_bound(sum/2+sum%2)<<endl;
}

Measured memory_bytes: 96512
def partition(A, p, r):
  x = A[r]
  i = p -1

  for j in range(p, len(A)):
    if A[j] <= x:
      i += 1
      A[i], A[j] = A[j], A[i]
  return i

n = int(input())
A = list(map(int, input().split()))
cnt = partition(A, 0, len(A)-1)

ans = []
for i, j in enumerate(A):
  if i == cnt:
    ans.append("["+str(j)+"]")
  else:
    ans.append(str(j))

print (" ".join(ans))


Measured memory_bytes: 16584
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <numeric>

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define pb(a) push_back(a)

typedef long long ll;
using namespace std;

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 int dy[] = { 0, 0, 1, -1 };
//const int dx[] = { 1, -1, 0, 0 };
const int dx[8] = { 1, 0, -1, 0, 1, -1, -1, 1 };
const int dy[8] = { 0, 1, 0, -1, 1, 1, -1, -1 };
ll gcd(ll a, ll b);
ll lcm(ll x, ll y);

//vector<ll> a;

int main()
{
	ll r;
	cin >> r;
	
	cout << 3*r*r << endl;
	
	return 0;
}


Measured memory_bytes: 256
n,m,q = map(int,input().split())
li = [i for i in range(1,m+1)]
lin = []

for _ in range(q):
    a,b,c,d = map(int,input().split())
    lin.append((a,b,c,d))

from itertools import combinations_with_replacement
li = list(combinations_with_replacement(li, n))
ma = 0

for i in li:
    point = 0
    for j in lin:
        a,b,c,d = j
        a -= 1
        b -= 1
        if i[b]-i[a] == c:
            point += d
    ma = max(point,ma)

print(ma)

Measured memory_bytes: 21484
gets

b = gets.split.map(&:to_i)

def func(seq)
  return [] if seq.empty?
  return nil if seq.each.with_index(1).any? {|item, index| item > index}
  seq.each.with_index(1).reverse_each.lazy.select do |item, index|
    item == index
  end.map(&:first).map do |i|
    func(seq.dup.tap{|s| s.delete_at(i-1) })&.push(i)
  end.reject(&:nil?).first
end

ans = func(b)

if ans
  ans.each do |i|
    puts i
  end
else
  puts(-1)
end


Measured memory_bytes: 6396
#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#include<cmath>
#define pb push_back
#define ll long long
#define ull unsigned long long
#define deb(x) cerr<<#x<<" "<<x<<"\n"
#define debi cerr<<"hey sparky\n"
#define x first
#define y second
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define newline cout<<"\n"
#define yes cout<<"Yes"<<"\n"
#define no cout<<"No"<<"\n"
#define INF (ll)1e14+5
#define nax (ll)2e5+3
#define eps (double)1e-9
#define all(x) x.begin(),x.end()
#define MAX_N 3005
using namespace std;
using namespace __gnu_pbds; 
typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> pdbs;
// look for  all edge cases
//search for a pattern


//dp[N][heads]
long double dp[MAX_N][MAX_N];

int main(){
	fast;
	int n ;
	cin >> n;
	
	vector<long double> v(n+1);
	for(int i= 1 ;i<=n;i++){
		cin >> v[i];
	}
	
	memset(dp,0.0,sizeof(dp));
	dp[0][0] = 1.00;
	vector<long double> tail_prob(n+1,1);
	for(int i = 1; i<=n ;i++){
		tail_prob[i] = tail_prob[i-1]*(1.00 - v[i]);
	}
	for(int i =1 ; i<=n;i++){
		for(int j = 0 ; j<n;j++){
			//deb(dp[i-1][j+1]);
			dp[i][j+1] = (j == 0 ?tail_prob[i-1]*v[i]:dp[i-1][j]*v[i]);  
			dp[i][j+1] += dp[i-1][j+1]*(1.00 - v[i]) ;
			//deb(i);
			//deb(j+1);
			//deb(dp[i][j+1]);
		}
	}
	long double ans = 0;
	for(int i= n/2+1;i<=n;i++){
		ans += dp[n][i];
	}	
		
	cout<<fixed<<setprecision(9)<<ans;	
		
	return 0;
}

	


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

using namespace std;

int main()
{
    int n,val;
    cin>>val;
    n=val;
    int sum=0;
    while(n!=0){
        sum+=(n%10);
        n=n/10;
    }
   if(val%sum==0)
        cout<<"Yes";
    else cout<<"No";
  return 0;
}


Measured memory_bytes: 3608
a=list(input())
gamen=[]
for i in range (len(a)):
  if a[i]=='0':
    gamen.append('0')
  if a[i]=='1':
    gamen.append('1')
  if a[i]=='B':
    if gamen==[]:
      continue
    else:
      del gamen[-1]
mpjiretsu = ''.join(gamen)

print(mpjiretsu)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1000000000000000000

using namespace std;

int main(void){
  ll d, t, s;
  cin >> d >> t >> s;
  
  
  if (d <= t*s){
    cout << "Yes" << endl;
  }
  else
    cout << "No" << endl;
    
  

  return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
#include <new>

using namespace std;

int main(){
    int H,A;
    cin >> H >> A;
    int f = H/A;
    int s = H%A;
    if(s == 0){
        cout << f << endl;
    }else{
        cout << f + 1 << endl;
    }
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <stdio.h>

using namespace std;

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

	if (a < b && b < c){
		cout << "Yes" << endl;
	}
	else{
		cout << "No" << endl;
	}

	return 0;
}

Measured memory_bytes: 1156
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* constant */

#define MAX_STR (4000)

/* global variables */

static char str0[MAX_STR + 1], str1[MAX_STR + 1];
static int seqs[2][MAX_STR + 1];

/* main */

int main(int argc, char **argv) {
  int cur, i, j, l, max_len, n0, n1, nxt;

  for (;;) {
    if (gets(str0) == NULL) break;
    gets(str1);

    n0 = strlen(str0);
    n1 = strlen(str1);

    memset(seqs, 0, sizeof(seqs));

    cur = 0;
    nxt = 1;

    max_len = 0;

    for (i = 0; i < n0; i++) {
      seqs[nxt][0] = 0;

      for (j = 0; j < n1; j++) {
        if (str0[i] == str1[j]) {
          l = seqs[nxt][j + 1] = seqs[cur][j] + 1;
          if (max_len < l) max_len = l;
        }
        else
          seqs[nxt][j + 1] = 0;
      }

      nxt = cur;
      cur = 1 - cur;
    }

    printf("%d\n", max_len);
  }

  return 0;
}

Measured memory_bytes: 556
#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<tuple>
#include<algorithm>
#include<cmath>
#include<limits>
#include<set>
#include<deque>
#include<queue>
#include<stack>
using namespace std;
#define int long long int
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define dup(x,y) (((x)+(y)-1)/(y))
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
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<int, int>P;
const int MOD = 1e9 + 7;
//const int MOD = 998244353;
const int INF = 1e18;
const long double PI = (acos(-1));


signed main() {
	string S, T;
	cin >> S >> T;
	int ans = 0;
	rep(i, S.size()) {
		if (S[i] != T[i])ans++;
	}
	cout << ans;
}

Measured memory_bytes: 3844
N, A, B, K = map(int, input().split())
MOD = 998244353

g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
for i in range(2, 3*10**5+1):
    g1.append((g1[-1] * i) % MOD)
    inverse.append((-inverse[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * inverse[-1]) % MOD)

def comb(n, r, mod=MOD):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n-r] % mod

ans = 0
for i in range(N+1):
  if (K - i*A) % B == 0:
    j = (K - i*A) // B
    ans += comb(N, i) * comb(N, j) % MOD
    ans %= MOD

print(ans)

Measured memory_bytes: 38980
def main():
    h,w = map(int,input().split())
    c = []
    for i in range(0,10):
        cc = list(map(int,input().split()))
        c.append(cc)
    a = []
    for i in range(0,h):
        aa = list(map(int,input().split()))
        a.append(aa)
    # ワーシャルフロイド（最短経路だす）
    for i in range(10):
        for j in range(10):
            for k in range(10):
                c[j][k] = min(c[j][k], c[j][i] + c[i][k])
    cnt = 0
    for i in range(h):
        for j in range(w):
            if a[i][j] == -1:
                continue
            else:
                cnt += c[a[i][j]][1]
    print(cnt)


if __name__=='__main__':
    main()


Measured memory_bytes: 3444
#define  _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <algorithm>
#include <utility>
#include <functional>
#include <cstring>
#include <queue>
#include <stack>
#include <math.h>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <math.h>
#include <iostream>
#include <random>
#include<map>
#include <iomanip>
#include <time.h>
#include <stdlib.h>
#include <list>
#include <typeinfo>
#include <list>
#include <set>
#include <cassert>
#include<fstream>
#include <unordered_map>
#include <cstdlib>
#include <complex>
using namespace std;
using ll = long long;
#define Ma_PI 3.141592653589793
#define eps 0.00000001
#define LONG_INF 3000000000000000000
#define rep(i,n) for(long long i = 0;i < n;++i)    
#define seg_size 524288

int k;
int choose(int n,int k,int nine){
    if(n<k)return 0;
    int a=1;
    for(int i=0;i<nine;i++){
        a*=9;
    }
    if(k==0)return a;
    if(k==1)return n*a;
    else return (n-1)*n/2*a;
}
void cn(string &n,int cnt){
    //cout<<cnt<<endl;
    rep(i,n.size()){
        if(cnt==0)n[i]='9';
        else if(n[i]!='0'){
            cnt--;
            if(cnt==0)n[i]-=1;
        }
        //cout<<i<<"::"<<n<<endl;
    }
        
    if(n[0]=='0'){
        n.erase(0,1);
    }
}
int main(){
    string n;
    
    cin>>n;
    cin>>k;
    int cnt=0;
    rep(i,n.size()){
        if(n[i]!='0')cnt++;
    }
    //cout<<cnt<<" ";
    if(cnt<k)cn(n,cnt);
   // cout<<n<<endl;

    cnt=0;
    rep(i,n.size()){
        if(n[i]!='0')cnt++;
    }
    if(cnt<k)cn(n,cnt-1);
    //cout<<"n="<<n<<endl;
    if(k>n.size()){
        cout<<0<<endl;
        return 0;
    }
    int keta=0;
    int t=n.size();
    rep(i,t){
        if(i==0||k>i) continue;
        
        keta+=choose(i-1,k-1,k);
    
    }
    
    //cout<<n[0]<<" "<<n[1]<<endl;
    //cout<< "t="<<t<<endl;
    vector<int>fr(k),m(k);
   
    for(int i=0;i<k;i++){
        for(int j=0;j<n.size();j++){
            if(n[j]!='0'){
                fr[i]=n[j]-'0';
                m[i]=j+1;
                i++;
                if (i == k)break;
            }
        }  
    }
    int ans=keta;
    // cout<<keta<<endl;
    //cout<<m[0]<<" "<<m[1]<<endl;
    // cout<<fr[0]<<" "<<fr[1]<<endl;

    rep(i,k){
        ans+=(fr[i]-1)*choose(t-m[i],k-i-1,k-i-1);
    }
    //cout<<ans<<endl;
    rep(i,k-1){
        ans+=choose(t-m[i+1],k-1-i,k-1-i);
    }
    ans++;
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define ll long long
#define ull unsigned long long
#define ld long double
#define vl vector<long long>
#define vvl vector<vector<long long>>
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define rrep(i, x) for (ll i = ((ll)(x)-1); i >= 0; i--)
#define pll pair<long long,long long>
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define vvc vector<vector<char>>
#define vc vector<char>
#define vvb vector<vector<bool>>
#define vb vector<bool>
#define maxe(x) *max_element(all(x))
#define mine(x) *min_element(all(x))
#define Size(x) ((int)(x).size())
#define umap unordered_map
const long long INF = 1LL << 60;
const long double pi = 3.1415926535897932;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

    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;
    }

//lis,modpow,uf,modncr,soinsubunkai,yakusurekkyo,gyakugen
//mint,dijkstra

    signed main(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        ll n;
        cin>>n;
        vl A(n);
        rep(i,n)cin>>A[i];
        sort(all(A));
        cout<<A[n-1]<<' ';
        ll it1=lower_bound(all(A),A[n-1]/2)-A.begin();
        ll it2=it1-1;
        chmax(it2,0LL);
        if(abs(A[it1]*2-A[n-1])<abs(A[it2]*2-A[n-1])){
            cout<<A[it1]<<endl;
        }else{
            cout<<A[it2]<<endl;
        }
    }

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

int main()
{
	int n;
	const int max_n = 1000;
	double a[max_n];
	while (cin >> n, n) {
		double s = 0.0;
		double sum = 0.0;
		for (int i = 0; i < n; i++) {
			cin >> a[i];
			sum += a[i];
		}
		double m = sum / n;
		for (int i = 0; i < n; i++) {
			s += pow(a[i] - m, 2);
		}
		s /= n;
		s = sqrt(s);
		printf("%.6f\n", s);
	}
    return 0;
}

Measured memory_bytes: 1252
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())

def make_divisors(n):
    i = 1
    lowest = 10**18
    while i*i <= n:
        if n % i == 0:
            lower_divisor = i
            upper_divisor = n//i
        i += 1
    return len(str(upper_divisor))
    
print(make_divisors(N))

Measured memory_bytes: 62700
N = int(input())
A = list(map(int, input().split()))

if len(set(A)) == 1 and A[0] == 0:
  print(0)
else:
  ans = [0]*N
  ans[N//2:] = A[N//2:]
  for i in range(N//2):
    j = N//2 - i
    check = 0
    for n in range(N//j):
      check += ans[j*(n+1)-1]
    ans[j-1] = 1 if (check%2 != A[j-1]) else 0
  ans = [i for i,x in enumerate(ans) if x==1]
  print(len(ans))
  print(' '.join([str(n+1) for n in ans]))

Measured memory_bytes: 18868
import math as m1

def ncr(n1,n2):
  f= m1.factorial
  ans = f(n1)//(f(n1-n2)*f(n2))
  return ans

n,m = map(int,input().split())

res =0
if n<2:
  res+=0
if m<2:
  res+=0
if n>=2:
  res+=ncr(n,2)
if m>=2:
  res+=ncr(m,2)
  
print(res)
  

Measured memory_bytes: 38384
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
using ll = long long;

int main() {
	string S;
	cin >> S;
	// 00000 -> 01010
	// 00011 -> 01010
	// 000000 -> 010101
	// 0000000 -> 0101010
	// 00000000 -> 01010101
	int total_matched = 0;
	for (int x=0; x<2; ++x) {
		char left, right;
		if (x==0) {
			left = '0'; right = '1';
		} else {
			left = '1'; right = '0';
		}
		int left_matched, right_matched;
		left_matched = 0;
		right_matched = 0;
		for (int i=0; i<S.size(); ++i) {
			if (i%2 == 0) {
				left_matched += (S[i] == left) ? 1 : 0;
			} else {
				right_matched+= (S[i] == right) ? 1 : 0;
			}
		}
		total_matched = max(total_matched, left_matched + right_matched);
	}	
	cout << S.size() - total_matched << endl;
	return 0;
}



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

#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define ACC(c) (accumulate(ALL(c), 0LL))
#define PRINT(x) cout << (x) << "\n"

using namespace std;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;

inline int in(int& a) {return scanf("%d", &a);}
auto pint_compare = [](pint x, pint y) -> bool{return (x.first < y.first);};
const int MOD = 1000000007;

signed main(){
    string S;
    string w[3] = {"Sunny", "Cloudy", "Rainy"};
    cin >> S;
    if(S == w[0]) PRINT(w[1]);
    else if(S == w[1]) PRINT(w[2]);
    else if(S == w[2]) PRINT(w[0]);
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main() {
	long long int n,max=0,a[200000],b[200000],number;
	scanf("%lld", &n);
	
	for (int i = 1; i <= n; i++) {
		scanf("%lld%lld", &a[i],&b[i]);
		if (max < a[i]) { number = b[i];max=a[i]; }
	}
	printf("%lld", max+number);
}


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

using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long ll;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef pair<int, int> P;

const int MOD = 1000000007;
const int INF_32 = 1LL << 30;
const int64_t INF_64 = 1LL << 60;

int main()
{
    int n;
    cin >> n;
    map<ll, ll> mp;
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        ll a;
        cin >> a;
        ans += mp[i - a];
        mp[i + a]++;
    }

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 26264
import Data.Int
import Data.List
import Data.Vector.Unboxed ((!))
import qualified Data.Vector.Unboxed as V

main = do
  [n,x] <- map read.words <$> getLine
  set <- sortBy (flip compare).map read.words <$> getLine
  print $ solve n x set

solve :: Int64 -> Int64 -> [Int64] -> Int64
solve n x = (*% fact n).(!fromIntegral x).go 1
  where
  go _ [] = V.fromListN 100001 [0..100000]
  go i (s:set) = V.generate 100001 f
    where
    f x' = let x = fromIntegral x' in (a!fromIntegral x *% (n-i) + a!fromIntegral (x`mod`s)) *% inv (n-i+1)
    a = go (i+1) set

infixl 7 *%
infixl 5 +%
infixl 5 -%
a *% b = a * b `mod` 1000000007
a -% b = (a - b) `mod` 1000000007
a +% b = (a + b) `mod` 1000000007
fact = foldl (*%) 1.enumFromTo 2
inv x = u where (u,_,_) = euc x 1000000007
euc = go 1 0 0 1
  where
  go u v u' v' x 0 = (u,v,x)
  go u v u' v' x y = go u' v' (u - q * u') (v - q * v') y r
    where (q,r) = quotRem x y



Measured memory_bytes: 167036
#include<stdio.h>
int main(){
    int x[20000],i=0;

    while(1){
        scanf("%d",&x[i]);
        if(x[i]==0){
            break;
        }
        i++;
    }

    i=0;
    while(x[i]!=0){
        printf("Case %d: %d\n",i+1,x[i]);
        i++;
    }

    return 0;
}

Measured memory_bytes: 644
#include <iostream>
#include <vector>
#include <limits.h>
#include <algorithm>
#include <string>
#include <math.h>
#include <limits.h>
#include <queue>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <cassert>
#include <random>
#include <functional>
#include <stack>
#include <iomanip>
#include <cassert>
//#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
const long long MOD = 1e9+7;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ld, ll> pdl;
typedef pair<ld, ld> pdd;
//typedef boost::multiprecision::cpp_int bigint;

//最大公約数
//O(log max(a,b))
template<class T>
T GCD(T a, T b) {
	if (b == 0)return a;
	return GCD(b, (T)(a % b));
}

ll N, X;

int main() {
	cin >> N >> X;
	ll G = GCD(N, X);
	ll NN = N / G;
	cout << 3 * (NN - 1) * G << endl;
	return 0;
}

Measured memory_bytes: 256
Scanf.scanf "%d %d" (fun n x ->
    let d = 2 * n - 1 in
    let prt a b = for i = a to b do Printf.printf "%d\n" i done in
    if x = 1 || x = d then print_endline "No" else (
        print_endline "Yes";
        if x = n then prt 1 d else
        if x < n then (
            prt 1 (x - 2);
            prt (x + 1) n;
            prt (x - 1) x; 
            prt (n + 1) d;
        ) else (
            prt 1 (n - 1);
            prt x (x + 1);
            prt n (x - 1);
            prt (x + 2) d;
        )
    )
)

Measured memory_bytes: 3840
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string.h>
#include <stack>
#include <map>
#include <unordered_map>
#include <climits>
using namespace std;
const int INF = 1e9;
#define ll long long
#define int ll
#define fast                      \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
#define testcase \
    int t;       \
    cin >> t;    \
    while (t--)
#define pb push_back
#define endl "\n"
#define deb1(x) cout << #x << ": " << x << endl
#define deb2(x, y) cout << #x << ": " << x << " | " << #y << ": " << y << endl
#define deb3(x, y, z) cout << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl
#define deb4(x, y, z, w) cout << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << " | " << #w << ": " << w << endl
#define deb5(a, b, c, d, e) cout << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(a) int((a).size())
#define pii pair<int, int>
#define fi first
#define se second
#define ld long double
#define vii vector<int>
#define all(v) v.begin(), v.end()
#define prec(n) fixed << setprecision(n)
const int MOD = (int)1e9 + 7;
const int MOD2 = 1007681537;
const ll LINF = (ll)1e18;
const ld PI = acos((ld)-1);
const ld EPS = 1e-12;
inline ll gcd(ll a, ll b)
{
    ll r;
    while (b)
    {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}
inline ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
inline ll fpow(ll n, ll k, int p = MOD)
{
    ll r = 1;
    for (; k; k >>= 1)
    {
        if (k & 1)
            r = r * n % p;
        n = n * n % p;
    }
    return r;
}
template <class T>
inline int chkmin(T &a, const T &val) { return val < a ? a = val, 1 : 0; }
template <class T>
inline int chkmax(T &a, const T &val) { return a < val ? a = val, 1 : 0; }
inline void addmod(int &a, int val, int p = MOD)
{
    if ((a = (a + val)) >= p)
        a -= p;
}
inline void submod(int &a, int val, int p = MOD)
{
    if ((a = (a - val)) < 0)
        a += p;
}
inline int mult(int a, int b, int p = MOD) { return (ll)a * b % p; }
inline int inv(int a, int p = MOD) { return fpow(a, p - 2, p); }
inline void get_arr(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cin >> arr[i];
}
inline void print_arr(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int32_t main()
{
    int n;
    cin>>n;
    int arr[n];
    get_arr(arr,n);
    int dp[n];
    dp[0]=0;
    dp[1]=abs(arr[1]-arr[0]);
    int a,b;
    for(int i=2;i<n;i++)
    {   
        a=abs(arr[i]-arr[i-1])+dp[i-1];
        b=abs(arr[i]-arr[i-2])+dp[i-2];
        dp[i]=min(a,b);
    }
    // print_arr(dp,n);
    cout<<dp[n-1]<<endl;
}


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

int mygcd ( int a, int b, int &S ) {

    if ( b == 0 ) {
        return ( a );
    }
    S++;

    return ( mygcd ( b, a % b, S ) );

}
int main()
{
    int A, B;

    while ( cin >> A >> B, A || B ) {

        int S = 0;
        int div;

        if ( A < B ) {
            swap ( A, B );
        }

        div = mygcd(A, B, S);
        cout << div << " " << S << endl;
    }

    return ( 0 );
}



Measured memory_bytes: 3008
#include<bits/stdc++.h>
using namespace std;
char ans[1010][1010];
int n, m, a, b;
#define vput(x, y) ans[x][y] = '^', ans[(x)+1][y] = 'v'
#define hput(x, y) ans[x][y] = '<', ans[x][(y)+1] = '>'
int main() {
	cin.tie(0)->sync_with_stdio(0);
	memset(ans, '.', sizeof ans);
	cin >> n >> m >> a >> b;
	if(n&m&1) {
		for(int i = 0; i+1 < n-3 + 2*(m==1) && b; i += 2) vput(i, m-1), b--;
		for(int i = 0; i+1 < m-3 + 2*(n==1) && a; i += 2) hput(n-1, i), a--;
		
		for(int i = 0; i + 2 < n; i+=2) {
			for(int j = 0; j + 2 < m; j+=2) {
				if(i >= n-3 && j >= m-3) continue;
				if(a>=max(1, b)) {
					a-=2;
					hput(i, j);
					hput(i+1, j);
				} else if(b>=max(1, a)) {
					b-=2;
					vput(i, j);
					vput(i, j+1);
				}
			}
		}
		if((n==1||m==1)&&(a+b)) return cout << "NO", 0;
		if(a==2&&b==2) {
			hput(n-3, m-3);
			vput(n-3, m-1);
			vput(n-2, m-3);
			hput(n-1, m-2);
		} else if(a<2&&b<4) {
			if(a) hput(n-1, m-3);
			for(int x = m-3; b--; x++) vput(n-3, x);
		} else if(b<2&&a<4) {
			if(b) vput(n-3, m-1);
			for(int x = n-3; a--; x++) hput(x, m-3);
		} else
			return cout << "NO", 0;
		cout << "YES\n";
		for(int i = 0; i < n; i++, cout << '\n')
			for(int j = 0; j < m; j++)
				cout << ans[i][j];
		return 0;
	}
	if(m&1) for(int i = 0; i+1 < n && b; i += 2) vput(i, m-1), b--;
	if(n&1) for(int i = 0; i+1 < m && a; i += 2) hput(n-1, i), a--;
	for(int i = 0; i + 1 < n-(n&1); i+=2) {
		for(int j = 0; j + 1 < m-(m&1); j+=2) {
			if(a) {
				hput(i, j);
				if(a>1) hput(i+1, j);
				a-=min(a, 2);
			} else if(b) {
				vput(i, j);
				if(b>1) vput(i, j+1);
				b-=min(b, 2);
			}
		}
	}
	if(a+b) return cout << "NO", 0;
	cout << "YES\n";
	for(int i = 0; i < n; i++, cout << '\n')
		for(int j = 0; j < m; j++)
			cout << ans[i][j];
}



Measured memory_bytes: 2176
#B
import itertools
n = int(input())
w = list(map(int,input().split()))

w = [0] + w
acc = list(itertools.accumulate(w))

b = []
for i in range(1,len(acc)):
    left = acc[i]
    right = acc[-1] - left
    b.append(abs(left-right))
    
print(min(b))

Measured memory_bytes: 3064
#include<iostream>
using namespace std;
int main(void){
  int N;
  cin>>N;
  if(N==1){
    cout<<"Hello World"<<endl;
    return 0;
  }else{
    int A,B;
    cin>>A>>B;
    cout<<A+B<<endl;
	return 0;
  }
}

Measured memory_bytes: 256
def main():
    N, M, r = map(int, input().split())
    edge = [list(map(int, input().split())) for _ in range(M)]

    dist = [float('inf')] * N
    dist[r] = 0

    for i in range(N):
        flag = False
        for a, b, c in edge:
            if dist[b] > dist[a] + c:
                dist[b] = dist[a] + c
                flag = True
        if flag is False:
            break
        else:
            if i == N - 1:
                print('NEGATIVE CYCLE')
                exit()

    for i in range(N):
        if dist[i] == float('inf'):
            print('INF')
        else:
            print(dist[i])


if __name__ == '__main__':
    main()



Measured memory_bytes: 5980
#include <bits/stdc++.h> 
#include <time.h>
#define F(i,a,b) for(long long i=a;i<=(b);++i)
#define dF(i,a,b) for(long long i=a;i>=(b);--i) 
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3f
#define pb push_back
#define maxnkp make_pair
#define fi first
#define se second
#define eps 1e-10
#define PI acos(-1.0)
using namespace std;
typedef long long ll;
const int mods = 1e9+7;
const int maxn = 2e5+10; 
const int N = 1e5+10;
const int E = 1e6+10;  
int n,k,p,h,w;
ll a[maxn];
vector<ll> pos,neg,zero;

ll qpow(ll n,ll b){
	ll res =1;
	while(b){
		if(b&1) res = n*res%mods;
		n = n*n%mods;
		b>>=1;
	}
	return res;
}

int main(){
	cin>>n>>k;
	F(i,1,n){
		cin>>a[i];
		if(a[i]<0) neg.pb(a[i]);
		else if(a[i]==0) zero.pb(a[i]);
		else pos.pb(a[i]);
	}
	sort(neg.begin(),neg.end());
	sort(pos.begin(),pos.end());
	ll sum = 1;
	if(n-k<zero.size()){
		printf("0\n");
		return 0;
	}
	if(n-k==zero.size()){
		int ap = 0;
		F(i,1,n){
			if(a[i]!=0){
				if(a[i]<0) ap++;
				sum*=a[i];
				sum%=mods;
			}
		}
		if(ap%2==1&&zero.size()){
			cout<<"0"<<endl;
			return 0;
		}
		if(sum<0) sum+=mods;
		cout<<sum<<endl;
		return 0;
	}
	if(!pos.size()){
		if(k%2==1){
			if(zero.size()){
				printf("0\n");
				return 0;
			}
			else{
				for(int i=neg.size()-1;i>=neg.size()-k;i--){
					sum*=neg[i];
					sum%=mods;
				}
				if(sum<0) sum+=mods;
				cout<<sum<<endl;
				return 0;
			}
		}
	}
	int pp=pos.size()-1,nn=0,cnt=0;
	int ap=0;
	while(cnt<k){
		if(pp<0){
			sum*=neg[nn++];
			sum%=mods;
			ap++;
			cnt++;
			continue;
		}
		if(nn>=neg.size()){
			sum*=pos[pp--];
			sum%=mods;
			cnt++;
			continue;
		}
		if(pos[pp]<abs(neg[nn])){
			sum *= neg[nn++];
			sum%=mods;
			ap++;
		}
		else{
			sum*=pos[pp--];
			sum%=mods;
		}
		cnt++;
	}
	if(ap%2==0){
		if(sum<0) sum+=mods;
		cout<<sum<<endl;
	}
	else{
		if(pp<0&&nn>=neg.size()){
			if(zero.size()){
				cout<<"0"<<endl;
				return 0;
			}
			else{
				if(sum<0) sum+=mods;
				cout<<sum<<endl;
			}
		}
		if(pp==pos.size()-1||nn==neg.size()){
			sum*=pos[pp];
			sum%=mods;
			sum*=qpow(neg[nn-1],mods-2);
			sum%=mods;
			if(sum<0) sum+=mods;
			cout<<sum<<endl;
			return 0;
		}
		if(pp<0){
			sum*=neg[nn];
			sum%=mods;
			sum*=qpow(pos[0],mods-2);
			sum%=mods;
			if(sum<0) sum+=mods;
			cout<<sum<<endl;
			return 0;
		}
		ll x = abs(neg[nn])*abs(neg[nn-1]);
		ll y = pos[pp]*pos[pp+1];
		if(x>y){
			sum*=neg[nn];
			sum%=mods;
			sum*=qpow(pos[pp+1],mods-2);
			sum%=mods;
			if(sum<0) sum+=mods;
			cout<<sum<<endl;
			return 0;
		}
		else{
			sum*=pos[pp];
			sum%=mods;
			sum*=qpow(neg[nn-1],mods-2);
			sum%=mods;
			if(sum<0) sum+=mods;
			cout<<sum<<endl;
			return 0;
		}
	}
}
/*
6 4
-2 -7 -8 -9 8 2
*/


Measured memory_bytes: 7076
#include<bits/stdc++.h>
#define rep(i,n) for(int (i) = 0;(i) < (n);(i)++)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;
using namespace std;
using ll = long long;

vector<vector<int>> dp(100005, vector<int>(3, 0));
// dp[i][j] := i日終了時点での最大の幸福度(最後の選択がj)

int main(void) {
  int n;
  cin >> n;
  int abc[n + 1][3];
  rep (i, n) cin >> abc[i + 1][0] >> abc[i + 1][1] >> abc[i + 1][2];

  for (int i = 1; i <= n; i++) {
    rep (j, 3) {
      rep (k, 3) {
        if (j == k) continue;
        dp[i][j] = max(dp[i][j], dp[i - 1][k] + abc[i][j]);
      }
    }
  }
  
  cout << max({dp[n][0], dp[n][2], dp[n][1]}) << endl;
  return 0;
}

Measured memory_bytes: 6912
#define _USE_MATH_DEFINES
#define INF 0x1f1f1f1f
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
 
using namespace std;
 
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P > PP;
 
int tx[] = {0,1,0,-1};
int ty[] = {-1,0,1,0};
 
static const double EPS = 1e-8;

int block[12][12];
int idx2heart[12];
int dp[145][145];

class MinimumSteinerTree {
public:
  int solver(int total_chocolates,int H,int W){
    if(total_chocolates <= 1) return 0;

    for(int k = 0; k < H * W; k++){
      for(int i = 0; i < H * W; i++){
        for(int j = 0; j < H * W; j++){
          dp[i][j] = min(dp[i][j],dp[i][k] + dp[k][j]);
        }
      }
    }

    int steiner_tree[1<<total_chocolates][H * W];
    memset(steiner_tree,0x1f,sizeof(steiner_tree));
    for(int i = 0; i < total_chocolates; i++){
      for(int to = 0; to < H * W; to++){
        steiner_tree[(1 << i)][to] = dp[idx2heart[i]][to];
      }
    }

    for(int S = 1; S < (1<<total_chocolates); S++){
      for(int from = 0; from < H * W; from++){
        
        int tmp = INF;
        for(int E = 0; E < S; E++){
          for(int to = 0; to < H * W; to++){
            if((E | S) != S) continue;
            tmp 
              = min(tmp,
                    dp[from][to]
                    + steiner_tree[E][to]
                    + steiner_tree[S - E][to]);
          }
        }
        steiner_tree[S][from] = min(steiner_tree[S][from],tmp);
      }
    }

    int res = INF;
    for(int S = 0; S < (1 << total_chocolates); S++){
      for(int to = 0; to < H * W; to++){
        res = min(res,
                  steiner_tree[S][to]
                  + steiner_tree[((1<<total_chocolates) - 1) - S][to]);
      }
    }
    return res;
  }
};

int main(){
  int H,W;
  while(~scanf("%d %d",&H,&W)){
    if(H == 0 && W == 0) break;

    int idx = 0;
    for(int y = 0; y < H; y++){
      for(int x = 0; x < W; x++){
        scanf("%d",&block[y][x]);
        if(block[y][x] == 1){
          idx2heart[idx] = y * W + x;
          idx++;
        }
      }
    }
    int total_chocolates = idx;

    memset(dp,0x1f,sizeof(dp));
    for(int from = 0; from < H * W; from++){
      dp[from][from] = 0;
      for(int i = 0; i < 4; i++){
        int dx = from % W + tx[i];
        int dy = from / W + ty[i];
        if(dx < 0 || dx >= W || dy < 0 || dy >= H) continue;
        int to = dy * W + dx;
        dp[from][to] = dp[to][from] = 1;
      }
    }

    MinimumSteinerTree mst;
    printf("%d\n",H * W - (mst.solver(total_chocolates,H,W) + 1));
  }
}

Measured memory_bytes: 1308
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    String str1 = scan.nextLine();
    String str2 = scan.next();
    String str3 = scan.next();    
    
    int num1 = Integer.parseInt(str1);
    int num2 = Integer.parseInt(str2);
    int num3 = Integer.parseInt(str3);    

    int sum = 0;
    String str4 = "";
    
    for(int i=1;i<=1000;i++) {
      sum = num1 * i;
      if(num2 <= sum && num3 >= sum) {
          str4 = "OK";
          break;
      }
      str4 = "NG";
    }
    String str = String.valueOf(num1);
    str = str4;
    System.out.println(str);
    scan.close();    
  }
}

Measured memory_bytes: 35792
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
#include<list>
#include<set>
using namespace std;
int mod = 1e9+7;

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

  if( r < 1200 ) cout << "ABC" << endl;
  else if( r < 2800 ) cout << "ARC" << endl;
  else cout << "AGC" << endl;

  return 0;
}




//


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=1e9+7;
const int INF=1e9;
const ll LINF=(ll)1e18;

int main(){
    int n,r;
    cin>>n>>r;
    if(n>=10)cout<<r<<endl;
    else cout<<r+100*(10-n)<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

inline bool isPrime(int a){
  if(a<=1)return false;
  for(int i=2;i*i<=a;i++){
    if(a % i == 0)return false;
  }
  return true;
}

int main(){
  vector<int> table(10001,0);
  for(int i=1;i<=10000;i++){
    if(i>=2 && isPrime(i) && isPrime(i-2)){
      table[i] = i;
    }else{
      table[i] = table[i-1];
    }
  }

  int n;
  while(cin >> n){
    if(n==0)break;
    cout << table[n]-2 << " " << table[n] << endl;
  }  
}

Measured memory_bytes: 1232
h, w = map(int, input().split())

from math import ceil
h_odd_num = ceil(h / 2)
h_even_num = h // 2

w_odd_num = ceil(w / 2)
w_even_num = w // 2

if h > 1 and w > 1:
  print(h_odd_num * w_odd_num + h_even_num * w_even_num)
else:
  print(1)

Measured memory_bytes: 38480
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

N, M = map(int, input().split())

if M % 2 == 0 :
    vec = [[] for _ in range(N)]
    for _ in range(M) :
        A, B = map(int, input().split())
        vec[A-1].append(B-1)
        vec[B-1].append(A-1)

    visited = [False] * N
    CD = [[] for _ in range(N)]

    def dfs(cur, pre) :
        for nex in vec[cur] :
            if nex == pre :
                continue
            
            if not visited[nex] :
                visited[nex] = True
                dfs(nex, cur)
            elif not cur in CD[nex] :
                CD[cur].append(nex)
        
        if pre != -1 :
            if len(CD[cur]) % 2 == 0 :
                CD[pre].append(cur)
            else :
                CD[cur].append(pre)

    visited[0] = True            
    dfs(0, -1)

    for i in range(N) :
        for j in CD[i] :
            print(i + 1, j + 1)
else :
    print(-1)

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

using namespace std;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl;
#define OK(ok) cout << (ok ? "Yes" : "No") << endl;
typedef long long ll;

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail) {
  cin >> head; CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

const ll LINF = 1e18 + 1;
const int MOD = 1e9 + 7;
const int MAX_N = 1e5 + 1;

ll H, W;

ll solve()
{
  ll res = LINF;
  ll sq1, sq2, sq3;
  
  FOR (wi, 1, W) {
    sq1 = H * wi;
    REP(hi, 2) {
      if (hi == 0) {
	sq2 = H * ((W - wi) / 2);
      } else {
	sq2 = (H / 2) * (W - wi);
      }
      sq3 = H * W - sq1 - sq2;
      ll mx = max(sq1, max(sq2, sq3));
      ll mn = min(sq1, min(sq2, sq3));

      /*
	if (mx - mn < res) {
	debug(wi);
	debug(mx - mn);
	}
      */
      res = min(res, mx - mn);
    }
  }
  return res;
}

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

  cin >> H >> W;
  ll ans = LINF;
  ans = min(ans, solve());
  swap(H, W);
  ans = min(ans, solve());

  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 256
// Problem : C - こだわり者いろはちゃん / Iroha's Obsession
// Contest : AtCoder Beginner Contest 042
// URL : https://atcoder.jp/contests/abc042/tasks/arc058_a
// Memory Limit : 256.000000MB 
// Time Limit : 2000.000000milisec 
// Powered by CP Editor (https://github.com/coder3101/cp-editor2)

//1-1-20
#include<bits/stdc++.h>

#define Pi acos(-1.0)
#define U unsigned
#define ll long long
#define uu first
#define vv second
#define endl "\n"
#define scu(n) scanf("%u",&n)
#define scl(n) scanf("%d",&n)
#define scll(n) scanf("%lld",&n)

//Vector Macros
#define pb push_back
#define eb emplace_back
#define ALL(v) v.begin(),v.end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end())
#define MIN(c) *min_element(ALL(c))
#define MAX(c) *max_element(ALL(c))
#define SUM(c) accumulate(ALL(c),0)

//Loop Macros
#define FOR(i,a,b) for(ll i=a;i<=b;i++)
#define rep(i,a,b)  for(int i=a;i<=b;i++)
#define For(i,n) for(int i=0;i<n;i++)

//Debug Macros
#define deb(a) cout << #a << " : " << a << " ";
#define debln(a) cout<< #a <<" : " << a << endl;
#define open  freopen("input.txt","r",stdin);
#define close freopen ("output.txt","w",stdout);

//Print Macros
#define print(v)  for(auto x : v) {  cout<<x<<" ";   }  cout<<endl;
#define PRINT(v)  for(auto x : v) { cout<<x.uu<<" "<<x.vv<<endl; }

/*
ll for_binarySearch(ll a,ll b,ll aa[],ll x){while(a<=b){ll mid=(a+b)/2;if(aa[mid]==x) return 1;else if(aa[mid] > x) b=mid-1;else a=mid+1;}return -1;}
ll for_gcd(ll a,ll b){if(a==0) return b;else return for_gcd(b%a,a);}
ll for_prime(ll x){for (ll i=2;i*i<=x;i++){if(x%i==0) return 0;}return 1;}
void for_swap(char *x,char *y){char temp;temp=*x;*x=*y;*y=temp;}
ll for_big_mod(ll b,ll p,ll m){if(p==0) return 1;else if(p%2==0){ll k=for_big_mod(b,p/2,m);return (k*k)%m;}else return ((b%m)*(for_big_mod(b,p-1,m)))%m;}
ll for_josephus(ll n,ll k){if(n==1) return 1;return (for_josephus(n-1,k)+k-1)%n+1;}
ll for_gcdExtended(ll a,ll b,ll *x,ll *y){if(a==0){*x=0;*y=1;return b;}ll x1,y1;ll gcd=for_gcdExtended(b%a,a,&x1,&y1);*x=y1-(b/a)*x1;*y=x1;return gcd;}
*/

#define fastio  ios::sync_with_stdio(false); cin.tie(nullptr);

using namespace std;

int dp[11];
int n,k,i;

bool valid(int n)
{
	while(n)
	{
		if(dp[n%10])
		   return false;
		n/=10;
	}
	
	return true;
}

int main()
{
	fastio
	
	cin>>n>>k;
	
	For(i,k){
		
		int x;
		cin>>x;
		dp[x]++;
	}
	
	i=n;
	
	while(i)
	{
		if(valid(i)){
			
			cout<<i<<endl;
			break;
		}
		i++;
	}
}

Measured memory_bytes: 256
if __name__ == "__main__":
    N = int(input())
    dp = [0] * 3

    for day in range(N):
        cur_activities = [int(x) for x in input().split()]

        new_dp = [0] * 3

        for i in range(3):
            for j in range(3):
                if i != j:
                    new_dp[j] = max(new_dp[j], dp[i] + cur_activities[j])

        dp = new_dp

    print(max(dp))





Measured memory_bytes: 3188
#東京海上日動　プログラミングコンテスト2020 b
a,v = map(int, input().split())
b,w = map(int, input().split())
t = int(input())
dis = abs(a-b)
move =  v-w
if dis <= move * t:
    print('YES')
else:
    print('NO')


Measured memory_bytes: 9168