akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
public class Main {
 public static void main (String[] args){

	 	Scanner sc = new Scanner(System.in);
	 	
	 	// 整数の入力
	 	int a = sc.nextInt();
	 	int b = sc.nextInt();
	 	int c = sc.nextInt();
	 	int d = sc.nextInt();

	 	Integer [] numbs = {a,b,c,d};
 	
	 	String strBl;
	 	if(Arrays.asList(numbs).contains(1)&&
	 			Arrays.asList(numbs).contains(9) &&
	 			Arrays.asList(numbs).contains(7)&&
	 			Arrays.asList(numbs).contains(4)) {
	 		strBl = "YES";
	 	} else{
	 		strBl = "NO";
	 	}
	 	// 出力
	 	
	 	System.out.println(strBl);

	 
	 
 }
	
}


Measured memory_bytes: 21716
#include<iostream>
using namespace std;
int main()
{
	int a,s,t=0;
	cin>>a;
	int n;
	n=a;
    while(a)
 	{
  		s=a%10;
  		a=a/10;
  		t+=s;
 	}
	if(n%t==0)
	cout<<"Yes"<<endl;
	else
	cout<<"No"<<endl;
} 

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define pb push_back
#define mod 1000000007
#define mk make_pair
int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin>>n;
    int a[n];int c[n];int b[n];
    for(int i=0;i<n;i++)
    {cin>>a[i]>>b[i]>>c[i];}
    int dp[n][6];
    dp[0][0]=b[0];dp[0][4]=a[0];
    dp[0][1]=c[0];dp[0][2]=a[0];
     dp[0][3]=c[0]; dp[0][5]=b[0];
    for(int i=1;i<n;i++)
    {
        dp[i][0]=max(dp[i-1][2],dp[i-1][4])+b[i];
        dp[i][1]=max(dp[i-1][2],dp[i-1][4])+c[i];
        dp[i][2]=max(dp[i-1][0],dp[i-1][5])+a[i];
        dp[i][3]=max(dp[i-1][0],dp[i-1][5])+c[i];
        dp[i][4]=max(dp[i-1][1],dp[i-1][3])+a[i];
        dp[i][5]=max(dp[i-1][3],dp[i-1][1])+b[i];
    }
    int ans=dp[n-1][0];
    for(int i=1;i<6;i++)
    ans=max(ans,dp[n-1][i]);
    cout<<ans;
    return 0;
}

Measured memory_bytes: 3840
#include<stdio.h>
int main()
{
	int A,B,C;
	scanf("%d %d %d",&A,&B,&C);
	if(A==5&&B==5&&C==7||A==5&&C==5&&B==7||B==5&&C==5&&A==7)
	{
		printf("YES\n");}
			 else printf("NO\n");
			 return 0;
}

Measured memory_bytes: 128
#include <iostream>

using namespace std;

int main() {
    int w, h, n;
    cin >> w >> h >> n;

    int x[100], y[100], a[100];
    for (int i = 0; i < n; i++)
        cin >> x[i] >> y[i] >> a[i];

    bool rect[100][100];
    for (int i = 0; i < w; i++) {
        for (int j = 0; j < h; j++)
            rect[i][j] = false;
    }

    for (int i = 0; i < n; i++) {
        switch (a[i]) {
            case 1:
                for (int k = 0; k < x[i]; k++) {
                    for (int l = 0; l < h; l++)
                        rect[k][l] = true;
                }
                break;
            case 2:
                for (int k = x[i]; k < w; k++) {
                    for (int l = 0; l < h; l++)
                        rect[k][l] = true;
                }
                break;
            case 3:
                for (int k = 0; k < w; k++) {
                    for (int l = 0; l < y[i]; l++)
                        rect[k][l] = true;
                }
                break;
            case 4:
                for (int k = 0; k < w; k++) {
                    for (int l = y[i]; l < h; l++)
                        rect[k][l] = true;
                }
                break;
        }
    }

    int area = 0;
    for (int i = 0; i < w; i++) {
        for (int j = 0; j < h; j++) {
            if (!rect[i][j])
                area++;
        }
    }

    cout << area << endl;

    return 0;

}

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, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp setprecision
#define pb(x) push_back(x)
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ld, ld> pdd;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = 1e8;
const ll INF = 1e16;
const string alpha = "abcdefghijklmnopqrstuvwxyz";

int main(){
    int N;
    cin >> N;
    int a[N][N];
    int i = 1;
    while(true){
        bool update = false;
        rep(j, N-1){
            rep2(k, j+1, N-1){
                if(j%(1<<(i-1)) == k%(1<<(i-1)) && j%(1<<i) != k%(1<<i)){
                    a[j][k] = i;
                    update = true;
                }
            }
        }
        if(!update) break;
        i++;
    }
    rep(i, N-1){
        rep2(j, i+1, N-1){
            cout << a[i][j] << ' ';
        }
        cout << endl;
    }
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<string> vs;
typedef vector<char> vc;
typedef queue<ll> ql;
typedef deque<ll> dql;
typedef priority_queue<ll/*, vl, greater<ll>*/> pql; //降順(/*昇順*/)
typedef set<ll> sl;
typedef pair<ll, ll> pl;
typedef vector<vl> vvl;
typedef vector<pl> vpl;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
#define rep2(i, k, n) for(ll i = ll(k); i <= ll(n); i++)
#define rep3(i, n, k) for(ll i = ll(n); i >= ll(k); i--)
#define all(v) (v).begin(), (v).end()
ll mod(ll a, ll b) {if(b == 0) return 0; return (a % b + b) % b;}
bool chmin(ll &a, ll b) {if(b < a) {a = b; return 1;} return 0;}
bool chmax(ll &a, ll b) {if(b > a) {a = b; return 1;} return 0;}
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;
const ll MAX = 1e9;
const char newl = '\n';

vl Prime;
void get_Prime (ll n) {
  vb prime(n+1, 1);
  prime[0] = 0;
  prime[1] = 0;
  
  rep2(i, 2, n) {
    if(!prime[i]) continue;
    
    Prime.push_back(i);
    for(ll j=2; i*j < n; j++) {
      prime[i*j] = 0;
    }
  }
}

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

  ll n;
  cin >> n;
  vl a(n);
  rep(i, n) cin >> a[i];
  
  ll g=a[0];
  rep2(i, 1, n-1) g = gcd(g, a[i]);
  if(g!=1) {cout << "not coprime" << newl; return 0;}
  
  ll M=0;
  rep(i, n) chmax(M, a[i]);

  vb prime(M+1, 1);
  prime[0] = 0;
  prime[1] = 0;
  
  vl HPF(M+1);
  rep(i, M+1) HPF[i] = i;
  
  rep2(i, 2, M) if(prime[i]) for(ll j=2; i*j <= M; j++) {prime[i*j] = 0; HPF[i*j] = i;}
  
  rep(i, n) {
    while(a[i]>1) {
      ll num = HPF[a[i]];
      if(!prime[num]) {cout << "setwise coprime" << newl; return 0;}
      prime[num] = 0;
      while(a[i]%num==0) a[i] /= num;
    }
  }
  
  cout << "pairwise coprime" << newl;
  return 0;
}

Measured memory_bytes: 18996
#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <algorithm>

using namespace std;

using ll = long long int;

int main() {

	ll X, Y, Z, K;
	vector<ll> A;
	vector<ll> B;
	vector<ll> C;

	cin >> X >> Y >> Z >> K;

	A.reserve(X);
	B.reserve(Y);
	C.reserve(Z);

	for (int i = 0; i < X; i++) cin >> A[i];
	for (int i = 0; i < Y; i++) cin >> B[i];
	for (int i = 0; i < Z; i++) cin >> C[i];

	std::sort(&A[0], &A[X], std::greater<ll>());
	std::sort(&B[0], &B[Y], std::greater<ll>());
	std::sort(&C[0], &C[Z], std::greater<ll>());

	std::vector<ll> ans;
	
	for (int i = 0; i < X; i++) {
		for (int j = 0; j < Y; j++) {
			for (int k = 0; k < Z; k++) {
				if (i * j * k > K) break;
				ans.push_back(A[i] + B[j] + C[k]);
			}
		}
	}
	
	std::sort(ans.begin(), ans.end(), std::greater<ll>());

	for (int i = 0; i < K; i++)
		cout << ans[i] << "\n";

	return 0;
}



Measured memory_bytes: 35176
#include<iostream>
#include<algorithm>
#include<math.h>
#include<map>
using namespace std;
int a[200010] , range[1000010];
map<int , int>mp;
int main()
{
	int n,ans=0;	cin>>n;
	for(int i=1;i<=n;i++)
		cin>>a[i];
	sort(a+1 , a+1+n);
	for(int i=1;i<=n;i++)
		range[a[i]]++;
	for(int i=1;i<=n;i++)
	{
		bool OK=true;
		for(int j=2;j<=sqrt(a[i])&&OK;j++)
		{
			if(a[i]%j==0)
			{
				if(range[j]!=0||range[a[i]/j]!=0)
					OK=false;
			}
		}
		if(OK&&range[a[i]]==1){
			ans++;
			//cout<<a[i]<<endl;
		}
	}
	if(range[1]==1){
		cout<<1<<endl;
		return 0;
	}
	else if(range[1]>1){
		cout<<"0"<<endl;
		return 0;
	}
	cout<<ans<<endl;
}

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

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

int cnt[100000];
int main(){
	int n,K,q;cin>>n>>K>>q;
	rep(i,q){
		int a;scanf("%d",&a);a--;
		cnt[a]++;
	}
	rep(i,n){
		int d=q-cnt[i];
		if(d>=K){
			puts("No");
		}
		else puts("Yes");
	}
}

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

long long N, Q;
string S;
long long l[100005];
long long r[100005];
long long AC[100005]; //idx以下にいくつACがあるか

int main(){
	cin >> N >> Q;
	cin >> S;
	for(long long i = 0; i < Q; i++){
		cin >> l[i] >> r[i];
		l[i]--; r[i]--;
	}

	for(long long i = 0; i < S.size() - 1; i++){
		if(S[i] == 'A' && S[i+1] == 'C'){
			AC[i+1] = AC[i] + 1;
		} else {
			AC[i+1] = AC[i];
		}
		//cout << "AC[" << i << "] = " << AC[i] << endl;
	}


	for(long long i = 0; i < Q; i++){
		//cout << "r " << r[i] << " l  " << l[i] << endl;
		cout << AC[r[i]] - AC[l[i]] << endl;
	}
}


Measured memory_bytes: 3456
#include <iostream>
using namespace std;
#pragma warning (disable: 4996)

int N, D[1 << 18];
int cnt[1 << 18];
long long mod = 998244353;

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> D[i];
		cnt[D[i]]++;
	}
	if (cnt[0] != 1 || D[1] != 0) {
		cout << "0" << endl;
		return 0;
	}

	long long ans = 1;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= cnt[i]; j++) { ans *= cnt[i - 1]; ans %= mod; }
	}
	cout << ans << endl;
	return 0;
}

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

int main()
{
    long N;
    long long sum=0;
    cin >> N;
    long long a[200001]={0};
    for(int i=0;i<N;i++){
        cin >> a[i];
        sum += a[i];
    }
    long long ans=10000000000;
    long long tmp=0;
    for(int k=0;k<N-1;k++){
            tmp+=a[k];
            ans=min(abs(sum-2*tmp),ans);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
using namespace std;
int main()
{
    ll n,i,j,k,c=0,min=10000000000;
    cin>>n;
    ll a[n];
    for(i=0;i<n;i++)
    {
        cin>>a[i];
        if(a[i]<=min){
            min=a[i];c++;}
    }
    cout<<c;
}


Measured memory_bytes: 5068
s = input()
t = input()
c = 0
ans = len(t)
for i in range(0,len(s)-len(t)+1):
  for j in range(len(t)):
    if s[i+j] != t[j]:
      c += 1
  ans = min(ans,c)
  c = 0
print(ans)

Measured memory_bytes: 9032
#include <math.h>
#include <ctype.h>
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, n) for (int i = a; i < n; i++)
#define REP(i, n) for(int i = 0; i < n; i++)
struct omt{omt(){ios::sync_with_stdio(false);cin.tie(0);}}star;

int main(){
    string r, g, b;
    cin >> r >> g >> b;
    
    r += g + b;
    int a = stoi(r);
    if(a % 4 == 0) cout << "YES" << endl;
    else cout << "NO" << endl;

    return 0;
}

Measured memory_bytes: 256
//Date:12-11-17

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<stdbool.h>
#include<float.h>
#include<math.h>
#include<ctype.h>
#include<limits.h>
#include<time.h>
#define ll long long
#define For(i,n)	for(i=0;i<n;i++)
#define rep(i ,a ,b)	for(i=(a);i<=(b);i++)
#define mset(a ,value)	memset(a ,value ,sizeof(a))
#define s(a)	scanf("%d" ,&a);
#define ls(a)	scanf("%ld" ,&a)
#define lls(a)	scanf("%lld" ,&a)
#define reg(i)	register int i
#define infinite INT_MAX
#define MAX 1001
int min(int a,int b){	return (a<b?a:b);	}
int max(int a,int b){	return (a>b?a:b);	}
const int mod = 1e9+7;
int n;
bool prime[1001];
ll power(ll a, ll b, ll mod){
	ll x = 1, y = a;
	while (b){
		if (b%2)	x = (x*y)%mod;
		y = (y*y)%mod;
		b /= 2;
	}
	return x%mod;
}	

void sieve(){
	ll i ,j;
	mset(prime ,1);
	prime[1] =false;
	for(i=2;i<=1000;i++){
		if(prime[i]==true){
			j=i*i;
			while(j<=1000){
				prime[j] = false;	j+=i;
			}
		}
	}
}

main(){
	ll i ,j ,k;
	sieve();
	s(n);
	ll ans=1LL;
	for(i=2;i<=n;i++){
		if(prime[i]){
			ll p = 0;
			k=i;
			while(k<=n){	p+=n/k;	k*=i;	}
			//printf("%d %d\n" ,i ,p);
			ans *= (p+1);
			ans%=mod;
		}
	}
	printf("%lld" ,ans);
	return 0;
}

Measured memory_bytes: 128
import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Random;

public class Main {

    public static void main(String[] args) throws Exception {
        try (BufferedInputStream in = new BufferedInputStream(System.in);
             PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out))) {

            _Scanner sc = new _Scanner(in);

            int k = sc.nextInt();
            String s = sc.next();

            if (s.length() <= k) {
                out.println(s);
            } else {
                out.println(s.substring(0, k) + "...");
            }

        }
    }



    
    
    private static void reverse(int[] vs) {
        for (int i = 0; i < vs.length / 2; i++) {
            swap(vs, i, vs.length - 1 - i);
        }
    }

    static class _Scanner {
        InputStream is;
        _Scanner(InputStream is) {
            this.is = is;
        }
        byte[] bb = new byte[1 << 15];
        int k, l;
        byte getc() {
            try {
                if (k >= l) {
                    k = 0;
                    l = is.read(bb);
                    if (l < 0) return -1;
                }
                return bb[k++];
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        byte skip() {
            byte b;
            while ((b = getc()) <= 32)
                ;
            return b;
        }

        int nextInt() {
            int n = 0;
            int sig = 1;
            for (byte b = skip(); b > 32; b = getc()) {
                if (b == '-') {
                    sig = -1;
                } else {
                    n = n * 10 + b - '0';
                }
            }
            return sig * n;
        }

        long nextLong() {
            long n = 0;
            long sig = 1;
            for (byte b = skip(); b > 32; b = getc()) {
                if (b == '-') {
                    sig = -1;
                } else {
                    n = n * 10 + b - '0';
                }
            }
            return sig * n;
        }

        public String next() {
            StringBuilder sb = new StringBuilder();
            for (int b = skip(); b > 32; b = getc()) {
                sb.append(((char) b));
            }
            return sb.toString();
        }
    }

    private static void shuffle(int[] ar) {
        Random rnd = new Random();
        for (int i = 0; i < ar.length; i++) {
            int j = i + rnd.nextInt(ar.length - i);
            swap(ar, i, j);
        }
    }

    private static void shuffle(Object[] ar) {
        Random rnd = new Random();
        for (int i = 0; i < ar.length; i++) {
            int j = i + rnd.nextInt(ar.length - i);
            swap(ar, i, j);
        }
    }

    private static void swap(int[] ar, int i, int j) {
        int t = ar[i];
        ar[i] = ar[j];
        ar[j] = t;
    }

    private static void swap(Object[] ar, int i, int j) {
        Object t = ar[i];
        ar[i] = ar[j];
        ar[j] = t;
    }


}


Measured memory_bytes: 36208
N,M,X = map(int,input().split())
A = [list(map(int,input().split())) for n in range(N)]
a = 10**9

for i in range(2**N):
  S = (M+1)*[0]
  for j in range(N):
    if (i>>j)&1:
      S = [S[k]+A[j][k] for k in range(M+1)]
  if all([X<=s for s in S[1:]]):
    a = min(a,S[0])

if a==10**9:
  print(-1)
else:
  print(a)

Measured memory_bytes: 9236
h, w = map(int, input().split())
board = ["#"*(w+2)]
for i in range(h):
    board += ["#" + input() + "#"]
board += ["#" * (w + 2)]

for i in range(1, h):
    for j in range(1, w):
        f = 0
        if board[i][j] == ".":
            continue
        for dy, dx in zip([0, -1, 1, 0], [-1, 0, 0, 1]):
            if board[i + dy][j + dx] == ".":
                f += 1
            if f == 4:
                print("No")
                exit()
print("Yes")

Measured memory_bytes: 3064
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
 
#include<bits/stdc++.h>
 
using namespace std;
#define ll long long
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define ull unsigned long long
#define rep(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define ff first
#define ss second
#define fast ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0); 
#define nl "\n"
#define sz(a) (int)(a).size() 
#define all(a) (a).begin(),(a).end()
#define fl(a,x) memset(a,x,sizeof(a));
#define pt(a,x) cout << get<x>(a) << " " ;  
#define mt make_tuple 
#define vec vector
 
#define int long long 
 
const int mod = (int) 1e9 + 7 ;
const int MOD = (int) 998244353 ;
const int INF = (int) 1e18 ;
 
typedef vector<int> vii;
typedef pair<int,int> pii;
typedef vector<pii> vpi;
typedef vector<vector<int> > vv;
 
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
 
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}


void solve(int test) {
	int n,m,k; cin >> n >> m >> k ;
	vii A(n),B(m);
	rep(i,0,n) cin >> A[i] ;
	rep(i,0,m) cin >> B[i] ;

	rep(i,1,n) A[i] += A[i-1] ;
	rep(i,1,m) B[i] += B[i-1] ;

	int ans = 0 ;

	rep(i,0,n) {
		if(A[i] > k) break ;
		int it = ub(all(B),k-A[i]) - B.begin();
		--it; 
		ans = max(ans, i+it+2); 
	}

	rep(i,0,m) {
		if(B[i] > k) break ;
		int it = ub(all(A),k-B[i]) - A.begin();
		--it; 
		ans = max(ans, i+it+2); 
	}

	cout << ans ;
}
 
int32_t main() {
 
 
    fast;
	int t=1;
	// cin>>t;
	rep(i,0,t) {
		solve(i) ;
	}
 
	// cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}

Measured memory_bytes: 6368
def main():
    import sys
    input = sys.stdin.readline
    from heapq import heappop, heappush
    N, M = map(int, input().split())
    A = []
    for a in input().split():
        heappush(A, (-1) * int(a))
    for _ in range(M):
        a = (-1) * heappop(A)
        a //= 2
        heappush(A, -a)
    print((-1) * sum(A))


if __name__ == '__main__':
    main()

Measured memory_bytes: 59760
#include <bits/stdc++.h>
using namespace std;
int main() {
    int a, b, c, m;
    cin >> a >> b >> c;
    m = __gcd(__gcd(a, b), c);
    a /= m;
    b /= m;
    c /= m;
    if (c % __gcd(a, b) == 0) cout << "YES";
    else cout << "NO";
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
typedef int _int;
#define int long long
const int N=1005;
int n,k,a[N],b[N*N],flg,ans;bool mked[N*N],mkes[N*N];
_int main(){
    ios::sync_with_stdio(false);
    cin>>n>>k;for(int i=1;i<=n;++i)cin>>a[i],a[i]+=a[i-1];
    for(int i=0;i<n;++i)for(int j=i+1;j<=n;++j)b[++flg]=a[j]-a[i];
    for(int i=50;i>=0;--i){
        int cnt=0;
        for(int j=1;j<=flg;++j){
            if(!mked[j]&&(b[j]&(1ll<<i)))mkes[j]=0,++cnt;else mkes[j]=1;
        }if(cnt>=k)ans+=1ll<<i,memcpy(mked,mkes,sizeof(mkes));
        memset(mkes,0,sizeof(mkes));
    }cout<<ans<<endl;return 0;
}

Measured memory_bytes: 6400
#include<bits/stdc++.h>
using namespace std;
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
 
typedef long long ll;
typedef pair<int, int> ii;

#define DEBUG false

struct UnionFind {
  vector<int> data;
  UnionFind(int v) : data(v, -1) {}
  int root(int x) {
    return data[x] < 0 ? x : data[x] = root(data[x]);
  }
  bool same(int x, int y) {
    return root(x) == root(y);
  }
  int size(int x) {
    return -data[root(x)];
  }
  void merge(int x, int y) {
    x = root(x), y = root(y);
    if (x != y) {
      if (size(y) > size(x))
        swap(x, y);
      data[x] += data[y];
      data[y] = x;
    }
  }
};

struct NODE{
	int x, y;
	int cost;
	
	NODE(){x = y = cost = 0;}
	NODE(int x, int y, int cost):x(x), y(y), cost(cost){}
	
	bool operator<(const NODE r){
		return cost < r.cost;
	}
};

int main(){
	
	int n, m;
	while(cin >> n >> m, m, n){
		vector<NODE> v(m);
		rep(i, m){
			int x, y, cost;
			cin >> x >> y >> cost;
			v[i] = NODE(x, y, cost);
		}
		
		SORT(v);
		
		UnionFind uni(n+1);
		
		ll ans = 0;
		rep(i, m){
			int xx = v[i].x;
			int yy = v[i].y;
			if(uni.root(xx) != uni.root(yy)){
				uni.merge(xx, yy);
				ans += v[i].cost;
			}
		}
		
		cout << ans << endl;
		
	}
	
	
	
	return 0;
}

/*
struct BIT {
  int N;
  vector<ll> data;
  BIT(int n) : N(n), data(n + 1, 0) { }
  void add(int a, ll w) {
    ++a;
    for(int x = a; x <= N; x += x & -x) {
      data[x] += w;
    }
  }
  ll sum(int a) {
    ll ret = 0;
    for(int x = a; x > 0; x -= x & -x) {
      ret += data[x];
    }
    return ret;
  }
  
  ll sum(int l, int r){//[l, r)
  	return sum(r) - sum(l);
  }
};

BIT bit = BIT(1);
int m, n;

ll dfs(int pos, int rest){
	ll ret = LLINF;
	
	if(rest == 1) return bit.sum(pos, n+1);
	for(int i = 0; i + pos <= n+1; i++){
		ll hoge1 = bit.sum(pos, pos+i);
		ll hoge2 = dfs(pos+i, rest-1);
		cout << "sum(" << pos << ", " << pos+i << "): " << hoge1 << endl;
		cout << "des(" << pos+i << ". " << rest-1 << "): " << hoge2 << endl;
		cout << endl;
		ret = min(ret, hoge1 + hoge2);
	}
	
	return ret;
}

int main(){

	while(cin >> m >> n, m, n){
		bit = BIT(n);
		rep(i, n){
			ll tmp;
			cin >> tmp;
			bit.add(i+1, tmp);
		}
		
		cout << dfs(1, m) << endl;
		
	}
	
	return 0;
}
*/

Measured memory_bytes: 3068
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
#
# Created: Jul, 13, 2020 13:52:40 by Nobody
# $Author$
# $Date$
# $URL$
__giturl__ = "$URL$"


from sys import stdin
input = stdin.readline


def main():
  N = int(input())
  A = list(map(int, input().split()))
  B = list(map(int, input().split()))

  sum_ = 0
  for i in range(N):
    temp_sum = min(A[i]+A[i+1], B[i])
    sum_ += temp_sum
    A[i+1] -= (temp_sum - min(A[i], B[i]))

  print(sum_)


if(__name__ == '__main__'):
  main()


Measured memory_bytes: 96732
#include<bits/stdc++.h>
using namespace std;
int a,b,c,n,s;
int main()
{
    cin >> a >> b >> c >> n;
    for (int i = 0; i <= a; i ++)
        for (int j = 0; j <= b; j ++)
            if ((n-i*500-j*100>=0)&&(n-i*500-j*100<=c*50))
                s ++;
    cout << s << endl;
    return 0;
}

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

int main(){
  int n;
  cin>>n;
  vector<int>x(n);
  vector<int>y(n);
  for(int i=0;i<n;i++){
    cin>>x[i]>>y[i];
  }
  sort(x.begin(),x.end());
  sort(y.begin(),y.end());
  int ans;
  if(n%2==1){
    cout<<y[n/2]-x[n/2]+1<<endl;
    return 0;
  }
  else{
    cout<<(y[n/2]+y[n/2-1])-(x[n/2]+x[n/2-1])+1<<endl;
  }
}


Measured memory_bytes: 4840
#include<iostream>
#include<cstdio>
#include<math.h>
#include<string>
#include<algorithm>
#include<functional>
#include<vector>
#include<set>
#include<map>
#define INF 999999
#define EPS 1.0e-6

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<int, P> PP;

ll n, a, b;
ll x[105000];

int main()
{
	cin >> n >> a >> b;
	for (int i = 0; i < n; i++) {
		cin >> x[i];
	}
	ll ans = 0;
	for (int i = 1; i < n; i++) {
		ans += min((x[i] - x[i - 1])*a, b);
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1024
arr = []

while true
  val1, val2, val3 = gets.split(" ").map(&:to_i)
  break if val1 == -1 && val2 == -1 && val3 == -1
  arr << [ val1, val2, val3 ]
end

ans = []

arr.each do |val|
  if val[0] == -1 || val[1] == -1
    ans << 'F'
  elsif 80 <= val[0] + val[1]
    ans << 'A'
  elsif 65 <= val[0] + val[1]
    ans << 'B'
  elsif 50 <= val[0] + val[1] || 50 <= val[2]
    ans << 'C'
  elsif 30 <= val[0] + val[1]
    ans << 'D'
  else
    ans << 'F'
  end
end

puts ans

Measured memory_bytes: 6108
#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;

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

    if(a>=b){
        cout<<"delicious"<<endl;
    }
    else if(b-a<=x){
        cout<<"safe"<<endl;
    }
    else{
        cout<<"dangerous"<<endl;
    }
    return 0;
}

Measured memory_bytes: 256
interface Pos {
  b: number;
  e: number;
}

function Main(input: string) {
  const lines = input.split('\n');
  const first = lines[0].split(' ');
  const n = +first[0];
  const x = +first[1];
  const y = +first[2];
  const map = Array(n + 1);
  const result: Pos[][] = [];
  for (let i = 1; i <= n; i++) {
    map[i] = Array(n);
    result.push([]);
  }
  
  map[x][y] = 1;
  result[1].push({b:x, e:y});
  for(let i=1;i<= n-1;i++){
    map[i][i + 1] = 1;
    result[1].push({ b: i, e: i + 1 });
  }
  
  for(let d = 2;d < n; d++){
    for(let i=0, len = result[d-1].length;i<len; i++){
      const {b, e} = result[d-1][i];
      if(map[b-1] && (map[b-1][e]||Infinity)>d && (b-1)>=1){
        map[b-1][e] = d;
        result[d].push({b: b-1, e});
      }
      if(map[b+1] && (map[b+1][e]||Infinity)>d && (b+1<e)){
        map[b+1][e]= d;
        result[d].push({b:b+1, e});
      }
      if((map[b][e-1]||Infinity)>d && (b<e-1)){
        map[b][e-1]=d;
        result[d].push({b, e: e-1});
      }
      if((map[b][e+1]||Infinity) >d && (e+1<=n)){
        map[b][e+1]=d;
        result[d].push({b, e: e+1});
      }
    }
  }
  console.log(result.splice(1).map(r=>r.length).join('\n'));
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 201532
#include<bits/stdc++.h>
using namespace std;
map<int,int> mp;
int pos=0;
int back=0; 
int dfs(int i, vector<vector<int>>& adj){
    
    if(adj[i].size()==0)
        return 0;
    
    int maximumdepth=0;
    for(int j=0;j<adj[i].size();j++){

            if(mp.find(adj[i][j]) != mp.end() )
            {
                maximumdepth = max(maximumdepth, 1 + mp[adj[i][j]]);
            }
            else{
                maximumdepth = max(maximumdepth, 1+dfs(adj[i][j],adj));
            }
          
     
    }
    mp[i]=maximumdepth;
    return maximumdepth;
    
}
int main(){
    
    int n,m; cin>>n>>m;
    vector<vector<int>> adj;
    adj.resize(n);
    int visited[n]={0};
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        adj[a-1].push_back(b-1);
    }
    int globmax=0;
    for(int i=0;i<n;i++){
      if(mp.find(i) == mp.end() ){
          dfs(i,adj);
      }
    }
    for(int i=0;i<n;i++)
        globmax=max(globmax,mp[i]);
    cout<<globmax<<endl;
}

Measured memory_bytes: 14208
#include<iostream>
using namespace std;
int main() {
	int H, W;
	while (1) {
		cin >> H >> W;
		if (H == 0 && W == 0)break;
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				cout << "#";
				if (j == W - 1)cout << endl;
			}
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 1156
import Control.Monad
import Data.Array.IO
import Data.IORef

divisor = 10^9 + 7

main = do
  n <- readLn :: IO Int
  as <- getLine >>= return . map read . words :: IO [Int]

  memo <- newArray (1,n) 0 :: IO (IOUArray Int Int)
  double_pos <- newIORef (0,0) :: IO (IORef (Int,Int))

  forM_ (zip [1..n+1] as) $ \(i,a) -> do
    m <- readArray memo a
    if m >= 1 then
      writeIORef double_pos (m, i)
      else
      writeArray memo a i
        
  (fs, sn) <- readIORef double_pos 

  let rl = (fs-1) + (n+1-sn)

  var1 <- newIORef 1 :: IO (IORef Integer)
  var2 <- newIORef 1 :: IO (IORef Integer)

  forM_ [1..n+1] $ \k -> do
    modifyIORef var1 (\x -> (x * div_modp (fromIntegral $ n+2-k) (fromIntegral k) divisor) `mod` divisor)
    if k == 1 then
      writeIORef var2 1
      else if rl < k - 1 then
      writeIORef var2 0
      else
      modifyIORef var2 (\x -> (x * div_modp (fromIntegral $ rl+1-(k-1)) (fromIntegral $ k-1) divisor) `mod` divisor)
      
    print =<< do
      a1 <- readIORef var1
      a2 <- readIORef var2
      return $ (a1 - a2) `mod` divisor

  where
    factorial n
      | n <= 1 = 1 
      | otherwise = n * factorial (n-1)
      
    combination n k
      | k > n = 0
      | k == 0 = 1
      | otherwise = ((div_modp n k divisor) * (combination (n-1) (k-1))) `mod` divisor

    div_modp a b m = (a * (power_modp b (m-2) m)) `mod` m

    power_modp a 0 m = 1
    power_modp a 1 m = a `mod` m
    power_modp a p m = ((power'^2 `mod` m) * (if mod p 2 == 0 then 1 else a)) `mod` m
      where power' = power_modp a (div p 2) m
    


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

void solve() {
    int n;
    string str;
    cin >> n >> str;

    stack<int> l, r;
    int x = 0;
    rep(i, n) {
        if (str[i] == '(') {
            l.push(0);
        } else if (l.empty()) {
            r.push(0);
        } else {
            l.pop();
        }
    }

    // cout << l.size() << " " << r.size() << endl;

    rep(i, r.size()) cout << "(";
    cout << str;
    rep(i, l.size()) cout << ")";
    cout << endl;
}

int main() {
    solve();
    return 0;
}


Measured memory_bytes: 3640
def main():
    s=input()
    t=input()
    if len(s) != len(t):
        print('No')
    ret1 = {}
    ret2 = {}
    for i in range(len(s)):
        ret1[s[i]] = ret1.get(s[i], set())
        ret1[s[i]].add(t[i])
        ret2[t[i]] = ret2.get(t[i], set())
        ret2[t[i]].add(s[i])
    if max(len(i) for i in ret1.values()) == 1 and max(len(i) for i in ret2.values()) == 1:
        print('Yes')
    else:
        print('No')

if __name__ == '__main__':
    main()

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <map>
#include <string.h>
#include <algorithm>
#define P pair<int,int>
#define INF (1<<30)
using namespace std;

vector<int> Ind(100010);		//Ind[n]  ??\???n???euler tour??¨??§???????????°?????????
vector<bool> f(100010, false);	//
vector<vector<int>> T(100010);	//??°??????
vector<P> ET;                   //????????¢?´¢??¨

void dfs(int n,int dep) {
	f[n] = true;
	ET.emplace_back(make_pair(dep,n));
	Ind[n] = ET.size() - 1;
	for (int next : T[n]) {
		if (f[next] == true) continue;
		dfs(next,dep + 1);
		ET.emplace_back(make_pair(dep,n));
	}
}

P RMQ(int a, int b, int k, int l, int r, vector<P>& node) {
	if (r <= a || b <= l) {return P(INF, INF); }
	if (a <= l && r <= b) return node[k];

	P vl = RMQ(a, b, 2 * k + 1, l, (l + r) / 2,node);
	P vr = RMQ(a, b, 2 * k + 2, (l + r) / 2, r, node);
	return min(vl, vr);
}

int main() {
	cin.tie(0); ios::sync_with_stdio(false);
	//Graph initialize
	int n_; cin >> n_;
	for (int i = 0; i < n_; i++) {
		int k; cin >> k;
		for (int j = 0; j < k; j++) {
			int c; cin >> c;
			T[i].emplace_back(c);
			T[c].emplace_back(i);
		}
	}
	//ET??¨?????????
	dfs(0,0);

	//RMQ initialize
	n_ = ET.size();

	int n = 1;
	while (n < n_) n *= 2;
	vector<P> node(2 * n - 1, P(INF, INF));

	for (int i = 0; i < n_;i++) { node[n - 1 + i] = ET[i]; }
	for (int i = n - 2; i >= 0; i--) { node[i] = min(node[2 * i + 1], node[2 * i + 2]); }

	//Answer
	int q; cin >> q;
	for (int i = 0; i < q; i++) {
		int u, v; cin >> u >> v;
		int a = Ind[u], b = Ind[v];
		if (a > b) { swap(a, b); }
		if (a == b) { cout << u << endl; continue; }
		cout << RMQ(a,b, 0, 0, n, node).second << endl;
	}
}

Measured memory_bytes: 20564
n=int(input())
a=list(map(int,input().split()))
if n%2==0:
    b=[a[n-1-2*i] for i in range(0,n//2)]
    c=[a[2*i] for i in range(0,n//2)]
    ans=b+c
    print(*ans)
else:
    b=[a[n-1-2*i] for i in range(0,(n-1)//2+1)]
    c=[a[2*i+1] for i in range(0,(n-1)//2)]
    ans=b+c
    print(*ans)


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

int main(){
    int n,m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    rep(i,m){
        int a,b;
        cin >> a >> b;
        a--;b--;
        g[a].push_back(b);
    } 
    int now = 0,flag = 0;
    for(auto i:g[now]){
        for(auto j :g[i]){
            if(j==n-1) flag = 1;
        }
    }
    if(flag) cout << "POSSIBLE" << endl;
    else cout << "IMPOSSIBLE" << endl;
    
}

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

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

  map<int, int> prime;

  for(int i=1;i<=n;i++) {
    int copy = i;
    for(int j=2;j<=i;j++) {
      while(copy % j == 0) {
        copy /= j;
        prime[j]++;
      }
    }
  }

  multiset<int> primeSet;

  for(auto it = prime.begin();it != prime.end(); it++) {
    primeSet.emplace(it->second + 1);
  }

  auto lowerThan75 = primeSet.lower_bound(75);
  int seventyFive = primeSet.size() - distance(primeSet.begin(), lowerThan75);
  auto lowerThan25 = primeSet.lower_bound(25);
  int twentyFive = primeSet.size() - distance(primeSet.begin(), lowerThan25);
  auto lowerThan15 = primeSet.lower_bound(15);
  int fifteen = primeSet.size() - distance(primeSet.begin(), lowerThan15);
  auto lowerThan5 = primeSet.lower_bound(5);
  int five = primeSet.size() - distance(primeSet.begin(), lowerThan5);
  auto lowerThan3 = primeSet.lower_bound(3);
  int three = primeSet.size() - distance(primeSet.begin(), lowerThan3);

  int a = seventyFive;
  int b = twentyFive * (three - 1);
  int c = fifteen * (five - 1);
  int d = five * (five - 1) / 2 * (three - 2);

  cout << a + b + c + d << endl;
}

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

int main(){
  int n,m,c,count=0; cin>>n>>m>>c;
  vector<int> a(m),b(m);
  rep(i,m){cin>>b.at(i);}
  rep(i,n){
    int sum=c;
    rep(j,m){
      cin>>a.at(j);
      sum+=a.at(j)*b.at(j);
    }
    if(sum>0){count++;}    
  }
  cout<<count;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;

int main() {
    ll L, R;

    scanf("%lld %lld", &L, &R);

    if ((R-L)/2019>=1) printf("0\n");
    else {
        int minv = 2019;
        for (ll l=L; l<R; l++) {
            for (ll r=l+1; r<=R; r++) {
                int tmp = (l*r)%2019;
                minv = min(tmp, minv);
            }
        }
        printf("%d\n", minv);
    }

    return 0;
}

Measured memory_bytes: 128
# -*- coding: utf-8 -*-
"""
Created on Wed Sep 25 08:58:11 2019

@author: avina
"""

n = int(input())
d = {}
for i in range(n):
  a = list(input())
  a.sort()
  a = ''.join(a)
  if a not in d:
    d[a] = 1
  else:
    d[a]+=1
ans = 0
for i in d:
    ans += ((d[i])*(d[i]-1))//2
print(ans)

Measured memory_bytes: 17924
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

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

    if(a + b < 10) {
        out(a + b);
    }
    else {
        out("error");
    }

    re0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    
    for(int i=1;i<n+1;i++)
    {
        int x=i;
        if(x%3==0){cout<<" "<<i;}
        else if(x%3!=0 && x%10==3){cout<<" "<<i;}
        else { 
            x/=10;
            for(int u=0; ;u++){
              if(x!=0 && x%10==3){cout<<" "<<i; break;}
              if(x!=0 && x%10!=3){x/=10;}
              else break;
            }
        }
    }
    cout<<endl;
    return 0;
}


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

using ll = long long;

int main() {
  ll N, A, B;
  cin >> N >> A >> B;
  if (A == 0) {
    cout << 0 << endl;
    return 0;
  }
  ll SUM{A + B};
  ll ans = (N / SUM) * A;
  ans += min(N % SUM, A);

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
int main(int argc, char const *argv[]) {
    int n;
    cin >> n;
    set<int> st;
    REP(i,n) {
        int a; cin >> a;
        st.insert(a);
    }
    if (st.size()%2 == 0) cout << st.size()-1 << endl;
    else cout << st.size() << endl;
    return 0;
}

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

int main()
{
	int N; cin >> N;
	double ans = 0;
	for (int i = 0; i < N; i++) {
		double x;
		string u;
		cin >> x >> u;

		if (u == "BTC") x *= 380000;
		ans += x;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <functional>
#include <string>
#include <vector>
#include <set>
#include <map>

using namespace std;
//
//class UnionFind {
//private:
//	vector<int> uf;
//
//public:
//	UnionFind(int n) : uf(n, -1) {}
//
//	int find(int x) {
//		if (uf[x] < 0) {
//			return x;
//		}
//		return uf[x] = find(uf[x]);
//	}
//
//	bool unite(int x, int y) {
//		x = find(x);
//		y = find(y);
//		if (x != y) {
//			if (uf[x] > uf[y]) {
//				swap(x, y);
//			}
//			uf[x] += uf[y];
//			uf[y] = x;
//			return true;
//		} else {
//			return false;
//		}
//	}
//
//	int size(int x) {
//		return -uf[find(x)];
//	}
//
//	bool same(int x, int y) {
//		return find(x) == find(y);
//	}
//};
//
//bool gg[50][50];

int main() {
	int n, m;
	cin >> n >> m;
	vector<vector<int>> g(n);
	long long iso = 0;
	for (int i = 0; i < m; i++) {
		int u, v;
		scanf("%d %d", &u, &v);
		u--;
		v--;
		g[u].push_back(v);
		g[v].push_back(u);
		//gg[u][v] = true;
		//gg[v][u] = true;
	}
	//UnionFind uf(n * n);
	//long long naive = n * n;
	//for (int i = 0; i < n; i++) {
	//	for (int j = 0; j < n; j++) {
	//		for (int k = 0; k < n; k++) {
	//			for (int l = 0; l < n; l++) {
	//				if (gg[i][j] && gg[k][l]) {
	//					naive -= uf.unite(i * n + k, j * n + l);
	//				}
	//			}
	//		}
	//	}
	//}
	//cout << naive << endl;
	for (int i = 0; i < n; i++) {
		if (g[i].size() == 0) {
			iso++;
		}
	}
	vector<int> root(n, -1);
	function<void(int, int)> dfs = [&](int u, int r) {
		if (root[u] != -1) {
			return 0;
		}
		root[u] = r;
		for (int v : g[u]) {
			 dfs(v, r);
		}
	};
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		if (g[i].size() == 0) {
			continue;
		}
		if (root[i] != -1) {
			continue;
		}
		dfs(i, i);
		ans++;
	}
	ans *= ans;
	ans += iso * n * 2 - iso * iso;
	vector<int> color(n, -1);
	function<bool(int)> dfs2 = [&](int u) {
		for (int v : g[u]) {
			if (color[v] != -1) {
				if (color[v] != (color[u] ^ 1)) {
					return false;
				}
			} else {
				color[v] = color[u] ^ 1;
				if (!dfs2(v)) {
					return false;
				}
			}
		}
		return true;
	};
	long long b = 0;
	for (int i = 0; i < n; i++) {
		if (root[i] == i) {
			color[i] = 0;
			if (dfs2(i)) {
				b++;
			}
		}
	}
	ans += b * b;

	cout << ans << endl;
}


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

using int32 = int_fast32_t;
using int64 = int_fast64_t;

const int32 INF = 1e9;
const int32 MOD = 1e9+7;
const int64 LLINF = 1e18;

#define YES(n) cout << ((n) ? "YES\n" : "NO\n"  )
#define Yes(n) cout << ((n) ? "Yes\n" : "No\n"  )
#define ANS(n) cout << (n) << "\n"
#define REP(i,n) for(int64 i=0;i<(n);++i)
#define FOR(i,a,b) for(int64 i=(a);i<(b);i++)
#define FORR(i,a,b) for(int64 i=(a);i>=(b);i--)
#define ALL(obj) (obj).begin(),(obj).end()
#define pii pair<int32,int32>
#define pll pair<int64,int64>
#define pb(a) push_back(a)
#define mp make_pair

int64 modpow(int64 a, int64 r){
    if(r == 0)return 1;
    if(r % 2 == 0){
        return modpow(a * a % MOD, r / 2) % MOD;
    }else{
        return modpow(a, r - 1) * a % MOD;
    }
}

int64 modComb(int64 n, int64 r){
    r = min(r, n-r);
    int64 retval = 1;
    REP(i,r){
        retval = retval * (n - i) % MOD * modpow(i + 1, MOD-2) % MOD;
    }
    return retval;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int32 n,m,k;
    cin >> n >> m >> k;
    int64 pattern = modComb(n * m - 2, k - 2);
    int64 cnt1 = ((n * (n - 1) % MOD * 3 % MOD - (n - 1) * (2 * n - 1) % MOD) % MOD + MOD) % MOD;
    // FOR(i,1,n){
    //     cnt1 += i * (n - i);
    //     cnt1 %= MOD;
    // }
    cnt1 = cnt1 * m % MOD * m % MOD * pattern % MOD * n % MOD * modpow(6, MOD-2) % MOD;
    int64 cnt2 = ((m * (m - 1) % MOD * 3 % MOD - (m - 1) * (2 * m - 1) % MOD) % MOD + MOD) % MOD;
    // FOR(i,1,m){
    //     cnt2 += i * (m - i);
    //     cnt2 %= MOD;
    // }
    cnt2 = cnt2 * n % MOD * n % MOD * pattern % MOD * m % MOD * modpow(6, MOD-2) % MOD;;
    ANS((cnt1 + cnt2) % MOD);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define loop(i, x, n) for (int i = (x); i < (n); i++)
#define all(v) (v).begin(), (v).end()
#define int long long
using namespace std;
const int MOD = 1e9 + 7;
const int INF = 1e10;
template<typename T> void cmax(T &a, T b) { a = max(a, b); }
template<typename T> void cmin(T &a, T b) { a = min(a, b); }

signed main() {
  int n, m;
  while (cin >> n >> m) {
    if (n == 0 && m == 0) break;

    vector<int> h(n), w(m);
    rep(i, n) cin >> h[i];
    rep(i, m) cin >> w[i];

    map<int, int> mpH, mpW;
    rep(i, n) {
      int tmp = h[i];
      mpH[tmp]++;
      loop(j, i + 1, n) {
        tmp += h[j];
        mpH[tmp]++;
      }
    }
    rep(i, m) {
      int tmp = w[i];
      mpW[tmp]++;
      loop(j, i + 1, m) {
        tmp += w[j];
        mpW[tmp]++;
      }
    }
    int ans = 0;
    for (auto x : mpH) {
      if (mpW.count(x.first)) ans += x.second * mpW[x.first];
    }
    cout << ans << endl;
  }

  return 0;
}



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

typedef long long ll;
const int maxn=200010;
int n,k;
int a[maxn];
ll sum[maxn], num[maxn], ans, c[maxn]; 
int cnt;

int lowbit(int x){ return x&(-x); }
ll Sum(int x){
	ll ret=0;
	while(x){ ret+=c[x]; x-=lowbit(x); }
	return ret;
}
void add(int x){ while(x<maxn){ c[x]++; x+=lowbit(x); } }

int main(){

	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]), a[i]-=k, sum[i]=sum[i-1]+a[i];
	for(int i=1;i<=n;i++) num[++cnt]=sum[i];
	num[++cnt]=0;
	sort(num+1,num+1+cnt);
	cnt=unique(num+1,num+1+cnt)-num-1;
	add(lower_bound(num+1,num+1+cnt,0)-num);
	for(int i=1;i<=n;i++){
		ans+=Sum(lower_bound(num+1,num+1+cnt,sum[i])-num);
		add(lower_bound(num+1,num+1+cnt,sum[i])-num);
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 5760
from collections import Counter
n, k = map(int, input().split())
a = list(map(int, input().split()))
f = list(map(int, input().split()))
a.sort()
f.sort(reverse=True)

la = 10**6+1
cnt = [0] * la
for u in a:
    cnt[u] += 1
for i in range(1, la):
    cnt[i] += cnt[i-1]


def judge(x):
    y = k
    for i in range(n):
        goal = x//f[i]
        if a[i] > goal:
            y -= a[i] - goal
            if y < 0:
                return False
    return y >= 0


left = -1
right = 10**12 + 1
while left + 1 < right:
    mid = (left + right)//2
    if judge(mid):
        right = mid
    else:
        left = mid

print(right)


Measured memory_bytes: 137864
#include <bits/stdc++.h>
using namespace std;
#define rep0(i,n) for(int (i) = 0; (i) < (n); ++(i))
#define rrep0(i,n) for(int (i) = (n) - 1; (i) >= 0; --(i))
#define rep1(i,n) for(int (i) = 1; (i) < (n); ++(i))
#define rrep1(i,n) for(int (i) = (n) - 1; (i) >= 1; --(i))
#define nfor(i,a,b) for(int (i) = (a); (i) < (b); ++(i))
#define ll long long
#define mod (1000000007)
#define YES cout << "YES" << endl;
#define Yes cout << "Yes" << endl;
#define yes cout << "yes" << endl;
#define NO cout << "NO" << endl;
#define No cout << "No" << endl;
#define no cout << "no" << endl;
#define all(x) (x).begin(),(x).end()

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

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

int main()
{
    string s;
    ll cnt0 = 0,cnt1 = 0;
    cin >> s;
    rep0(i, s.size()){
        if (s[i] == '0')++cnt0;
        else ++cnt1;
    }
    cout << min(cnt0, cnt1) * 2 << endl;
    return 0;
}


Measured memory_bytes: 512
using System;
using System.Linq;
class t{
static void Main()=>
  Console.WriteLine(
  Console.ReadLine().Split()
  .Select(
    (x,i)=>new{v=int.Parse(x),i})
  .ToArray()
  .Aggregate(
    (r,v)=>new{
      v=(v.v%r.v==0?1:-1)*r.v+v.v,
      r.i})
  .v);
}

Measured memory_bytes: 13396
#include<bits/stdc++.h>
#include <iostream>
//#include <boost/math/common_factor.hpp>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pair<int, int> > vpii;
typedef vector<pair<ll, ll> > vpll;

#define all(x) x.begin(), x.end()
#define reg(i,x) for(ll i=0;i<x;i++)
#define regi(i,a,x) for(ll i=a;i<x;i++)
#define rev(i,n) for(ll i=n-1;i>0;i--)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
//const ll INF = 1e18;
const int INF = 1e9;
const int MOD = 1e9 + 7;
const int nax = 1000000 + 10;
int gcd(int a,int b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a,int b)
{
    return (a*b)/gcd(a,b);
}
ll MAXN=10e9;
int main()
{
    ll x,k,d;
    cin>>x>>k>>d;
    x=abs(x);
    ll a=abs(x)/d,ans=0;
    if(a>=k)
    {
        ans=x-(k*d);
        cout<<ans<<endl;
    }
    else
    {
        x-=a*d;
        k-=a;
        if(k%2==0)
        {
            cout<<x<<endl;
        }
        else
        {
            ans=abs(x-d);
            cout<<ans<<endl;
        }
    }
}


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

#define fi first
#define se second
#define m_p make_pair
#define p_b push_back
#define e_b emplace_back
#define all(x) (x).begin(),(x).end()
#define uniq(x) ((x).erase(unique(all(x)),(x).end()))
#define sz(x) ((int)(x).size())

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

#ifdef LOCAL//compile with -DLOCAL
#define debug(x) cerr<<"LINE"<<__LINE__<<" : "<<#x<<" = "<<(x)<<endl
#define debug_vec(x) cerr<<"LINE"<<__LINE__<<" : "<<#x<<" = ";\
  rep(i,sz(x)){cerr<<x[i]<<" ";}cerr<<endl
#define debug_mat(x) cerr<<"LINE"<<__LINE__<<" : "<<#x<<" = "<<endl;\
  rep(i,sz(x)){rep(j,sz(x[i])){cerr<<x[i][j]<<" ";}cerr<<endl;}cerr<<endl
#else
#define debug(x) void(0)
#define debug_vec(x) void(0)
#define debug_mat(x) void(0)
#endif

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


int main(){
  ios_base::sync_with_stdio(false);cin.tie(0);
  int N,K;
  cin >> N >> K;
  vector<int> A(N);
  rep(i,N)  cin >> A.at(i);

  int g=0;
  rep(i,N)  g=gcd(g,A.at(i));
  rep(i,N){
    int tmp=A.at(i)-K;
    if(tmp>=0 && tmp%g==0){
      cout << "POSSIBLE" << endl;
      return 0;
    }
  }
  cout << "IMPOSSIBLE" << endl;

  return 0;
}

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

#include <atcoder/segtree>

using namespace std;
using namespace atcoder;
#define rep(i,l,r) for(int i = l; i < r; ++i)

int e() {return 0;}
int op(int s1, int s2) {return max(s1, s2);}

int main() {
    int n, q, t, x, y;
    cin >> n >> q;

    vector<int> a(n);
    rep(i, 0, n) cin >> a[i];

    segtree<int, op, e> st(a);
    rep(i, 0, q) {
        cin >> t >> x >> y;

        if (t == 1) {
            st.set(x - 1, y);
        } else if (t == 2) {
            cout << st.prod(x - 1, y) << endl;
        } else {
            cout << st.max_right(x - 1, [&](int s) {return s < y;}) + 1 << endl;
        }
    }
}


Measured memory_bytes: 5760