akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define bug1( x ) {cerr << (#x) <<"="<< x << endl;}
#define bug2( x , y ) {cerr << (#x) <<"="<< (x) << "    " << (#y) << "="<< (y) << endl;}
#define bug3( x , y , z ) {cerr << (#x) <<"="<<(x) << "    " << (#y) <<"="<< (y) << "    " << (#z) <<"="<< (z) << endl;}
#define bug4( x , y , z , w) {cerr << (#x) <<"="<<(x) << "    " << (#y) <<"="<< (y) << "    " << (#z) <<"="<< (z) << "    " << (#w) <<"="<< w << endl;}
#define bug5( x , y , z , w ,p) {cerr << (#x) <<"="<<(x) << "    " << (#y) <<"="<< (y) << "    " << (#z) <<"="<< (z) << "    " << (#w) <<"="<< w << "    " << (#p) <<"="<< p << endl;}
#define bug6( x , y , z , w ,p , q) {cerr << (#x) <<"="<<(x) << "    " << (#y) <<"="<< (y) << "    " << (#z) <<"="<< (z) << "    " << (#w) <<"="<< w << "    " << (#p) <<"="<< p << "    " << (#q) <<"="<< q << endl;}
#define bugn( x , n ) {cerr << (#x) <<":";for(int i=0;i<n;i++)cerr << x[i] <<"  "; cerr << endl;}
#define bugnm( x , n , m ) {cerr << (#x)<<endl;for(int i=0;i<n;i++){cerr << "Row #" << i<< ":";for(int j=0;j<m;j++)cerr << x[i][j] << "   ";cerr << endl;}}
typedef long long ll;
typedef long double ld;
using namespace std;

const int maxn = 1e5+10;
int a[maxn],sum[41][2],dp[41][2],n,k;
int solve(int i,int bnd){
	if( i == -1 )return 0;
	int &ans = dp[i][bnd];
	if( ans != -1 )return ans;
	ans = 0;
	int cur = k >> i & 1;
	if( bnd ){
		for(int d=0;d<cur;d++){
			ans=max(ans,sum[i][d]+solve(i-1,0));
		}
		ans=max(ans,sum[i][cur]+solve(i-1,1));
	}else{
		for(int d=0;d<2;d++){
			ans=max(ans,sum[i][d]+solve(i-1,0));
		}
	}
	return ans;
}
int32_t main(){
	IOS
	cin>>n>>k;
	for(int i=0;i<n;i++){
		cin>>a[i];
	}
	memset(sum,0,sizeof(sum));
	for(int bit=0;bit<41;bit++){
		for(int i=0;i<n;i++){
			int b = a[i] >> bit & 1;
			sum[bit][b^1]+=1LL<<bit;
		}
	}
	memset(dp,-1,sizeof(dp));
	cout<<solve(40,1);
 }
/*
 * long long or int?
 * index out of bound? 
 * Tested on own test case?corner?
 * Make more general solution.
 * Read Read Read Read ....
 */


Measured memory_bytes: 4416
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1<<30;
const ll LINF = 1LL<<60;

#define int long long

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

    int n, k; cin >> n >> k;
    vector<int> a(n+1); for (int i = 0; i < n; i++) cin >> a[i+1];

    vector<int> cyc; cyc.push_back(1);
    vector<int> lastind(n+1, -1);
    lastind[1] = 0;
    
    int x = 1;
    while (true) {
        x = a[x];
        cyc.push_back(x);
        if (cyc.size()-1 == k) {
            cout << cyc.back() << endl;
            return 0;
        }
        if (lastind[x] != -1) {
            vector<int> path(cyc.begin()+lastind[x]+1, cyc.end());
            k -= lastind[x];
            int ind = k%path.size() - 1;
            if (ind < 0) ind = path.size()-1;
            cout << path[ind] << endl;
            return 0;
        }
        lastind[x] = cyc.size()-1;
    }

    return 0;
}

Measured memory_bytes: 8460
n=int(input())
s=[]
for i in range(n):
    x=list(input())
    x=sorted(x)
    s.append("".join(x))
s=sorted(s)
m=1
ans=0
for i in range(n-1):
    if s[i]==s[i+1]:
        m+=1
    else:
        ans+=m*(m-1)//2
        m=1
ans+=m*(m-1)//2
print(ans)
    


Measured memory_bytes: 17112
from math import sin, cos, radians, sqrt
a, b, C = [float(i) for i in input().split(" ")]
S = a * b * sin(radians(C)) / 2
L = a + b + sqrt( a**2 + b**2 - 2*a*b*( cos(radians(C)) ) )
h = 2 * S / a

print(S,L,h,sep = "\n")

Measured memory_bytes: 7812
#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define Y cout<<"YES"<<endl
#define N cout<<"NO"<<endl
int main()
{

    ll x,i,j;

    cin>>x;

    if(x==2){

        cout<<x<<endl;

        return 0;
    }

    if(x%2==0)x++;

    for(i=x;;i+=2){

        ll f=0;

        for(j=3;j*j<=x;j+=2){

            if(i%j==0){

                f=1;
                break;
            }
        }

        if(f==0){

            cout<<i<<endl;

            return 0;
        }
    }


}




Measured memory_bytes: 256
def main():
    N = int(input())
    A = input().split()
    B = A.copy()
    
    A = BubbleSort(A, N)
    print(*A)
    print('Stable')
    B = SelectionSort(B, N)
    print(*B)
    if A == B:
        print('Stable')
    else:
        print('Not stable')

def BubbleSort(A, N):
    count = 0
    for i in range(N):
        for j in range(N-1,i,-1):
            if A[j][1] < A[j-1][1]:
                A[j], A[j-1] = A[j-1], A[j]
                count += 1
    return A

def SelectionSort(A, N):
    count = 0
    
    for i in range(N):
        mini = i
        for j in range(i,N):
            if A[j][1] < A[mini][1]:
                mini = j
        if A[i][1] > A[mini][1]:
            A[i], A[mini] = A[mini], A[i]
            count += 1
    return A

main()



Measured memory_bytes: 5616
import itertools
n = int(input())
L = [[]for i in range(5)]
for i in range(n):
    s = str(input())
    if s[0] == "M":
        L[0].append(s)
    elif s[0] == "A":
        L[1].append(s)
    elif s[0] == "R":
        L[2].append(s)
    elif s[0] == "C":
        L[3].append(s)
    elif s[0] == "H":
        L[4].append(s)
L = [ i for i in L if len(i) > 0]
ans = 0
for i in itertools.combinations(L, 3):
    ans += len(i[0])*len(i[1])*len(i[2])
print(ans)

Measured memory_bytes: 10100
#include<stdio.h>

int main(){
  int N,num[100];
  int i,j,res,min,count=0;

  scanf("%d",&N);
  
  
  for(i=0;i<N;i++){
    scanf("%d",&num[i]);
  }

  for(i=0;i<=N-1;i++){
    min=i;
    for(j=i;j<=N-1;j++){
      if(num[j]<num[min]){
	min=j;
      }
    }
      
      if(num[i]!=num[min]){ 
	res=num[i];
	num[i]=num[min];
	num[min]=res;
	count++;
      }
    }

  for(i=0;i<N;i++){
    printf("%d",num[i]);
    if(i!=N-1) printf(" ");
    else printf("\n");
  }

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

  return 0;
}

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

typedef long long ll;

int main() {
    string s, t = "";
    cin >> s;
    rep(i, s.size()) {
        if (s.substr(i, 2) == "BC") {
            t.push_back('D');
            i++;
        } else {
            t.push_back(s[i]);
        }
    }
    //cout << t << endl;
    ll ans = 0, a = 0;
    rep(i, t.size()) {
        if (t[i] == 'A') a++;
        else if (t[i] == 'D') ans += a;
        else a = 0;
    }
    cout << ans << endl;
}

Measured memory_bytes: 776
s = input()
c1, c2 = s[0], s[-1]
cnt1, cnt2 = 0, 0
for i in range(1, len(s)):
  if c1!=s[i]:
    cnt1 += 1
    c1 = s[i]
for i in range(len(s)-2, -1, -1):
  if c2!=s[i]:
    cnt2 += 1
    c2 = s[i]
print(min(cnt1, cnt2))

Measured memory_bytes: 3188
#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : June 30, 2020
##################################################### SOURCE START #####################################################

N = int(input().strip())
As = list(map(int, input().strip().split()))

count = 0

while True:

    if all(a % 2 == 0 for a in As):
        count += 1
        As = [a // 2 for a in As]
    else:
        break

print(count)

##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker


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

#define PI 3.1415926535897932
#define MOD 1000000007
#define INF 2e9

#define REP(i, n) for(int i = 0; i < (n); i++)
#define REP1(i, n) for(int i = 1; i <= (n); i++)
#define FOR(i, start, end) for(int i = (start); i < (end); i++)
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef vector<bool> vb;

ll fact(ll n)
{
    ll res = 1;
    for(ll i = n; i > 1; i--)
    {
        res *= i;
        res %= MOD;
    }
    return res;
}

void solve()
{
    int N, M; cin >> N >> M;
    ll ans = 0;
    if(abs(N-M) >= 2) 
    {
        cout << 0 << endl;
        return;
    }
    else if(abs(N-M) == 1)
    {
        ans += fact(N) * fact(M);
        ans %= MOD;
    }
    else
    {
        ans =+ 2 * (fact(N) * fact(M));
        ans %= MOD;
    }
    
    cout << ans << endl;
}

int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define pa pair<int,int>
const int Maxn=1;
const int inf=2147483647;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*f;
}
int main()
{
	int n=read();
	char str[150];
	scanf("%s",str+1);int r=0,b=0;
	for(int i=1;i<=n;i++)
	if(str[i]=='R')r++;
	else b++;
	if(r>b)puts("Yes");
	else puts("No");
}


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

using namespace std;

#define ll long long
#define mx 0
#define mn 1e9
#define v(dt) vector<dt>
#define pr(x, y) pair<x,y>
#define loop(x, s, n) for(int x = s; x < n; ++x)
#define in_arr(n) loop(i,0,n){cin>>a[i];}
#define out_arr(n) loop(i,0,n){cout<<a[i];}

const int N = 1e5 + 7;

inline void boost() {
    cin.tie(0), cout.tie(0), cin.sync_with_stdio(0), cout.sync_with_stdio(0);
}

int main() {
    boost();
    ll a, b;
    cin >> a >> b;
    ll s = 1;
    ll cnt = 0;
    while (s < b) {
        cnt++;
        s = (s-1) + a;
    }
    cout << cnt;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
    #define ll long long
    using namespace std;
     
    int main()
    {
        
        int N, A, B, pos;
        scanf("%d %d %d", &N, &A, &B);
        ll ans = 0;
        int cur = -1;
        while(N--)
        {
            scanf("%d", &pos);
            if(cur == -1)
            {
                cur = pos;
            }
            ans = ans + min((long long)B, 1ll * (pos - cur) * A );
            cur = pos;
        }
        cout<<ans<<endl;
     
        return 0;
    }

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

const int MAXV = 108;
const int MAXCAKE = 6;
const int H = 106;
const int D = 107;

int m, n, k, d, calorie[MAXCAKE];

struct Edge { int to, cost, cakeFlag; };
vector<Edge> G[MAXV];

int dist[1<<MAXCAKE][MAXV];

int toInt(string s) {
	int ret = 0;
	for (int i=0; i<(int)s.size(); ++i) {
		ret = ret * 10 + (s[i] - '0');
	}
	return ret;
}

int makeKey(string s) {
	if (s[0] == 'C') return toInt(s.substr(1)) - 1;
	if (s[0] == 'L') return toInt(s.substr(1)) + 5;
	return (s == "H" ? H : D);
}

void addEdge(string a, string b, int cost) {
	int ak = makeKey(a);
	int bk = makeKey(b);
	if (b[0] == 'C') {
		G[ak].push_back((Edge){bk, cost - calorie[bk], 1 << bk});
	} else {
		G[ak].push_back((Edge){bk, cost, 0});
	}
	if (a[0] == 'C') {
		G[bk].push_back((Edge){ak, cost - calorie[ak], 1 << ak});
	} else {
		G[bk].push_back((Edge){ak, cost, 0});
	}
}

int shortestPath(int from, int to) {
	fill((int*)dist, (int*)(dist + sizeof(dist) / sizeof(*dist)), INT_MAX);
	dist[0][from] = 0;
	queue<pair<int,int> > q;
	q.push(make_pair(from, 0));
	while ( ! q.empty()) {
		int now = q.front().first;
		int flag = q.front().second;
		q.pop();
		for (int i=0; i<(int)G[now].size(); ++i) {
			Edge &e = G[now][i];
			if (flag & e.cakeFlag) continue;
			if (dist[flag][now] + e.cost < dist[flag | e.cakeFlag][e.to]) {
				dist[flag | e.cakeFlag][e.to] = dist[flag][now] + e.cost;
				q.push(make_pair(e.to, flag | e.cakeFlag));
			}
		}
	}
	int ret = INT_MAX;
	for (int i=0; i<(1<<MAXCAKE); ++i) {
		ret = min(ret, dist[i][to]);
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	while (cin >> m >> n >> k >> d, m) {
		fill(G, G+MAXV, vector<Edge>());
		for (int i=0; i<m; ++i) {
			cin >> calorie[i];
		}
		string a, b;
		int cost;
		for (int i=0; i<d; ++i) {
			cin >> a >> b >> cost;
			addEdge(a, b, cost * k);
		}
		cout << shortestPath(H, D) << endl;
	}
	return 0;
}

Measured memory_bytes: 1340
// Solution by ** Abhishek Mittal **
#include<iostream>
#include<fstream>
#include<math.h>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<math.h>

#define FIO ios_base::sync_with_stdio(0);  cin.tie(0);
#define PI 3.14159265358979323846
#define mod 1000000007
#define ll long long
#define vll vector<long long>  

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

// Used to traverse in any STL container with iterators
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)

// Find whether element is present in given container or not
#define present(container, element) (container.find(element) != container.end())

// Finds whether element in present container is present in vector or not
#define cpresent(container, element) (find(all(container),element) != container.end())

using namespace std;

const ll mxlen = 1e6;

// vector<int> adj(mxlen);

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
    #endif
    FIO
    ll n, d;
    ll x, y;
    cin>>n>>d;
    int cnt = 0;
    for(int i=0;i<n;i++){
        cin>>x>>y;
        if(x*x + y*y <= d*d)cnt++;
    }
    cout<<cnt<<endl;
    return 0;
}

Measured memory_bytes: 3220
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(ll i=a;i<=b;i++)
#define repr(i,a,b) for(ll i=a;i>=b:i--)

int main() {
    // your code goes here
    ll n,x[105],ans=1e17;
    cin >> n;
    rep(i,1,n){
        cin >> x[i];
    }
    rep(i,1,100){
        ll memo=0;
        rep(j,1,n){
            memo+=(x[j]-i)*(x[j]-i);
        }
        ans=min(ans,memo);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    if(a<=b&&a<=c)
    {
        if(b<=c)
        {
            printf("%d %d %d\n",a,b,c);
        }
        else
        {
            printf("%d %d %d\n",a,c,b);
        }
    }
    else if(b<=a&&b<=c)
    {
        if(a<=c)
        {
            printf("%d %d %d\n",b,a,c);
        }
        else
        {
            printf("%d %d %d\n",b,c,a);
        }
    }
    else
    {
        if(a<=b)
        {
            printf("%d %d %d\n",c,a,b);
        }
        else
        {
            printf("%d %d %d\n",c,b,a);
        }
    }
    return 0;
}

Measured memory_bytes: 596
import bisect
N=int(input())
A=[int(input()) for _ in range(N)]
color=[]
A=A[::-1]
for a in A:
    i=bisect.bisect_right(color,a)
    if i==len(color):
        color.append(a)
    else:
        color[i]=a
print(len(color))

Measured memory_bytes: 56152
import java.util.*;

class Main{

  public static void main(String args[]){

    Scanner s=new Scanner(System.in);
    int N=s.nextInt();
    int M=s.nextInt();
    int[] height=new int[N];
    int [][] pair=new int[M][2];
    for(int i=0;i<N;i++) height[i]=s.nextInt();
    for(int i=0;i<M;i++) for(int j=0;j<2;j++) pair[i][j]=s.nextInt();    
    boolean[] ansBox=new boolean[N];
    for(int i=0;i<N;i++) ansBox[i]=true; 
    
    for(int i=0;i<M;i++){
      if(height[pair[i][0]-1]<=height[pair[i][1]-1]) ansBox[pair[i][0]-1]=false;
      if(height[pair[i][1]-1]<=height[pair[i][0]-1]) ansBox[pair[i][1]-1]=false;
    }
	int ans=0;
    for(int i=0;i<N;i++) if(ansBox[i]==true) ans+=1;

    System.out.println(ans);
  }  
}

Measured memory_bytes: 62760
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<n; ++i)
#define rep1(i, n) for (int i=1; i<=n; ++i)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
constexpr ll  MOD = (1e9+7);
constexpr int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
constexpr int lcm(int a, int b) { return a / gcd(a, b) * b; }

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
ll factorial(ll n, ll m=2) {
    // calculate n!
    m = max(2LL, m);
    ll rtn = 1;
    for (ll i=m; i<=n; i++) {
        rtn = (rtn * i) % MOD;
    }
    return rtn;
}
ll modinv(ll a, ll m) {
    ll b = m, u = 1, v = 0;
    while (b) {
        ll t = a / b;
        a -= t * b;
        swap(a, b);
        u -= t * v;
        swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}
ll modpow(ll a, ll n) {
    ll res = 1;
    while (n > 0) {
        if (n & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        n >>= 1;
    }
    return res;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    string s; cin >> s;
    string ans = "yes";
    
    for (char c = 'a'; c <= 'z'; c++)  {
        int cnt = 0;
        for (int i = 0; i < s.size(); i++) {
        if (s.at(i) == c) cnt++;
        }
        if (cnt > 1) ans = "no";
    }
    cout << ans << endl;
    return 0;
}

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

//
#define int long long
#define pb(x) push_back(x)
#define m0(x) memset((x), 0, sizeof(x))
#define mm(x) memset((x), -1, sizeof(x))

//container
#define ALL(x) (x).begin(), (x).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(i, c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define UNIQUE(v) (v).erase(unique((v).begin(), (v).end()), (v).end());
#define PERM(c) \
  sort(ALL(c)); \
  for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))

// debug
#define GET_VAR_NAME(variable) #variable
#define test(x) cout << GET_VAR_NAME(x) << " = " << x << endl;

// bit_macro
#define bit(n) (1LL << (n))
#define bitset(a, b) (a) |= (1 << (b))
#define bitunset(a, b) (a) |= ~(1 << (b))
#define bitcheck(a, b) ((((a) >> (b)) & 1) == 1)
#define bitcount(a) __builtin_popcountll((a))

//typedef
typedef long long lint;
typedef complex<long double> Complex;
typedef pair<int, int> P;
typedef tuple<int, int, int> TP;
typedef vector<int> vec;
typedef vector<vec> mat;

//constant
const int INF = (int)1e18;
const int MOD = (int)1e9 + 7;
const double EPS = (double)1e-10;
const int dx[] = {-1, 0, 0, 1, 0, -1, -1, 1, 1};
const int dy[] = {0, -1, 1, 0, 0, 1, -1, 1, -1};

//
template <typename T>
void chmax(T &a, T b) { a = max(a, b); }
template <typename T>
void chmin(T &a, T b) { a = min(a, b); }
//
inline int toInt(string s) {
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
template <class T>
inline string toString(T x) {
  ostringstream sout;
  sout << x;
  return sout.str();
}

//
struct Accelerate_Cin {
  Accelerate_Cin() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);
  };
};

signed main() {
  int a, b;
  cin >> a >> b;
  if (a <= 0 && b >= 0) {
    cout << "Zero" << endl;
    return 0;
  }

  if (a > 0) {
    cout << "Positive" << endl;
    return 0;
  }

  if ((abs(a - b) + 1) % 2 == 0) {
    cout << "Positive" << endl;
  } else {
    cout << "Negative" << endl;
  }

  return 0;
}


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

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP0(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REP1(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)

typedef long long LL;
typedef pair<int, int> pii;

const int INTINF = int(1e9) + 1;
const LL LLINF = LL(1e18) + 1;
#define pow10(n) int(1e##n + n)

// 頂点をインデックスで管理
struct UnionFind
{
    std::vector<int> rank, p, cnt;
    set<int> roots;

    UnionFind(){};
    UnionFind(int size)
    {
        init(size);
    }

    void init(int size)
    {
        rank.resize(size, 0);
        p.resize(size, 0);
        cnt.resize(size, 0);
        for (int i = 0; i < size; i++) makeSet(i);
    }

    void makeSet(int x)
    {
        p[x] = x;
        rank[x] = 0;
        cnt[x] = 1;
        roots.insert(x);
    }

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

    void unite(int x, int y)
    {
        if (same(x, y))
            return;
        link(findSet(x), findSet(y));
    }

    void link(int x, int y)
    {
        if (rank[x] > rank[y])
        {
            p[y] = x;
            roots.erase(y);
            cnt[x] += cnt[y];
        }
        else
        {
            p[x] = y;
            roots.erase(x);
            cnt[y] += cnt[x];
            rank[y] += (rank[x] == rank[y]);
        }
    }

    int findSet(int x)
    {
        if (x != p[x])
        {
            p[x] = findSet(p[x]);
        }
        return p[x];
    }

    int setSize(int x)
    {
        return cnt[findSet(x)];
    }
};

void solve()
{
    LL N, M;
    cin >> N >> M;
    UnionFind uf(N);
    vector<pii> E(M);

    REP0 (i, M)
    {
        cin >> E[i].first >> E[i].second;
        E[i].first--;
        E[i].second--;
    }

    vector<LL> ans;
    LL max_ans = N * (N - 1) / 2;
    LL c = 0;

    for (int i = M - 1; i >= 0; i--)
    {
        ans.push_back(max_ans - c);

        int s = E[i].first, t = E[i].second;
        if (!uf.same(s, t))
        {
            LL s_sz = uf.setSize(s), t_sz = uf.setSize(t);
            c -= s_sz * (s_sz - 1) / 2;
            c -= t_sz * (t_sz - 1) / 2;
            c += (s_sz + t_sz) * (s_sz + t_sz - 1) / 2;
        }

        uf.unite(s, t);
    }

    for (int i = M - 1; i >= 0; i--) cout << ans[i] << endl;
}

int main(int argc, char const *argv[])
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(10);
    solve();
    return 0;
}


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

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

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

  int sum[n]={0};
  for(int i=1;i<n;i++){
    int a;
    cin >> a;
    sum[a-1]++;
  }
  rep(i,n){
    cout << sum[i] << endl;
  }
  return 0;
}

Measured memory_bytes: 4400
#include <stdio.h>
#include <numeric>
#include <time.h>
#include <bitset>
#include <string.h>
#include <stack>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <math.h>
#include <queue>
#include <complex>
#include <functional>
#include <limits.h>
using namespace std ;
typedef long long ll ;
typedef long double ld ;
typedef unsigned long long ull ;
#ifdef _WIN32
#define LLD "%I64d"
#else
#define LLD "%lld"
#endif
#define pi (acos(-1.0))
#define fi first
#define se second
#define SZ(x) ((int)x.size())
#define lson (o<<1),l,mid
#define rson (o<<1|1),mid+1,r
#define MP make_pair
#define sqr(x) ((x)*(x))
#define ALL(v) (v).begin(),(v).end()
#define showtime fprintf(stderr,"time = %.15f\n",clock() / (double)CLOCKS_PER_SEC)
const double eps = 1e-9 ;
const int MOD=(int)1e9+7,BAS=233;
inline int sign(double x){return x<-eps?-1:x>eps;}
inline int clz(int x){return __builtin_clz(x);}
inline int clz(ll x){return __builtin_clzll(x);}
inline int lg2(int x){return !x ? -1 : 31-clz(x);}
inline int lg2(ll x){return !x ? -1 : 63-clz(x);}
int AP (char *s) {
	unsigned hash=0;
	for(int i=0; s[i]; i++){
		if (i & 1) hash ^= (~((hash<<11)^s[i]^(hash>>5)));
		else hash ^= ((hash<<7)^s[i]^(hash>>3));
   } return hash & 0x7FFFFFFF;
}

const int M = 400+5;
const int inf = 0x3f3f3f3f;
int dp[41][M][M];
int a[M], b[M], c[M];
int n;
int ma, mb;

inline void Minx (int &a,int b) {
	if (a>b) a=b;
}

int main () {
	scanf ("%d%d%d", &n,&ma,&mb);
	for (int i=1; i<=n; i++) scanf ("%d%d%d", a+i,b+i,c+i);
	memset (dp, inf , sizeof(dp));
	dp[0][0][0]=0;
	for (int i=1; i<=n; i++) {
		for (int j=0; j<M; j++) {
			for (int z=0; z<M; z++) {
				if (dp[i-1][j][z]!=inf) {
					Minx (dp[i][j+a[i]][z+b[i]], dp[i-1][j][z]+c[i]);
				}
			}
		}
		for (int j=0; j<M; j++) {
			for (int z=0; z<M; z++) {
				Minx (dp[i][j][z], dp[i-1][j][z]);
			}
		}
	}
	int ans = inf;
	for (int i=1; i<=n; i++) {
		for (int j=1; j<M; j++) {
			for (int z=1; z<M; z++) if (j*mb==z*ma) {
				Minx (ans, dp[i][j][z]);
			}
		}
	}
	printf ("%d\n", ans==inf?-1:ans);
	return 0;
}

Measured memory_bytes: 26496
<?php
list($K, $N) = array_map(function ($n) {
    return (int)$n;
}, explode(' ', fgets(STDIN)));

$A = array_map(function ($n) {
    return (int)$n;
}, explode(' ', fgets(STDIN)));

$max = $A[1] - $A[0];

for ($i = 0; $i < $N; $i++) {
    if ($i === $N - 1) {
        $distance = $K - $A[$i] + $A[0];
    } else {
        $distance = $A[$i + 1] - $A[$i];
    }
    if ($distance > $max) {
        $max = $distance;
    }
}

echo $K - $max;

Measured memory_bytes: 27380
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <algorithm>
#include <array>
int main(){
    int N,K;
    int count=0;
    std::cin >> N >> K;
    std::vector<int> COUNT(N),A(N);
    for(int i=0;i<N;i++){
        std::cin >> A[i];
    }
    std::sort(A.begin(),A.end());
    int k=0;
    for(int i=0;i<N;i++){
        COUNT[k]++;
        if(A[i]!=A[i+1]&&i!=N){
            k++;
        }
    }
    int min = 0,i=0;
    std::sort(COUNT.begin(),COUNT.begin()+k);

    while(K<k){
        count+=COUNT[i];
        k--;
        i++;
        
    }
    std::cout << count << std::endl;
}

Measured memory_bytes: 1792
#!/usr/bin/env python3
# n,m = map(int,sys.stdin.readline().split())
# a = tuple(map(int,sys.stdin.readline().split()))
# a = tuple(sys.stdin.readline() for _ in range(n))
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
import sys

#for sparse data
# 05_large 11s->6s
import collections

def solve():
  N,W = map(int,sys.stdin.readline().split())
  vw = tuple(tuple(map(int,sys.stdin.readline().split())) for _ in range(N))
  dp = {}
  dp[0] = 0
  #a = sorted(a,reverse=True)
  for v,w in vw:
    temp = dp.copy()
    for j in list(dp.keys()):
      if j+w <= W and (not j+w in dp or dp[j+w] < dp[j]+v):
        temp[j+w] = dp[j]+v
        #dp = {**dp,**temp}
    dp = temp
    #print(w,v,dp)
  print(max(dp.values()))

#weight dp ()
def solve1():
  N,W = map(int,sys.stdin.readline().split())
  vw = tuple(tuple(map(int,sys.stdin.readline().split())) for _ in range(N))
  V = sum(v for v,_ in vw)
  dp = [W+1]*(V+1)
  dp[0] = 0
  for v,w in vw:
    for c_v in range(V+1)[::-1]:
      if 0 <= c_v-v: #select
        dp[c_v] = min(dp[c_v],dp[c_v-v]+w)
    #print(dp)
  for c_v in range(V+1)[::-1]:
    if dp[c_v] <= W:
      return c_v
  return V
print(solve1())


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

using namespace std;

int main() {
	int A, B, C;
	cin >> A >> B >> C;
	if (((A+B+C)==17)&&(5 == min(A,min(B,C)))&&(7 == max(A,max(B,C)))) {
		cout << "YES"<<endl;
	}
	else {
		cout << "NO" << endl;
	}
	return 0;
}


Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define all(i) i.begin(), i.end()
template<class T, class U> bool cmax(T& a, U b) { if (a<b) {a = b; return true;} else return false; }
template<class T, class U> bool cmin(T& a, U b) { if (a>b) {a = b; return true;} else return false; }

// http://noshi91.hatenablog.com/entry/2019/03/31/174006
template <uint_fast64_t Mod = 1'000'000'007>
struct modint {
  using u64 = uint_fast64_t;

  u64 n;

  modint(const u64 x = 0) : n(x % Mod) {}
  modint operator+(const modint r) const { return modint(*this) += r; }
  modint operator-(const modint r) const { return modint(*this) -= r; }
  modint operator*(const modint r) const { return modint(*this) *= r; }
  modint operator/(const modint r) const { return modint(*this) /= r; }
  modint &operator+=(const modint r) {
    n += r.n;
    if (n >= Mod) n -= Mod;
    return *this;
  }
  modint &operator-=(const modint r) {
    if (n < r.n) n += Mod;
    n -= r.n;
    return *this;
  }
  modint &operator*=(const modint r) {
    n = n * r.n % Mod;
    return *this;
  }
  modint &operator/=(modint r) {
    n = n * inv();
    return *this;
  }
  modint pow(u64 x) const {
    modint<Mod> ret(1), tmp(*this);
    while (x) {
      if (x&1) ret *= tmp;
      tmp *= tmp;
      x >>= 1;
    }
    return ret;
  }
  modint inv() const {
    return pow(Mod-2);
  }
};
using mint = modint<1'000'000'007>;

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

  ll n;
  cin >> n;
  vl a(n);
  rep(i, n) {
    cin >> a[i];
  }
  sort(all(a));
  vector<mint> c(n);
  rep(i, n) {
    c[i] = mint(a[i]);
  }

  mint ans(0);
  rep(i, n) {
    ll r = n-1-i;
    ans += c[i]*(2+r);
  }
  ans *= mint(2).pow(2*n-2);

  cout << ans.n << endl;
}


Measured memory_bytes: 3456
/* BISMILLAHIR RAHMANIR RAHIM */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
	ios_base :: sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n, m;
	cin >> n >> m;
	string G[n];
	for(int i = 0; i < n; i++) {
		cin >> G[i];
	}

	const ll mod = 1e9 + 7;
	ll dp[n + 2][m + 2];
	dp[0][0] = 1;

	auto isValid = [&](int i, int j) {
		return (i >= 0 and i < n and j >= 0 and j < m and G[i][j] != '#');
	};

	for(int i = 0; i< n; i++) {
		for(int j = 0; j < m; j++) {
			if( i == 0 and j == 0 ) continue;
			dp[i][j] = 0;
			if( !isValid( i, j ) ) continue;
			if( isValid( i - 1, j ) ) (dp[i][j] += dp[i - 1][j]) %= mod;
			if( isValid( i, j - 1 ) ) (dp[i][j] += dp[i][j - 1]) %= mod;
		}
	}

	cout << dp[n - 1][m - 1] << "\n";
}

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

int main(){
    int a, b;
    cin>>a>>b;
    int m = min(a, b);
    int mx = max(a, b);
    for(int i=0; i<mx; ++i){
        cout<<char(m+48);
    }
    cout<<endl;
}

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

typedef vector<int> vi;

const int INF = 1000000000;

int main() {FIN
    
    int n, k, x, y, t = 0;
    cin >> n;
    cin >> k;
    cin >> x;
    cin >> y;
    
    t += min(n, k) * x;
    if (n > k)
		t += (n - k) * y;
	cout << t << "\n";
    
    return 0;
}


Measured memory_bytes: 3580
from itertools import accumulate


def run(n, a):
    # sum_a = [sum(a[0:i+1]) for i in range(n)]
    sum_a = list(accumulate(a))
    li = 0
    ri = 2
    t = sum_a[-1]
    diff = sum_a[-1]
    # 真ん中の切れ込みを順に変更
    # 左の切れ込みの位置はiに対して単調増加
    # 左の切れ込みで真ん中の項を移動するかどうかは、
    # 真ん中の項を除いて、小さい方に入れる
    # ただし単調増加なので、左の切れ込みの左側が
    # 小さいときに真ん中を左の切れ込みの左側に入れる
    # 右も同様に考える
    for i in range(1, n-2):
        while sum_a[i] > sum_a[li+1] + sum_a[li]:
            li += 1
        while t + sum_a[i] > sum_a[ri+1] + sum_a[ri]:
            ri += 1
        p = sum_a[li]
        q = sum_a[i] - p
        r = sum_a[ri] - q - p
        s = t - sum_a[ri]
        diff = min(diff, max(p, q, r, s) - min(p, q, r, s))
    return diff


def read_line():
    n = int(input())
    a = list(map(int, input().split()))
    return (n, a)


def main():
    n, a = read_line()
    print(run(n, a))


if __name__ == '__main__':
    main()


Measured memory_bytes: 24180
#include <bits/stdc++.h>
using namespace std;
#define rep0(i,n) for(ll (i) = 0; (i) < (n); ++(i))
#define rrep0(i,n) for(ll (i) = (n) - 1; (i) >= 0; --(i))
#define rep1(i,n) for(ll (i) = 1; (i) < (n); ++(i))
#define rrep1(i,n) for(ll (i) = (n) - 1; (i) >= 1; --(i))
#define nfor(i,a,b) for(ll (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;
}

ll fac(ll n){
    ll t = 1;
    rep1(i, n + 1)t *= i;
    return t;
}

int main()
{
    ll n,m;
    cin >> n >> m;
    if (m/2 <= n) {
        cout << m / 2 << endl;
    }else{
        cout << n + (m - n * 2) / 4 << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;
using ll = long long;

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

    map<char, int> alph;
    char maximum = 'a';
    for (int i = 0; i < s.size(); i++) {
        alph[s[i]]++;
        if (alph[s[i]] >= alph[maximum]) {
            if (alph[s[i]] == alph[maximum] && s[0] == s[i]) {
                continue;
            } else {
                maximum = s[i];
            }
        }
    }

    string t = s;
    map<char, int> alph_tmp = alph;
    int min_out = s.size();
    for (char maximum = 'a'; maximum <= 'z'; maximum++) {
        string s = t;
        alph = alph_tmp;
        while (s.size() != alph[maximum]) {
            for (int i = 0; i < s.size() - 1; i++) {
                if (s[i] != maximum && s[i + 1] == maximum) {
                    alph[s[i]]--;
                    s[i] = maximum;
                    alph[maximum]++;
                }
            }
            for (int i = s.size() - 1; i >= 0; i--) {
                // if (s[i] != maximum || i == 0) {
                alph[s[i]]--;
                s.erase(i, 1);
                break;
                // }
            }
            // if (maximum == 'r') {
            // cout << s << " " << s.size() << " " << alph[maximum] << endl;
            // }
        }
        int output = t.size() - s.size();
        // if (output != t.size()) {
        // cout << maximum << " " << s << " " << output << endl;
        // }
        if (min_out > output) min_out = output;
    }
    cout << min_out << endl;

    return 0;
}


Measured memory_bytes: 3604
#include <cstdio>
#include <climits>
#include <cassert>
#include <cmath>
#include <iostream>
#include <string>
#include <algorithm>
#include <numeric>
#include <functional>
#include <tuple>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <vector>
#include <iterator>
#include <regex>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define FOR(x,xs) for(auto &x: xs)

using namespace std;
typedef long long ll;
typedef pair<int,int> PI;
typedef pair<ll,ll> PL;
typedef vector<int> VI;
typedef vector<ll> VL;

template <class T, template <class, class> class C, class charT = char>
void vdump(const C<T, allocator<T>> &v, const charT* delimiter = ", ",
           ostream &stream = cout) {
  copy(v.begin(), v.end(), ostream_iterator<T>(stream, delimiter));
  stream << endl;
}

// 1-indexed
template <class T, class Op = T (*) (T, T)>
struct Bit {
  int n;
  vector<T> dat;
  Op op;
  T unit;
  Bit(int n, Op op = Op(), T unit = T()) : n(n), dat(n + 1, unit), op(op), unit(unit) {
  }
  Bit(const vector<T> &arr, Op op = Op(), T unit = T())
    : n(arr.size()), dat(arr.size() + 1), op(op), unit(unit) {
    copy(arr.begin(), arr.end(), dat.begin() + 1);
    for(int i=1; i<n; i++) {
      dat[i + (i & -i)] = op(dat[i + (i & -i)], dat[i]);
    }
  }
  void operate(int k, T a) {
    while(k <= n) {
      dat[k] = op(dat[k], a);
      k += k & -k;
    }
  }
  T accum(int k) {
    T sum = unit;
    while(k > 0) {
      sum = op(sum, dat[k]);
      k -= k & -k;
    }
    return sum;
  }
};

int main() {
  ios::sync_with_stdio(false);
  int n;
  cin >> n;
  ll k;
  cin >> k;
  VL as(n);
  FOR(a,as) {
    cin >> a;
  }
  VL bs(n+1);
  bs[0] = 0;
  REP(i,0,n) {
    bs[i+1] = bs[i] + as[i] - k;
  }
  VL b_sort = bs;
  sort(b_sort.begin(), b_sort.end());
  Bit<ll, plus<ll>> bit(n+1, plus<ll>(), 0);
  ll ans = 0;
  FOR(b,bs) {
    int c = lower_bound(b_sort.begin(), b_sort.end(), b) - b_sort.begin() + 1;
    ans += bit.accum(c);
    bit.operate(c, 1);
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 6528
N, K = map(int,input().split())
mod = 10**9+7
res = 0
total = (N) * (N+1) // 2
for k in range(K, N + 2):
	tmp = k - 1
	X = tmp * (tmp + 1) // 2
	tmp = N-k
	Y = total - (tmp * (tmp + 1) // 2)
	res+= Y - X + 1
	res %= mod
print(res % mod)

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

using namespace std;

#define int long long

int n, m, k;
int c[3001][3001];
int f[3001][3001][4], g[3001][3001][4];

int gay(int x, int y, int cur)
{
	if (x == n && y == m)
	{
		if (cur < 3)
			return c[x][y];
		return 0;	
	}
	if (g[x][y][cur])
		return f[x][y][cur];
	int cur_ans = 0;
	if (y < m) cur_ans = max(cur_ans, gay(x, y + 1, cur));
	if (y < m && cur < 3) cur_ans = max(cur_ans, gay(x, y + 1, cur + 1) + c[x][y]);
	if (x < n) cur_ans = max(cur_ans, gay(x + 1, y, 0));
	if (x < n && cur < 3) cur_ans = max(cur_ans, gay(x + 1, y, 0) + c[x][y]);
	g[x][y][cur] = 1;
	return f[x][y][cur] = cur_ans;
}

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

	cin >> n >> m >> k;
	for (int i = 1; i <= k; i++)
	{
		int x, y, v;
		cin >> x >> y >> v;
		c[x][y] = v;
	}
	cout << gay(0, 1, 0);
}

Measured memory_bytes: 637316
#include<stdio.h>

int main()
{
    int a[10000], i, n, count=0;

    scanf("%d", &n);

    for (i = 0; i < n; i++)
        scanf("%d", &a[i]);

    for (i = 0; i < n; i++) {
        while (1)
            if (a[i] % 2 == 0 && a[i] != 0) {
                a[i] = a[i] / 2;
                count++;
            }
            else break;
    }

    printf("%d", count);

    return 0;
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef double db;

const ll mod  = 1e9+7;
const db eps  = 1e-9 ;
const ll maxn = 1e5+1;
const ll inf = LLONG_MAX;

#define mp make_pair
#define pb push_back
#define endl "\n"
#define deb(x) cout << #x << " " << x << endl

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

    db a,b,c,d;
    cin >> a >> b >> c >> d;
    
    if( ceil(c/b) > ceil(a/d)) cout << "No";
    else cout << "Yes";
    

    return 0;
} 

Measured memory_bytes: 3736
idx_com = 0
idx_x = 1
idx_y = 2
idx_z = 3

n, nq = map(int, input().split())
parents = list(range(n))
ranks = [0] * n
weights = [0] * n

def find(x):
    if parents[x] == x:
        return x
    y = find(parents[x])
    weights[x] += weights[parents[x]]
    parents[x] = y
    return y

def unite(x, y, w):
    root_x = find(x)
    root_y = find(y)

    if ranks[root_x] < ranks[root_y]:
        parents[root_x] = root_y
        weights[root_x] = -w - weights[x] + weights[y]
    else:
        parents[root_y] = root_x
        weights[root_y] = +w - weights[y] + weights[x]
        if ranks[root_x] == ranks[root_y]:
            ranks[root_x] += 1

def same(x, y):
    return find(x) == find(y)

def diff(x, y):
    return weights[y] - weights[x]

for _ in range(nq):
    q = list(map(int, input().split()))
    if q[idx_com] == 0:
        unite(q[idx_x], q[idx_y], q[idx_z])
    else:
        if same(q[idx_x], q[idx_y]):
            print(diff(q[idx_x], q[idx_y]))
        else:
            print("?")


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

const int N = 1e5 + 5;
string s;
string t;
int prefixS[N];
int prefixT[N];

int q;

int main() {
	cin >> s;
	cin >> t;
	fill(prefixS, prefixS + N, 0);
	fill(prefixT, prefixT + N, 0);
	for(int i = 0; i < s.length(); i++) {
		prefixS[i+1] = prefixS[i] + ((s[i] == 'A')? 1:2);
	}

	for(int i = 0; i < t.length(); i++) {
		prefixT[i+1] = prefixT[i] + ((t[i] == 'A')? 1:2);
	}

	cin >> q;

	int a, b, c, d;
	while(q--) {
		cin >> a >> b >> c >> d;
		if(((prefixS[b] - prefixS[a-1])-(prefixT[d] - prefixT[c-1]))%3) {
			cout << "NO" << endl;
		} else {
			cout << "YES" << endl;
		}
	}

	return 0;
}

Measured memory_bytes: 1664
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <climits>
#include <iomanip>
#include <cmath>

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout << std::fixed << std::setprecision(10);

	int n;
	cin >> n;

	for (int i = 1; i < 10; i++) {
		for (int j = 1; j < 10; j++) {
			if (i * j == n) {
				cout << "Yes" << endl;
				return 0;
			}
		}
	}
	cout << "No" << endl;

	return 0;
}

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

int main(){
  int a,b,c,d,e;
  cin >> a >> b >> c >> d >> e;
  int N=5;
  
  //注文してから届くまでの時間
  vector<int> Time = {a,b,c,d,e};
  //順番の並び替え
  vector<int> index = {0,1,2,3,4};
  
  int BestTime = (int)1e9;//←10^9(double)
  
  //indexの中身が
  //0,1,2,3,4
  //0,1,2,4,3
  //:
  //4,3,2,1,0
  //の全探索ができる
  do {
    int NowTime=0;
    for (int i=0;i<N;++i){
      //10で割り切れるようになるまで1を足し続ける
      while (NowTime%10!=0) NowTime++;
      NowTime+=Time[index[i]];
    }
    BestTime=min(BestTime,NowTime);
  }
  while (next_permutation(index.begin(),index.end()));
  cout << BestTime << endl;
}
//全探索による解法
    
  


Measured memory_bytes: 256
//Andrew Yang
#include <iostream>
#include <stdio.h>
#include <sstream>
#include <fstream>
#include <string>
#include <string.h>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>	
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <climits>
using namespace std;
#define FOR(index, start, end) for(int index = start; index < end; index++)
#define RFOR(index, start, end) for(int index = start; index > end; index--)
#define FOREACH(itr, b) for(auto itr = b.begin(); itr != b.end(); itr++)
#define RFOREACH(itr, b) for(auto itr = b.rbegin(); itr != b.rend(); itr++)
#define INF 1000000000
#define M 1000000007
typedef long long ll;
typedef pair<int, int> pii;
vector<int> edges[100000];
int n, m, q;
int v[100000], d[100000], c[100000];
int ans[100000];
bool visited[100000][11];
void dfs(int node, int dis, int color)
{
	if (dis < 0)
	{
		return;
	}
	if (visited[node][dis])
	{
		return;
	}
	visited[node][dis] = true;
	if (ans[node] == -1)
	{
		ans[node] = color;
	}
	for (int j : edges[node])
	{
		dfs(j, dis - 1, color);
	}
	
}
int main(void)
{
	scanf("%d%d", &n, &m);
	FOR(i, 0, m)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		a--;
		b--;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	scanf("%d", &q);
	FOR(i, 0, q)
	{
		scanf("%d%d%d", &v[i], &d[i], &c[i]);
		v[i]--;
	}
	FOR(i, 0, n)
	{
		ans[i] = -1;
	}
	RFOR(i, q - 1, -1)
	{
		dfs(v[i], d[i], c[i]);
	}
	FOR(i, 0, n)
	{
		if (ans[i] != -1)
		{
			printf("%d\n", ans[i]);
		}
		else
		{
			printf("%d\n", 0);
		}
	}
}

Measured memory_bytes: 9080
#include<stdio.h>
#define MAX 100000
#define SENTINEL 2000000000
struct Card{
 char suit;
 int value;
};
struct Card L[MAX/2+2],R[MAX/2+2];
void merge(struct Card A[],int n,int left,int mid,int right){
 int i,j,k;
 int n1=mid-left;
 int n2=right-mid;
 for(i=0;i<n1;i++)L[i]=A[left+i];
 for(i=0;i<n2;i++)R[i]=A[mid+i];
 L[n1].value=R[n2].value=SENTINEL;
 i=j=0;
 for(k=left;k<right;k++){
  if(L[i].value<=R[j].value)A[k]=L[i++];
  else A[k]=R[j++];
 }
}
void mergeSort(struct Card A[],int n,int left,int right){
 int mid;
 if(left+1<right){
  mid=(left+right)/2;
  mergeSort(A,n,left,mid);
  mergeSort(A,n,mid,right);
  merge(A,n,left,mid,right);
 }
}
int partition(struct Card A[],int n,int p,int r){
 int i,j;
 struct Card t,x;
 x=A[r];
 i=p-1;
 for(j=p;j<r;j++){
  if(A[j].value<=x.value){
   i++;
   t=A[i];A[i]=A[j];A[j]=t;
  }
 }
 t=A[i+1];A[i+1]=A[r];A[r]=t;
 return i+1;
}
void quickSort(struct Card A[],int n,int p,int r){
 int q;
 if(p<r){
  q=partition(A,n,p,r);
  quickSort(A,n,p,q-1);
  quickSort(A,n,q+1,r);
 }
}
int main(){
 int n,i,v;
 struct Card A[MAX],B[MAX];
 char S[10];
 int stable=1;
 scanf("%d",&n);
 for(i=0;i<n;i++){
  scanf("%s %d",S,&v);
  A[i].suit=B[i].suit=S[0];
  A[i].value=B[i].value=v;
 }
 mergeSort(A,n,0,n);
 quickSort(B,n,0,n-1);
 for(i=0;i<n;i++){
  if(A[i].suit!=B[i].suit)stable=0;
 }
 if(stable==1)printf("Stable\n");
 else printf("Not stable\n");
 for(i=0;i<n;i++)printf("%c %d\n",B[i].suit,B[i].value);
 return 0;
}


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

typedef long long ll;

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for(int i=0; i<N; i++){
    cin >>A[i];
  }
  vector<int> ans(N);
  for(int i=0; i<N; i++){
    ans[A[i]-1]=i+1;
  }
  for(int i=0; i<N; i++){
    cout << ans[i] << " ";
  }
  cout <<endl;
}

Measured memory_bytes: 1664
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=2e5+5;
ll k,n,a[maxn],r[maxn],b[maxn];//r数组  实际路径   b数组 用城市做下标 顺序（时间）
ll  be,len,p=1 ,cnt;
int main()
{
   cin>>n>>k;
   for(int i=1;i<=n;i++) cin>>a[i];
   while(1)
   {
   	   if(b[a[p]]!=0)
   	   {
   	   	  be=b[a[p]]; len=cnt-be+1;break;
		  }
		r[++cnt]=a[p];
		b[a[p]]=cnt;
		p=a[p];
   }
   if(k<=be) cout<<r[k];
   else
      {
      	 int s=(k-be)%len;
      	 cout<<r[be+s];
	   } 

return 0;
}


Measured memory_bytes: 8192
#include "bits/stdc++.h"
using namespace std;
#define PB push_back
#define MP make_pair
#define REP(i,n) for(int i=0;i<(n);i++)

int main(){
    string in;
    string ans="";
    for(int i=0;i<3;i++){
        cin>>in;
        ans+=(in[0]-'a'+'A');
    }
    cout<<ans<<endl;
}

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

int main() {
	
	int a, b, c, x, y;
	cin >> a >> b >> c >> x >> y;
	int ans;
	int yen;
	
	// ABピザをmin(x, y)枚買い、残りはAピザorBピザを買う
	int tmp_x = x, tmp_y = y;
	yen = c * 2 * min(x, y);
	tmp_x -= min(x, y);
	tmp_y -= min(x, y);
	if(tmp_x > 0) yen += a * tmp_x;
	if(tmp_y > 0) yen += b * tmp_y;
	ans = yen;
	
	// ABピザをmax(x, y)枚買う
	yen = c * 2 * max(x, y);
	ans = min(ans, yen);
	
	//AピザとBピザのみを買う
	yen = a * x + b * y;
	ans = min(ans, yen);
	
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <cstdlib>
#include <set>
#include <queue>
using namespace std;

#define X first
#define Y second
#define N 110
typedef long long ll;
typedef pair<int,int> pii;
const int Mod=1000000007;

const double INF=1e18;

int n,m;
int s[N],t[N],a[N],b[N];

int main()
{
	//freopen("in.in","r",stdin);
	//freopen("out.out","w",stdout);
	
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&t[i]),s[i]=t[i]+s[i-1];
	scanf("%d",&m);
	for (int i=1;i<=m;i++)
	{
		scanf("%d%d",&a[i],&b[i]);
		printf("%d\n",s[a[i]-1]+s[n]-s[a[i]]+b[i]);
	}
	
	return 0;

}


Measured memory_bytes: 256
import java.util.*;

class Main{
	public static void main(String[] args){
		Scanner scan=new Scanner(System.in);
        int N=scan.nextInt();
        for(int i=1;i<10;i++){
          for(int j=1;j<10;j++){
            if(i*j==N){
              System.out.println("Yes");
              System.exit(0);
            }
          }
        }
      System.out.println("No");
    }
}

Measured memory_bytes: 21972
#include <iostream>
#include <math.h>
#include <vector>
#include <cstdlib>
#include <queue>

using namespace std;

int main(int argc, const char * argv[]) {
	int N, L;
	int min, min_index;
	int tmpabs;
	int sum;

	cin >> N >> L;
	int taste[N];

	taste[0] = L;
	min = abs(L);
	min_index = 0;
	sum = L;
	for(int i=1; i<N; i++){
		taste[i] = L + i;
		sum += taste[i];
		tmpabs = abs(taste[i]);
		if(min > tmpabs){
			min = tmpabs;
			min_index = i;
		}
	}
	cout << sum-taste[min_index] << endl; 
	return 0;
}



Measured memory_bytes: 256
import itertools

N = int(input())

l = len(str(N))

ans = 0
for i in range(1,l+1):
    for v in itertools.product(['3','5','7'],repeat=i):
        if '3' in v and '5' in v and '7' in v:
            n = int(''.join(list(v)))
            if n <= N:
                ans += 1

print(ans)



Measured memory_bytes: 3188