akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

#define fr(i, n)    for(int i=0; i<(int)n; ++i)
#define rfr(i, n)   for(int i=(int)n-1; i>=0; --i)
#define foor(i,a,n) for(int i=a; i<=(int)n; ++i)
#define rfoor(i,n,a)for(int i=(int)n; i>=a; --i)
#define foru(it, v) for(auto it : v)
#define si(n)       scanf("%d", &n)
#define si2(n,m)    scanf("%d%d", &n, &m)
#define si3(n,m,l)  scanf("%d%d%d", &n, &m, &l)
#define sl(n)       scanf("%lld", &n)
#define sl2(n,m)    scanf("%lld%lld", &n, &m)
#define sl3(n,m,l)  scanf("%lld%lld%lld", &n, &m, &l)
#define sd(n)       scanf("%lf", &n)
#define sld(n)      scanf("%Lf", &n)
#define sc(n)       scanf(" %c", &n)
#define sstr(n)     scanf("%s", n)
#define pi(n)       printf("%d\n", n)
#define pis(n)      printf("%d ", n)
#define pi2(n,m)    printf("%d %d\n", n, m)
#define pi3(n,m,l)  printf("%d %d %d\n", n, m, l)
#define pl(n)       printf("%lld\n", n)
#define pls(n)      printf("%lld ", n)
#define pl2(n,m)    printf("%lld %lld\n", n, m)
#define pl3(n,m,l)  printf("%lld %lld %lld\n", n, m, l)
#define pc(n)       printf("%c", n)
#define pstr(n)     printf("%s\n", n)
#define pstr2(n, m) printf("%s %s\n", n, m)
#define ff          first
#define ss          second
#define all(v)      v.begin(), v.end()
#define rall(v)     v.rbegin(), v.rend()
#define sz(v)       (int)v.size()
#define pub         push_back
#define pob         pop_back()
#define mmst(a, n)  memset(a, n, sizeof a);
#define ppcnt(n)    __builtin_popcountll(n);
#define leadingZ(n) __builtin_clz(n)
#define trailingZ(n)__builtin_ctz(n)
#define OO          0x3f3f3f3f
#define OOLL        0x3f3f3f3f3f3f3f3f
#define MOD         1000000007
#define EPS         0.000000001
#define ndl         "\n"
#define fastin      ios::sync_with_stdio(false); cin.tie(nullptr);
#define infile      freopen("input.txt", "r", stdin);
#define outfile     freopen("output.txt", "w", stdout);
#define PNO         printf("NO\n")
#define PYES        printf("YES\n")
#define pno         printf("No\n")
#define pyes        printf("Yes\n")
#define pln         printf("\n")

//#define row         vector<long long>
//#define matrix      vector<row>
//#define ROWS(v)     (v).size()
//#define COLS(v)     (v)[0].size()

#define DBG1(x)     cerr<<#x<<":"<<(x)<<'\n';
#define DBG2(x, y)  cerr<<#x<<":"<<(x)<<"  "<<#y<<":"<<(y)<<'\n';
#define DBG3(x,y,z) cerr<<#x<<":"<<(x)<<"  "<<#y<<":"<<(y)<<"  "<<#z<<":"<<(z)<<'\n';

using namespace std;

typedef long long lld;
typedef long double LD;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vii;
typedef vector<long long> vll;
typedef vector<pair<int, int>> vpii;
typedef vector<pair<long long , long long>> vpll;
typedef complex<double> point;

const int N = 2e6 + 9;

int t, id, n, m, x, y, k, c, xx, yy, ans;
//int a[N], f[N], cu[N], b[N];
vii v, adj[N];
bool fl, ok;
lld res, tot, sum;
char ch;
//string s, z;
char s[N], z[N];

int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    //fastin;
    si(n);
    pi(n*n*n);
    return 0;
}


Measured memory_bytes: 49024
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<int(n);i++)
#define N 510


int main(){
	int a[N][N];
	f(i, N){
		f(j, N)a[i][j] = 0;
	}
	vector<int>b;
	vector<int>c;
	vector<int>d;
	vector<int>e;
	int n, m, k;
	int x, y, z;
	long long s, ans;
	bool v = true;
	ans = 0;
	scanf("%d %d", &n, &m);
	f(i, n){
		f(j,m)scanf("%d", &a[i][j]);
	}
	f(i, n-1){
		f(j, m){
			if (a[i][j] % 2 == 1){
				if (j < m - 1){
					if (a[i][j + 1] % 2 == 1){
						b.push_back(i + 1);
						c.push_back(j + 1);
						d.push_back(i + 1);
						e.push_back(j + 2);
						a[i][j]--;
						a[i][j + 1]++;
					}
					else{
						b.push_back(i + 1);
						c.push_back(j + 1);
						d.push_back(i + 2);
						e.push_back(j + 1);
						a[i][j]--;
						a[i + 1][j]++;
					}
				}
				else{
					b.push_back(i + 1);
					c.push_back(j + 1);
					d.push_back(i + 2);
					e.push_back(j + 1);
					a[i][j]--;
					a[i + 1][j]++;
				}
			}
		}
	}
	f(j, m-1){
		if (a[n - 1][j] % 2 == 1){
			b.push_back(n);
			c.push_back(j + 1);
			d.push_back(n);
			e.push_back(j + 2);
			a[n-1][j]--;
			a[n-1][j + 1]++;
		}
	}

	printf("%d\n", b.size());
	f(i, b.size()){
		printf("%d %d %d %d\n", b[i], c[i], d[i], e[i]);
	}


	return 0;
}

Measured memory_bytes: 5220
#include<iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    if((a<b) && (b<c)){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}


Measured memory_bytes: 3100
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();

        for (int i = 1; i < b + 1; i++) {
            if ((a * i) % b == c) {
                System.out.println("YES");
                return;
            }
        }
        System.out.println("NO");
    }

}

Measured memory_bytes: 22996
n,k = map(int,input().split())
r,s,p = map(int, input().split())
t = list(input())

ans = 0

i = 0

while i < n-k:
  if t[i] != t[i+k]:
    if t[i+k] == "r":
      ans += p
    elif t[i+k] == "s":
      ans += r
    else:
      ans += s
  else:
    if t[i+k] == "r":
      t[i+k] = "g"
    elif t[i+k] == "s":
      t[i+k] = "g"
    else:
      t[i+k] = "g"
  i += 1

for j in range(k):
  if t[j] == "r":
    ans += p
  elif t[j] == "s":
    ans += r
  else:
    ans += s 
      
print(ans)
    

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

void textIO()
{
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

}

const int N = 1000001;

vector<int> divis[N];

int main()
{

    textIO();
    fastIO();

    for(int i=1;i<=N;i++){
        for(int j=i;j<=N;j+=i){
            divis[j].push_back(i);
        }
    }

    long long n, cnt = 0;
    cin >> n;

    vector<long long> arr(n);

    unordered_map<long long, long long> ump;

    for(int i=0;i<n;i++){
        cin >> arr[i];
        ump[arr[i]]++;
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<divis[arr[i]].size();j++){
            if(divis[arr[i]][j] == arr[i]){
                if(ump[divis[arr[i]][j]] > 1){
                    cnt++;
                    break;
                }
            }
            else if(ump[divis[arr[i]][j]] > 0){
                cnt++;
                break;
            }
        }
    }

    cout << n-cnt << '\n';

    return 0;
}


Measured memory_bytes: 141980
#include<bits/stdc++.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)
#define fi first
#define se second
#define INF 1000000009
#define LLINF 1000000000000000009LL
using ll = long long;

double dp[3009][3009];

int main(){
  int n;
  cin>>n;
  vector<double>p(n);
  rep(i,n)cin>>p[i];
  dp[0][0]=1;
  rep(i,n){
    rep(j,n+1){
      dp[i+1][j+1]+=dp[i][j]*p[i];
      dp[i+1][j]+=dp[i][j]*(1-p[i]);
    }
  }
  double ans=0;
  rep2(i,(n+1)/2,n+1){
    ans+=dp[n][i];
  }
  printf("%.10f\n",ans);
  return(0);
}


Measured memory_bytes: 70784
#include<bits/stdc++.h> //Ithea Myse Valgulious
namespace chtholly{
typedef long long ll;
#define re0 register int
#define rec register char
#define rel register ll
#define gc getchar
#define pc putchar
#define p32 pc(' ')
#define pl puts("")
/*By Citrus*/
inline int read(){
  int x=0,f=1;char c=gc();
  for (;!isdigit(c);c=gc()) f^=c=='-';
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return f?x:-x;
  }
inline bool read(ll &x){
  x=0;int f=1;char c=gc();
  for (;!isdigit(c)&&~c;c=gc()) f^=c=='-';
  if (!~c) return 0;
  for (;isdigit(c);c=gc()) x=(x<<3)+(x<<1)+(c^'0');
  return x=f?x:-x,1;
  }
template <typename mitsuha>
inline int write(mitsuha x){
  if (!x) return pc(48);
  if (x<0) x=-x,pc('-');
  int bit[20],i,p=0;
  for (;x;x/=10) bit[++p]=x%10;
  for (i=p;i;--i) pc(bit[i]+48);
  }
inline char fuhao(){
  char c=gc();
  for (;isspace(c);c=gc());
  return c;
  }
}using namespace chtholly;
using namespace std;
const int yuzu=1e5,mod=1e9+7;
int cnt[yuzu|10];

ll kasumi(ll a,ll b){
ll s=1;
for (;b;b>>=1,a=a*a%mod)
  if (b&1) s=s*a%mod;
return s;
}

int main(){
int i,n=read();
for (i=1;i<=n;++i) cnt[read()]++;
for (i=1;i<=n;++i){
  if (cnt[i]&&cnt[i]^2) return puts("0"),0;
  if (cnt[i]&&!(i&1)^(n&1)) return puts("0"),0;
  }
write(kasumi(2,n>>1));
}

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

using namespace std;

//#define int long long
#define FOR(i, j, k) for(int i = j; i < (int)k; ++i)
#define rep(i, j) FOR(i, 0, j)
#define INF (1 << 30)

typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> Pi;

const int MOD = 1e9 + 7;
const int dy[] = {0, 0, 1, -1};
const int dx[] = {1, -1, 0, 0};

template <class T> void chmin(T& a, const T& b) { a = min(a, b); }
template <class T> void chmax(T& a, const T& b) { a = max(a, b); }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

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

    int e, y;
    cin >> e >> y;
    if(e == 0) {
    	if(1989 <= y && y <= 2016) cout << "H" << y - 1988 << endl;
    	else if(1926 <= y && y <= 1988) cout << "S" << y - 1925 << endl;
    	else if(1912 <= y && y <= 1925) cout << "T" << y - 1911 << endl;
    	else cout << "M" << y - 1867 << endl;
    }
    else if(e == 1) {
    	cout << y + 1867 << endl;
    }
    else if(e == 2) {
    	cout << y + 1911 << endl;
    }
    else if(e == 3) {
    	cout << y + 1925 << endl;
    }
    else {
    	cout << y + 1988  << endl;
    }
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;

const ll LongINF=1e13+7;
const int INF=1e9+7;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};

template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template <class T, class Y>T GCD(T a, Y b){if(a<b){int c=a;a=b;b=c;}if (a % b == 0){return b;}return GCD(b, a % b);}
template<class T,class Y>T LCM(T a,Y b){return (a*b)/GCD(a,b);}
void clear(queue<pair<int, int>> &q){queue<pair<int, int>> empty;swap(q, empty);} //queueの中身の型は適時変更を忘れない

using vi=vector<int>;
using vii=vector<vi>;

#define REP(i,a,b) for(ll i=(a);i<(b);i++)
#define rep(i,n) REP(i,0,n)
#define pb push_back
#define rv reverse
#define ALL(a) (a).begin(),(a).end()
#define decimal(x) fixed<<setprecision(x)

int main(){
    ll n,ans=0;
    vi cnt(3,0);
    cin>>n;
    vector<string> s(n);
    rep(i,n){
        cin>>s[i];
        rep(j,s[i].size()-1){
            if(s[i][j]=='A'&&s[i][j+1]=='B')ans++;
        }
        if(s[i][0]=='B'&&s[i][s[i].size()-1]=='A')cnt[0]++;
        else if(s[i][0]=='B')cnt[1]++;
        else if(s[i][s[i].size()-1]=='A')cnt[2]++;
    }
    //cout<<ans<<endl;
    //cout<<cnt[0]<<" "<<cnt[1]<<" "<<cnt[2]<<endl;
    if(cnt[2]!=0&&cnt[1]!=0){
        ans+=cnt[0]+1;
        cnt[1]--;
        cnt[2]--;
    }
    else if(cnt[1]!=0){
        ans+=cnt[0];
        cnt[1]--;
    }else if(cnt[2]!=0){
        ans+=cnt[0];
        cnt[2]--;
    }else{
        ans+=max(0,cnt[0]-1);
    }
    ans+=min(cnt[1],cnt[2]);
    cout<<ans<<endl;
    return 0;
}

//a=97,z=122

Measured memory_bytes: 3640
#include <bits/stdc++.h>
// #pragma GCC optimize ("O3")
// #pragma GCC target ("sse4")
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;

#define REP(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for (int i=(a); i<(b); ++i)
#define FORD(i,a,b) for (int i=(a)-1; i>=(b); --i)

#define pb push_back
#define mp make_pair
#define st first
#define nd second

const int MOD = 1000000007;

int A[200];

int main() {
  // ios_base::sync_with_stdio(0);

  int N;
  scanf("%d", &N);
  REP(i,N) scanf("%d", &A[i]);

  int all = 1, odd = 1;
  REP(i,N) {
    all *= 3;
    odd *= (A[i] % 2 ? 1 : 2);
  }
  printf("%d\n", all - odd);
}


Measured memory_bytes: 256
N = int(input())

P2 = list(range(2,30001,2))
P3 = list(range(3,30001,6))
for i in range(1,5002):
  if (N-i*3)%2==0 and 0<(N-3*i)<=5000:
    x = 3*i
    y = (N-i*3)
    break
if N==5 or N>6:
  ans = P2[:x]+P3[:y]
elif N==3:
  ans = [2,5,63]
elif N==4:
  ans = [2,5,20,63]
elif N==6:
  ans = [2,3,4,185,7,9]
if N==19999:
  ans = P2[:14997]+P3[:5000]+[19,425]
print(*ans)

Measured memory_bytes: 4712
#include <iostream>
#include <algorithm>
#include <string>
#include <numeric>
#include <math.h>
#include <vector>
#include <boost/math/common_factor_rt.hpp>
using namespace std;
#define rep(i, n) for(int i = 0;i < n;i++)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define ll long long

int main(){
  int N;
  cin >> N;
  int p[100];
  int c[100];
  rep(i, N) cin >> p[i];
  rep(i, N) c[i] = i+1;
  int count1 = 0;
  int count2 = 0;
  int id1, id2;
  
  rep(i, N){
    if(p[i]!=c[i]){
      count1++;
      id2 = id1;
      id1 = i;
    }
  }
  if(count1==0){
    cout << "YES" << endl;
    return 0;
  }else if(count1!=2){
    cout << "NO" << endl;
    return 0;    
  }
  if(p[id1]==c[id2] &&p[id2]==c[id1]) cout << "YES" << endl;
  else cout << "NO" << endl;
}

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

int main() {
	int a[3]{ 1 };
	string s;
	while (cin >> s) {
		swap(a[s[0] - 'A'], a[s[2] - 'A']);
	}
	rep(k, 3)if (a[k])printf("%c\n", k + 'A');
	return 0;
}

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

int main() {
  int n, l, i;
  cin >> n >> l;
  vector<string> s(n);
  for (i = 0; i < n; i++) {
    cin >> s[i];
  }
  sort(s.begin(), s.end());
  string ans;
  for (i = 0; i < n; i++) {
    ans += s[i];
  }
  cout << ans << "\n";
  return 0;
}

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

bool is_war(const vector<int>& x, const vector<int>& y) {
  return *max_element(x.begin(), x.end()) >= *min_element(y.begin(), y.end());
}

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> x(N + 1), y(M + 1);
  cin >> x[0] >> y[0];
  rep(i, 0, N) cin >> x[i + 1];
  rep(i, 0, M) cin >> y[i + 1];

  if (is_war(x, y))
    cout << "War" << endl;
  else
    cout << "No War" << endl;

  return 0;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vb=vector<bool>;
using vvb=vector<vb>;
using vd=vector<double>;
using vvd=vector<vd>;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using tll=tuple<ll,ll>;
using tlll=tuple<ll,ll,ll>;
using vs=vector<string>;

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define rep(i,n) range(i,0,n)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define range(i,a,n) for(int i=(a);i<(n);i++)

#define LINF ((ll)1ll<<60)
#define INF ((int)1<<30)
#define EPS (1e-9)
#define MOD (1000000007ll)
#define fcout(a) cout<<setprecision(a)<<fixed
#define fs first
#define sc second
#define PI 3.1415926535897932384

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

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;}
template<class S>S acm(vector<S>&a){return accumulate(all(a),S());}
template<class S>S max(vector<S>&a){return *max_element(all(a));}
template<class S>S min(vector<S>&a){return *min_element(all(a));}
void YN(bool b){cout<<(b?"YES":"NO")<<"\n";}
void Yn(bool b){cout<<(b?"Yes":"No")<<"\n";}
void yn(bool b){cout<<(b?"yes":"no")<<"\n";}

ll max(int a,ll b){return max((ll)a,b);} ll max(ll a,int b){return max(a,(ll)b);}
template<class T>void puta(T&&t){cout<<t<<"\n";}
template<class H,class...T>void puta(H&&h,T&&...t){cout<<h<<' ';puta(t...);}
template<class S,class T>ostream&operator<<(ostream&os,pair<S,T>p){os<<"["<<p.first<<", "<<p.second<<"]";return os;};
template<class S>auto&operator<<(ostream&os,vector<S>t){bool a=1; for(auto s:t){os<<(a?"":" ")<<s;a=0;} return os;}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int q;
	cin>>q;
	while(q--){
		int cnt=0;
		string s;
		cin>>s;
		while(s.size()!=1){
			ll mx=0;
			rep(i,s.size()-1){
				ll a=stoll(s.substr(0,i+1));
				ll b=stoll(s.substr(i+1));
				chmax(mx,a*b);
			}
			cnt++;
			s=to_string(mx);
		}
		cout<<cnt<<"\n";
	}
}


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

int main(){
    int n;
    cin>>n;
    int result = 0;
    for (int i = 0; i < n; i++){
        int k ;
        scanf("%d",&k);
        result += k;
    }
    cout<<result-n<<endl;

}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var sc = bufio.NewScanner(os.Stdin)

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	_ = nextLine()

	inputs := strings.Split(nextLine(), " ")
	var A []int
	for i := 0; i < len(inputs); i++ {
		num, _ := strconv.Atoi(inputs[i])
		A = append(A, num)
	}

	ans := 1000000000
	for i := 0; i < len(A); i++ {
		count := 0
		for A[i]%2 == 0 {
			A[i] = A[i] / 2
			count++
		}
		if ans > count {
			ans = count
		}
	}
	fmt.Println(ans)
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

ll dp[409][409], sum[409][409];
ll a[409];
int N;

ll solve(int l, int r)
{
    if (dp[l][r] != -1) return dp[l][r];

    if (l == r) return dp[l][r] = 0;

    ll mn = 1e18;
    for (int i = l; i < r; i++)
    {
        mn = min(solve(l, i) + solve(i + 1, r) + sum[l][r], mn);
    }

    dp[l][r] = mn;
    return dp[l][r];
}

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

    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> a[i];
    }

    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++) dp[i][j] = -1;
    }

    ll full = 0;
    for (int i = 1; i <= N; i++)
    {
        full = 0;
        for (int j = i; j <= N; j++)
        {
            full += a[j];
            sum[i][j] = full;
        }
    }

    cout << solve(1, N) << "\n";
}

Measured memory_bytes: 6188
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]

uft = [-1] * N
def uft_root(a):
	if uft[a] < 0:
		return a
	uft[a] = uft_root(uft[a])
	return uft[a]

def uft_same(a, b):
	return (uft_root(a) == uft_root(b))

def uft_size(a):
	return -uft[uft_root(a)]

def uft_merge(a, b):
	if uft_same(a, b):
		return
	hi, lo = uft_root(a), uft_root(b)
	if -uft[hi] < -uft[lo]:
		hi, lo = lo, hi
	uft[hi] += uft[lo]
	uft[lo] = hi

result = [(N * (N - 1)) // 2]
for a, b in AB[::-1]:
	a, b = a - 1, b - 1
	if uft_same(a, b):
		result += [result[-1]]
		continue
	result += [result[-1] - (uft_size(a) * uft_size(b))]
	uft_merge(a, b)

for l in result[::-1][1:]:
	print(l)


Measured memory_bytes: 36028
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <list>
#include <iomanip>
#include <queue>
#include <functional>
#include <cassert>
#include <cmath>
#include <set>
#include <map>
#include <numeric>

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repe(i, n) for(int i = 0; i <= (n); i++)
#define fo(i, a, b) for(int i = (a); i < (b); i++)
#define foe(i, a, b) for(int i = (a); i <= (b); i++)
#define NL << endl

using namespace std;
using ll = long long;
const int INTMAX = numeric_limits<int>::max();
const int INTMIN = numeric_limits<int>::min();
const ll LLMAX = numeric_limits<long long>::max();
const ll LLMIN = numeric_limits<long long>::min();
const int MOD = 1000000007;
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }

using namespace std;

int main() {
	int n;
	cin >> n;
	vector<int> x(n), y(n), h(n);

	rep(i, n) {
		cin >> x[i] >> y[i] >> h[i];
	}

	rep(sy, 101) rep(sx, 101) {
		int minH = INTMAX;
		int dis = -1;
		bool suc = false;
		rep(i, n) {
			int t = abs(x[i] - sx) + abs(y[i] - sy);
			if (h[i] == 0) {
				minH = min(minH, t);
				if (dis != -1 && dis > minH)break;
			} else {
				if (dis == -1) dis = h[i] + t;
				else if (dis != h[i] + t) break;
			}
			if (i == n - 1) suc = true;
		}
		if (suc) {
			cout << sx << ' ' << sy << ' ' << dis NL;
			break;
		}
	}

	return 0;

}



Measured memory_bytes: 256
h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
d = (-1, 0), (1, 0), (0, -1), (0, 1)
p = [(i, j) for i in range(h) for j in range(w) if a[i][j] == '#']
n = h * w - len(p)
r = 0
while n:
    r += 1
    s = []
    for i, j in p:
        for di, dj in d:
            di += i
            dj += j
            if 0 <= di < h and 0 <= dj < w and a[di][dj] == '.':
                a[di][dj] = '#'
                s.append((di, dj))
    p = s
    n -= len(p)
print(r)

Measured memory_bytes: 132432
N=int(input())
data=list(input())
r=data.count("R")
w=data.count("W")
last=[]
for i in range(r):
    last.append("R")
for i in range(w):
    last.append("W")
ans=0
for i in range(len(data)):
    if last[i]!=data[i]:
        ans+=1
print(int(ans/2))

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

using namespace std;

int v[105];

int main(){
    int n,i,j,answer=1000005,val=0;

    cin>>n;

    for(i=1;i<=n;i++)
        cin>>v[i];

    for(i=1;i<=105;i++){
        val=0;

        for(j=1;j<=n;j++)
            val+=(v[j]-i)*(v[j]-i);

        if(val<answer)
            answer=val;
    }

    cout<<answer;

    return 0;
}


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

int main()
{  int n,m;
cin>>n>>m;
char  matrix[n][m] ;
for(int i=0;i<n;i++)
{
  for(int j=0; j<m;j++)
  {
    cin>>matrix[i][j] ;
  }
}
long long int ans=0;
long long int dp[n+1][m+1];
dp[0][0]=1;

for(int i=0;i<=n;i++)
{
  for(int j=0; j<=m;j++)
  {
     if(i==0 || j==0)
     dp[i][j]=0;
     else  if(i==1 and j==1)
     dp[i][j]=1;
     else if(matrix[i-1][j-1]=='#')
     {
        dp[i][j]=0;
     }
     else
     {
       dp[i][j] =(dp[i-1][j]+dp[i][j-1])%p ;
     }
     
  }
}
cout<<dp[n][m]<<endl;

  return 0;
}











Measured memory_bytes: 9088
package main

import (
	"fmt"
	"math"
)

var N, ans int

func main() {
	fmt.Scan(&N)

	A := make([][]int, 2)
	for i := 0; i < 2; i++ {
		A[i] = make([]int, N)

		for j := 0; j < N; j++ {
			fmt.Scan(&A[i][j])
		}
	}

	fmt.Println(bfs(A))
}

func bfs(a [][]int) (ans int) {
	q := make([][]int, 0)
	q = append(q, []int{0, 0, 0})

	for len(q) != 0 {
		var y, x = q[0][0], q[0][1]
		var c int = q[0][2] + a[y][x]
		q = q[1:]
		ans = max(c, ans)

		if x < N-1 {
			q = append(q, []int{y, x + 1, c})
		}
		if y == 0 {
			q = append(q, []int{y + 1, x, c})
		}
	}
	return
}

/*  ----------------------------------------  */

func combination(x, y int) int {
	return permutation(x, y) / permutation(y, y)
}

func permutation(x, y int) int {
	var ans int = 1
	for i := x - y; 0 < i; i-- {
		ans *= i
	}
	return ans
}

func max(x ...int) int {
	var res int = x[0]
	for i := 1; i < len(x); i++ {
		res = int(math.Max(float64(x[i]), float64(res)))
	}
	return res
}

func min(x ...int) int {
	var res int = x[0]
	for i := 1; i < len(x); i++ {
		res = int(math.Min(float64(x[i]), float64(res)))
	}
	return res
}
func pow(x, y int) int { return int(math.Pow(float64(x), float64(y))) }
func abs(x int) int    { return int(math.Abs(float64(x))) }
func floor(x int) int  { return int(math.Floor(float64(x))) }

type XY struct {
	x int
	y int
}
type SortBy []XY

func (a SortBy) Len() int      { return len(a) }
func (a SortBy) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a SortBy) Less(i, j int) bool {
	if a[i].x == a[j].x {
		return a[i].y > a[j].y
	}
	return a[i].x > a[j].x
}


Measured memory_bytes: 1024
using System;
 
 
namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            // get a integer
            //string a = Console.ReadLine();
            // get two integers separated with half-width break
            string[] input = Console.ReadLine().Split(' ');
 
            string b = input[0];
            string c = input[1];
 
            //case : both honest or dishonest
            if (b.Equals(c))
            {
                //output
                Console.WriteLine("H");
            }
            else
            {
                //output
                Console.WriteLine("D");
            }
        }
    }
}

Measured memory_bytes: 11092
#include<iostream>
#include<algorithm>
using namespace std;
int main (void)
{
  int a,b,ans;
  cin>>a>>b;
  ans=0;
  ans=ans+max(a,b);
  ans+=max(max(a-1,b-1),min(a,b));
  cout<<ans<<endl;
}
 

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

using namespace std;

typedef long long ll;
const ll INF=1e18;

typedef pair<ll,ll> P;

int N,K;
ll ans;
ll a[200005],s[200005];
P b[200005];

int bit[(1<<18)+1];

ll sum(int i){
  ll ret=0;
  while(i){
    ret+=bit[i];
    i-=(i&-i);
  }
  return ret;
}

void add(int i,int x){
  while(i<(1<<18)){
    bit[i]+=x;
    i+=(i&-i);
  }
}

int main() {

cin.tie(0);
ios::sync_with_stdio(false);

cin>>N>>K;

for(int i=1; i<=N; i++){
  cin>>a[i]; 
  a[i]-=K;
}

for(int i=1; i<=N; i++){
  s[i]=a[i]+s[i-1];
  if(s[i]>=0) ans++;
}

for(int i=1; i<=N; i++){
  b[i].first=s[i];
  b[i].second=i;
}

sort(b+1,b+N+1);

int j=0; ll x=-INF;

for(int i=1; i<=N; i++){
  if(b[i].first>x){
    j++; 
    x=b[i].first;
  }
    b[i].first=j;
}

for(int i=1; i<=N; i++){
  s[b[i].second]=b[i].first;
}

for(int i=1; i<=N; i++){
  ans+=sum(s[i]);
  add(s[i],1);
}

cout<<ans<<endl;

}


Measured memory_bytes: 7296
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <array>
#include <vector>

using namespace std;

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

	vector<int> vs( n + m );
	for ( int i = 0; i < n + m; i++ ) {
	  int val;
	  cin >> val;
	  vs[ i ] = val;
	}
	sort( vs.begin(), vs.end() );
	int max_range = 0;
	int before = 0;
	for ( const int val : vs ) {
	  max_range = max( max_range, val - before );
	  before = val;
	}
	cout << max_range << endl;
  }  
}

Measured memory_bytes: 1288
n, m = map(int, input().split())
ps = []
P = []
S = []
for i in range(m):
  a = list(input().split())
  d = int(a[0])
  t = [d, a[1]]
  ps.append(t)
  P.append(d)
  S.append(t[1])
ac = 0
penalty = 0
ans = [0]*100000
for j in range(m):
  if ans[P[j]] <= 0:
    ans[P[j]] -= 1
  if S[j] == 'AC' and ans[P[j]]<0:
    ans[P[j]] *= -1
    ac += 1
for a in ans:
  if a >0:
    penalty += a-1
print(ac, penalty)

Measured memory_bytes: 24324
import sys
read = sys.stdin.buffer.read
readlines = sys.stdin.buffer.readlines
input = sys.stdin.buffer.readline
N = int(input())
X = [tuple(map(int, line.split())) for line in sys.stdin.buffer.readlines()]


def d(x, y, u, v):
    return (x-u)**2+(y-v)**2


def check(x, y):
    r = 0
    nx = ny = 0
    for u, v in X:
        z = d(x, y, u, v)
        if z > r:
            r = z
            nx, ny = u, v
    return nx, ny


eps = 10**-8
alpha = 1
x = 500
y = 500
while True:
    nx, ny = check(x, y)
    if d(nx, ny, x, y)**0.5 < eps:
        break
    x, y = x+(nx-x)*alpha, y+(ny-y)*alpha
    alpha *= 0.999
    if alpha < eps:
        break

print(d(*check(x, y), x, y)**0.5)


Measured memory_bytes: 74596
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const ll maxn=2e5+1;
const ll INF=4e18;
void solve()
{
	ll N;
	cin>>N;
	ll a[maxn];
	for(ll i=0;i<N;i++)
	{
		cin>>a[i];
	}
	ll k=1,c=0;
	for(ll i=0;i<N;i++)
	{
		if(a[i]==k)
		{
			k++;
		}
		else
		{
			c++;
		}
	}
	if(c==N) cout<<-1<<"\n";
	else cout<<c<<"\n";
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll T=1,p=0;
	//cin>>T;
	do
	{
		solve();
		p++;
	}while(p<T);
	return 0;
}



Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i, b, n) for (long i = b; i < (n); ++i)

using namespace std;

void solve(long X) {
  rep (i, X, 1E6) {
    bool prime = true;
    rep (j, 2, i) {
      if (i % j == 0) {
	prime = false;
	break;
      }
    }
    if (!prime)
      continue;
    // Prime !!!
    cout << i << endl;
    return;
  }
}

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

  long X;
  cin >> X;
  solve(X);
  return 0;
}


Measured memory_bytes: 256
import java.util.*;
 
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    long N = sc.nextLong();
    long[] input = new long[5];
    long min = 1000000000000000L;
    for (int i = 0; i < 5; i++){
        long next = sc.nextLong();
        if (min > next){
            min = next;
        }
    }
    long minTimes = 0;
    if (N % min == 0){
        minTimes = (N / min) + 4;
    } else {
        minTimes = (N / min + 1) + 4;
    }
    System.out.println(minTimes);

  }
  
}


Measured memory_bytes: 21972
# -*- coding: utf-8 -*-

#-------
# Initialize

N,T = map(int, input().split())
t = list(map(int, input().split()))
ans = T

#-------
# Do
for i in range(len(t)-1):
    ans += min(T, t[i+1] - t[i])

#-------
# Output
print(ans)


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

int main() {
    int N;
    cin >> N;
    vector<int>as(N);
    for(int i=0; i<N; i++)cin >> as[i];
    sort(all(as));
    reverse(all(as));
    int alice,bob;
    alice = bob = 0;
    for (int i=0; i<N; i++){
        if (i%2 ==0)alice += as[i];
        else bob += as[i];
    }
    cout << alice - bob << endl;
}

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

int main( ){
    int n,a[60];
    long long ans;
    ans = 0;
    
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++)
            ans += a[i]*a[j];
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
	int card[4][14]={0};
	int i,n,c,j;
	char x;
	char a[]={'S','H','C','D'};
	cin>>n;
	for(i=0;i<n;i++){
		cin>>x>>c;
		if(x=='S'){
			card[0][c]=1;
		}
		else if(x=='H'){
			card[1][c]=1;
		}
		else if(x=='C'){
			card[2][c]=1;
		}
		else{
			card[3][c]=1;
		}
	}
	for(i=0;i<4;i++){
		for(j=1;j<14;j++){
			if(card[i][j]==0){
				cout<<a[i]<<" "<<j<<endl;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 3072
import java.util.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main {

	int INF = 1 << 28;
	int n,m;
	int p[];
	int[][] map;
	void run() {
		Scanner sc = new Scanner(System.in);
		for(;;) {
			n = sc.nextInt();
			m = sc.nextInt();
			map = new int[n][n];
			p = new int[3];
			for(int i=0;i<3;i++) p[i] = sc.nextInt();
			if( (n|m|p[0]|p[1]|p[2]) == 0 ) break;
			for(int[] a: map) fill(a, INF);
			for(int i=0;i<n;i++) map[i][i] = 0;
			for(int i=0;i<m;i++) {
				int a = sc.nextInt()-1;
				int b = sc.nextInt()-1;
				int c = sc.nextInt();
				map[a][b] = c;
			}
			for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) {
				map[i][j] = min(map[i][j], map[i][k] + map[k][j]);
			}
			int min = INF;
			for(int i=0;i<n;i++) {
				int sum = map[p[0]-1][i];
				for(int j=1;j<3;j++) {
					sum += map[i][p[j]-1];
				}
				min = min(min, sum);
			}
			System.out.println(min);
		}
	}

	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 13000
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        if (x == 3 || x == 5 || x == 7) {
            System.out.println("YES");
        }else{
            System.out.println("NO");
        }
        sc.close();
    }
}


Measured memory_bytes: 23124
#include <bits/stdc++.h>
using namespace std;
void init_ios() {ios_base::sync_with_stdio(false); cin.tie(nullptr);}

int N, K;
vector<int> G[2000];

int main() {
	scanf("%d%d", &N, &K);
	for (int i = 0, A,B; i < N-1; ++i) {
		scanf("%d%d", &A, &B);
		--A, --B;
		G[A].push_back(B);
		G[B].push_back(A);
	}

	int res = 1<<30;

	if (K%2) {
		vector<vector<bool>> chosen(N, vector<bool>(N, 0));
		for (int i = 0; i < N; ++i) {
			for (auto& j : G[i]) if (!chosen[i][j]) {
				chosen[i][j] = chosen[j][i] = 1;
				vector<int> checked(N, 0);
				checked[i] = checked[j] = 1;
				queue<pair<int, int>> q;
				q.emplace(i, 0), q.emplace(j, 0);
				while (q.size()) {
					auto p = q.front(); q.pop();
					if (p.second < K/2) for (auto& d : G[p.first]) if (!checked[d]) {
						checked[d] = 1;
						q.emplace(d, p.second+1);
					}
				}
				res = min(res, N-accumulate(checked.begin(), checked.end(), 0));
			}
		}
	} else {
		for (int i = 0; i < N; ++i) {
			vector<int> checked(N, 0);
			checked[i] = 1;
			queue<pair<int, int>> q;
			q.emplace(i, 0);
			while (q.size()) {
				auto p = q.front(); q.pop();
				if (p.second < K/2) for (auto& d : G[p.first]) if (!checked[d]) {
					checked[d] = 1;
					q.emplace(d, p.second+1);
				}
			}
			res = min(res, N-accumulate(checked.begin(), checked.end(), 0));
		}
	}

	printf("%d\n", res);

	return 0;
}


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

int main(){
   long int A,B,K;
   cin>>A>>B>>K;
  
   if(A>=K){
      cout<<A-K<<" "<<B<<endl;
   }
   else if(A+B>=K){
      cout<<0<<" "<<A+B-K<<endl;
   }
   else{
      cout<<0<<" "<<0<<endl;
   }
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
	int N; cin >> N;
	int sum = 0;
	int i = 0;
	while (sum < N) {
		sum += ++i;
	}
	while (N > 0) {
		cout << min(N, i) << endl;
		N -= min(N, i);
		i--;
	}


    return 0;
}


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

using namespace std;
typedef long long ll;
typedef vector<ll> vl ;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;

#define rep(i,N) for(int i=0; i < (int)N; i++)
#define all(v) (v).begin(),(v).end()

const int INF = 100000002;

struct UnionFind{
	vector<int> par;
	vector<int> rank;
	UnionFind(int n) : par(n), rank(n){
		for(int i = 0; i < n; i++){
			par[i] = i;
			rank[i] = 0;
		}
	}

	int find(int x){
		if(par[x] == x){
			return x;
		}else{
			return par[x] = find(par[x]);
		}
	}

	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if (x == y) return;
		if(rank[x] < rank[y]){
			par[x] = y;
		} else {
			par[y] = x;
			if(rank[x] == rank[y]) rank[x] ++;
		}
	}

	bool same(int x, int y){
		return find(x) == find(y);
	}	
};

int main(){
	int n, m; cin >> n >> m;
	auto u = UnionFind(n);
	vi p(n);
	rep(i,n){
		cin >> p[i];
		p[i] --;	
	} 
	rep(i,m){
		int x, y; cin >> x >> y;
		u.unite(p[x-1], p[y-1]);
	}
	
	int ans = 0;
	rep(i,n){
		if(u.same(p[i], i) || p[i]==i) ans ++;
	}
	cout << ans << endl;
}

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

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using WGraph = vector<vector<pair<int, ll>>>;

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

constexpr int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
constexpr int INF = 1e9;
constexpr int MOD = 1e9 + 7;
constexpr long long LINF = 1e18;
constexpr double EPS = 1e-10;
constexpr double PI = M_PI;

void solve() {
    string s;
    cin >> s;

    int N = (int)s.size();
    int ope;
    int cntF = count(s.begin(), s.end(), s.front()), cntB = count(s.begin(), s.end(), s.back());
    if (s.front() == s.back()) ope = N - (cntF * 2 - 1);
    else ope = N - 2 * max(cntF, cntB);
    if (ope%2 == 0) cout << "Second" << '\n';
    else cout << "First" << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    solve();

    return 0;
}


Measured memory_bytes: 3772
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n;
  cin >> n;
  char vec[n];
  for (int i = 0 ; i < n; i++){
  cin >> vec[i];
  }
  int count = 0;
  for (int i = 0 ; i < n; i++){
  if (vec[i] == 'Y'){
  count +=1;
  }
  }
  if(count >=1){
  cout << "Four";
  }else{
  cout << "Three";
  }
}


Measured memory_bytes: 256
import sys

input = sys.stdin.readline
N, Q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(N-1)]
px = [list(map(int, input().split())) for _ in range(Q)]
g = [[] for _ in range(N)]
for a, b in ab:
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)

children = [[] for _ in range(N)]
parent = [-1]*N
q = [0]
while len(q) > 0:
    v = q.pop()
    for u in g[v]:
        if u != parent[v]:
            parent[u] = v
            children[v].append(u)
            q.append(u)

counter = [0]*N
for p, x in px:
    counter[p - 1] += x

ans = [0]*N
q = [(0, 0)]
while len(q) > 0:
    v, c = q.pop()
    ans[v] = c + counter[v]
    for u in children[v]:
        q.append((u, ans[v]))
print(' '.join(map(str, ans)))


Measured memory_bytes: 206668
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int INF = 1e9;
int MOD = 1e9+7;
main(){
    int N,A[300][300];
    ll sum = 0;
    cin >> N;
    for(int i = 0;i < N;i++){
        for(int j = 0;j < N;j++){
            cin >> A[i][j];
            if(i < j)sum += A[i][j];
        }
    }
    bool flag[300][300];
    for(int i = 0;i < N;i++){
        for(int j = 0;j < N;j++){
            for(int k = 0;k < N;k++){
                if(i == j || j == k || k == i)continue;
                if(j > k)continue;                
                if(A[j][k] > A[j][i] + A[i][k]){
                    cout << -1 << endl;
                    return 0;
                }
                if(!flag[j][k] && A[j][k] == A[j][i] + A[i][k]){
                    sum -= A[j][k];
                    flag[j][k] = 1;
                }
            }
        }
    }    cout << sum << endl;
}   

Measured memory_bytes: 640
n,d=map(int,input().split())
li=[list(map(int, input().split())) for _ in range(n)]
res=0
import math
for i in range(n):
    for j in range(i+1,n):
        dis2=0
        for k in range(d):
          dis2+=(li[i][k]-li[j][k])**2
        dis=dis2**(1/2)
        if dis%1==0:res+=1
print(res)

Measured memory_bytes: 9364
#include <random>
#include <vector>
#include <iostream>
using namespace std;

int n;

#if 1
char query(int m) {
    cout << "?";
    for (int i = 0; i < n; i++) cout << ' ' << m + i;
    cout << endl;
    string s; cin >> s;
    return s[0];
}

char query(vector<int> &q) {
    cout << "?";
    for (int x : q) cout << ' ' << x;
    cout << endl;
    string s; cin >> s;
    return s[0];
}

#else

string ans;
int query_count = 0;

char query(int m) {
    query_count++;
    if (query_count > 210)
        cerr << "ERROR: QUERY LIMIT EXCEEDED" << endl;
    if (ans.empty()) {
        ans.resize(2*n, 'B');
        for (int i = 0; i < n; i++) ans[i] = 'R';
        mt19937 mt;
        for (int i = ans.size() - 1; i >= 1; i--) {
            uniform_int_distribution<int> dist(0, i-1);
            int j = dist(mt);
            swap(ans[i], ans[j]);
        }
        cerr << "generated answer: " << ans << endl;
    }
    int r = 0, b = 0;
    for (int i = 0; i < n; i++)
        if (ans[m+i-1] == 'R') r++; else b++;

    char ret = r > b ? 'R' : 'B';

    cerr << "?";
    for (int i = 0; i < n; i++) cerr << ' ' << m + i;
    cerr << endl;
    cerr << "returning " << ret << endl;

    return ret;
}

char query(vector<int> &q) {
    query_count++;
    if (query_count > 210)
        cerr << "ERROR: QUERY LIMIT EXCEEDED" << endl;
    if (ans.empty()) {
        ans.resize(2*n, 'B');
        for (int i = 0; i < n; i++) ans[i] = 'R';
    }
    int r = 0, b = 0;
    for (int x : q) if (ans[x-1] == 'R') r++; else b++;

    char ret = r > b ? 'R' : 'B';

    cerr << "?";
    for (int x : q) cerr << ' ' << x;
    cerr << endl;
    cerr << "returning " << ret << endl;

    return ret;
}
#endif

int main() {
    cin >> n;
    char ans[2*n+1];
    int lb = 1, ub = n+1;
    char L = query(1), R = query(n+1);
    while (ub - lb > 1) {
        int m = (lb + ub) / 2;
        char r = query(m);
        if (r == L) lb = m;
        else ub = m;
    }
    vector<int> q_in, q_out;
    for (int i = 1; i <= 2*n; i++)
        if (lb < i && i < lb + n) q_in.push_back(i);
        else if (i < lb || lb + n < i) q_out.push_back(i);
    ans[lb] = L; ans [lb + n] = R;
    cerr << q_in.size() << " " << q_out.size() << " size" << endl;
    q_in.push_back(-1);
    q_out.push_back(-1);
    for (int i = 1; i <= 2*n; i++) {
        if (i < lb || lb + n < i) {
            q_in.back() = i;
            ans[i] = query(q_in);
        } else if (lb < i && i < lb + n) {
            q_out.back() = i;
            ans[i] = query(q_out);
        }
    }
    cout << "! ";
    for (int i = 1; i <= 2*n; i++) cout << ans[i];
    cout << endl;
}


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

int main(){
  string s; cin>>s;
  if(s.size()<8){
    cout<<"YES"<<endl;
    return 0;
  }
  int win=0;
  for(int i=0;i<s.size();i++){
    if(s[i]=='o') win++;
  }
  if(win+(15-s.size())<8){
    cout<<"NO"<<endl;
  }else{
    cout<<"YES"<<endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define FORR(I,A,B) for(int I = ((B)-1); I >= (A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd(ll a,ll b){if(a<b)swap(a,b);if(a%b==0)return b;return gcd(b,a%b);}
ll lcm(ll a,ll b){ll c=gcd(a,b);return ((a/c)*(b/c)*c);}//saisyo kobaisu
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=1e18+7;
const ll MOD=1e9+7;
#define pri(a) cout << (a) << endl

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	//ifstream in("input.txt");
	//cin.rdbuf(in.rdbuf());
	ll N,M;
	cin >> N >> M;
	vector<ll> x(N),y(N),z(N);
	FOR(i,0,N){
		cin >> x[i] >> y[i] >> z[i];
	}
	ll ans = 0;
	FOR(i,0,2){ // 0+  1-
		FOR(j,0,2){
			FOR(k,0,2){
				ll ansp = 0;
				priority_queue<ll> q;
				FOR(l,0,N){
					ll inq = 0;
					if(i==0)inq += x[l];
					else inq -= x[l];
					if(j==0)inq += y[l];
					else inq -= y[l];
					if(k==0)inq += z[l];
					else inq -= z[l];
					q.push(inq);
				}
				FOR(i,0,M){
					ansp += q.top();
					q.pop();
				}
				ans = max(ans,ansp);
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    resolve(System.in, System.out);
  }

  static int MAX_INDEX = 200000;

  static void resolve(InputStream is, PrintStream pw) {
    Scanner sc = new Scanner(is);
    int n = Integer.parseInt(sc.next());
    int k = Integer.parseInt(sc.next());
    int c = Integer.parseInt(sc.next());
    String s = sc.next();
    boolean workable[] = new boolean[n];
    for (int i = 0; i < n; i++) {
      workable[i] = s.charAt(i) == 'o';
    }
    int[] leftGreedyWorkingDay = new int[MAX_INDEX];
    int[] rightGreedyWorkingDay = new int[MAX_INDEX];
    {
      // left greedy
      int restDays = MAX_INDEX;
      int workingCount = 0;
      for (int i = 0; i < n; i++) {
        if (workable[i] && restDays >= c) {
          workingCount++;
          leftGreedyWorkingDay[i] = workingCount;
          restDays = 0;
        } else {
          restDays++;
        }
      }
    }
    {
      // right greedy
      int restDays = MAX_INDEX;
      int workingCount = k;
      for (int i = n - 1; i >= 0; i--) {
        if (workable[i] && restDays >= c) {
          rightGreedyWorkingDay[i] = workingCount;
          workingCount--;
          restDays = 0;
        } else {
          restDays++;
        }
      }
    }
    for (int i = 0; i < n; i++) {
      if (leftGreedyWorkingDay[i] == rightGreedyWorkingDay[i] && leftGreedyWorkingDay[i] != 0) {
        pw.println(i + 1);
      }
    }
    pw.println();
  }
}


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

int main() {
    int n[3];
    for(int i = 0;i<3;i++) cin >> n[i];
    sort(n,n+3,greater<int>());
    if(n[0] == 7 && n[1]== 5 && n[2] == 5) cout << "YES" << endl;
    else cout << "NO" << endl;
}

Measured memory_bytes: 3520
from itertools import accumulate
from math import ceil

N,H=map(int,input().split())
a=[0 for i in range(0,N)]
b=[0 for i in range(0,N)]
for i in range(0,N):
    a[i],b[i]=map(int,input().split())

m=max(a)
katana1=[]
for i in range(0,N):
    if a[i]==m:
        katana1.append([b[i],i])

katana1.sort()
remove=katana1[0]
katana2=[]
for i in range(0,N):
    if b[i]>m and i!=remove[1]:
        katana2.append(b[i])

katana2.sort(reverse=True)

katana3=list(accumulate(katana2))
if len(katana3)>0:
    if katana3[-1]>=H:
        ans=1
        for i in range(0,len(katana3)):
            if katana3[i]<H:
                ans+=1
            else:
                print(ans)
                break
    else:
        throw=katana3[-1]
        H-=throw
        ans=len(katana3)
        if remove[0]>m:
            H-=remove[0]
            ans+=1
            if 0>=H:
                print(ans)
            else:
                ans+=ceil(H/m)
                print(ans)
        else:
            ans+=ceil(H/m)
            print(ans)
else:
    ans=0
    if remove[0]>m:
        H-=remove[0]
        ans+=1
        if 0>=H:
            print(ans)
        else:
            ans+=ceil(H/m)
            print(ans)
    else:
        ans+=ceil(H/m)
        print(ans)

Measured memory_bytes: 63024
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <queue>
#include <set>
#include <map>
#include <stack>
 
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
 
string S;
ll N,M,ans;

 
 
 
int main(){
    cin >> N;
    M = 100000000000000009;
    for(int i = 0;i<N;i++){
        ll m;
        cin >> m;
        if(M>=m){
            ans++;
            M = m;
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
n,m=map(int,input().split())
a1=[]
a2=[]
a3=[]
a4=[]
a5=[]
a6=[]
a7=[]
a8=[]
for i in range(n):
  a,b,c=map(int,input().split())
  a1.append( a+b+c)
  a2.append(-a+b+c)
  a3.append( a-b+c)
  a4.append( a+b-c)
  a5.append(-a-b+c)
  a6.append(-a+b-c)
  a7.append( a-b-c)
  a8.append(-a-b-c)
a1.sort(reverse=True)
a2.sort(reverse=True)
a3.sort(reverse=True)
a4.sort(reverse=True)
a5.sort(reverse=True)
a6.sort(reverse=True)
a7.sort(reverse=True)
a8.sort(reverse=True)
print(max(sum(a1[:m]),sum(a2[:m]),sum(a3[:m]),sum(a4[:m]),sum(a5[:m]),sum(a6[:m]),sum(a7[:m]),sum(a8[:m])))

Measured memory_bytes: 3316
#include "bits/stdc++.h"
using namespace std;
int main()
{
	int a,b,c,x,i,j,k;
	int count=0;
	scanf("%d %d %d %d",&a,&b,&c,&x);
	for(i=0;i<=a;i++)
	{
		for(j=0;j<=b;j++)
		{
			for(k=0;k<=c;k++)
			{
				if(i*500+j*100+k*50==x)
				{
					count++;
				}
			}
		}
	}
	printf("%d\n",count);
	return 0;
}

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

typedef long long llong;
// -2.1e-9 <= int <= 2.1e9

int main()
{
    pair<string, int> S, T;
    cin >> S.first >> T.first;
    cin >> S.second >> T.second;
    string U;
    cin >> U;
    if (U == S.first)
        S.second--;
    else if (U == T.first)
        T.second--;
    cout << S.second << ' ' << T.second << endl;
}


Measured memory_bytes: 256