akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define endl '\n'
#define fast ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define zy -2147382637
#define bql 2147483647
#define ll long long
#define ull unsigned long long
#define ld long double
#define il inline
#define sz(x) x.size()
#define maxn 100010
#define rp(i, l, r) for (int i = l; i <= r; i++)
#define rb(i, r, l) for (int i = r; i >= l; i--)
#define fi first
#define se second
#define pb push_back
#define mp make_pair

using namespace std;
ll max(ll a,ll b){if(a>b)return a;else return b;}
ll min(ll a,ll b){if(a<b)return a;else return b;}
ll lowbit(ll x){return x&(-x);}
ll prime(ll x){
   if(x<=1)return false;
   for(int i=2;i<=int(sqrt(x));i++){
	   if(x%i==0)return false;
   }return true;
}bool cmp(ll a,ll b){return a>b;}
ll gcd(ll a,ll b){ll r;while(b>0){r=a%b;a=b;b=r;}return a;}
ll powmod(ll a,ll b,ll mod) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
inline int readint() {
	char c = getchar(); int w = 1; int x = 0;
	while (!isdigit(c))
		(c == '-') && (w = -w), c = getchar();
	while (isdigit(c))
		x = (x << 3) + (x << 1) + (c ^ '0'), c = getchar();
	x *= w;
	return x;
}
inline ll readll() {
	char c = getchar(); ll w = 1; ll x = 0;
	while (!isdigit(c))
		(c == '-') && (w = -w), c = getchar();
	while (isdigit(c))
		x = (x << 3) + (x << 1) + (c ^ '0'), c = getchar();
	x *= w;
	return x;
}
void fl(string name){
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}
const int dx[8] = {-1, 1, 0, 0, -1, 1, -1, 1},
		  dy[8] = {0, 0, -1, 1, -1, -1, 1, 1};
struct node{int x,y;};
int h,w,k,xx1,yy1,x2,y2;
bool ok(int x,int y){
	if(x<=h&&x>=1&&y<=w&&y>=1)return true;
	else return false;
}
queue<node>Q;
int main(){
	cin>>h>>w>>k;
	char g[h+1][w+1];
	int vis[h+1][w+1],step[h+1][w+1];
	memset(vis,0,sizeof(vis));
	memset(step,0,sizeof(step));
	cin>>xx1>>yy1>>x2>>y2;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			cin>>g[i][j];
		}
	}
	node a,b;
	a.x=xx1,a.y=yy1;
	step[xx1][yy1]=0;
	vis[xx1][yy1]=1;
	Q.push(a);
	int ans=bql;
	while(!Q.empty()){
		a=Q.front();
		Q.pop();
		if(a.x==x2&&a.y==y2){
			ans=min(ans,step[x2][y2]);
		}
		for(int i=0;i<4;i++){
			for(int j=1;j<=k;j++){
				b.x=dx[i]*j+a.x;
				b.y=dy[i]*j+a.y;
				if(ok(b.x,b.y)==0||(step[b.x][b.y]<=step[a.x][a.y]&&step[b.x][b.y]))break;
				else{
					if(g[b.x][b.y]=='@')break;
					if(g[b.x][b.y]=='.'&&!vis[b.x][b.y]){
						vis[b.x][b.y]=1;
						step[b.x][b.y]=step[a.x][a.y]+1;
						Q.push(b);
					}
				}
			}
		}
	}
	if(ans==bql)cout<<-1<<endl;
	else cout<<ans<<endl;
	return 0;
}
/* stuff to remember
	* int overflow, array bounds
	* special cases (n=1? n=0?)
	* do something instead of nothing and stay organized
	* USE STATIC ARRAYS
	* DEFINING ARRAYS BEFORE main()
	* DO NOT DEFINE ARRAYS IN main()
	* USE INT INSTEAD OF LL,NOTICE THE MLE
*/

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

int main(){
    int K, S;
    cin >> K >> S;
    int cnt = 0;
    for (int X=0; X<=K; X++){
        for (int Y=0; Y<=K; Y++){
            int Z = S - X - Y;
            if (Z <= K && 0 <= Z){
                cnt += 1;
            }
        }
    }
    cout << cnt << endl;
}

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

int main(){
  int n,m,x,i;
  cin>>n>>m>>x;
  int a[m];
  for(i=0;i<m;i++)cin>>a[i];
  int L=0,R=0;
  for(i=0;i<m;i++){
    if(a[i]<x)L++;
    else R++;
  }
  cout<<min(L,R);
}
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
  char a, b;
  cin >> a >> b;

  if (a == 'H') cout << b << endl;
  else if (b == 'H') cout << 'D' << endl;
  else cout << 'H' << endl;

  return 0;
}


Measured memory_bytes: 384
from collections import Counter

N = int(input())
blue_list = [input() for _ in range(N)]
blue = Counter(blue_list)

M = int(input())
red_list = [input() for _ in range(M)]
red = Counter(red_list)

blue.subtract(red)
c = blue.most_common(1)[0][1]
if c < 0:
    print(0)
else:
    print(c)


Measured memory_bytes: 3700
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define MAXN 2006
using namespace std;
int deep[MAXN],sum,son[MAXN],k,n,u,v,ans;
vector<int> road[MAXN];
void DFS(int x,int father)
{
	deep[x]=deep[father]+1;
	if(deep[x]==k/2+1) son[x]=1;
	if(deep[x]>k/2) sum++;
	for(int i=0;i<(int)road[x].size();i++)
	{
		int nex=road[x][i];
		if(nex==father) continue;
		DFS(nex,x);
		son[x]+=son[nex];
	}
}
int main()
{
	//freopen("shorten.in","r",stdin);
	//freopen("shorten.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&u,&v);
		road[u].push_back(v);
		road[v].push_back(u);
	}
	deep[0]=-1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
			son[j]=0;
		sum=0;
		DFS(i,0);
		if(k%2)
		{
			int maxone=0;
			for(int j=1;j<=n;j++)
				if(deep[j]==1) maxone=max(maxone,son[j]);
			sum-=maxone;
		}
		if(i==1) ans=sum;
		else ans=min(ans,sum);
	}
	printf("%d",ans);
}

Measured memory_bytes: 512
#include<cstdio>
#include<algorithm>
int main(){
	int n;
	scanf("%d",&n);
	long long int a[n]={};
	long long int b[n]={};
	for(int i=0;i<n;i++){
		scanf("%lld",&a[i]);
		b[i]=a[i];
	}
	std::sort(b,b+n);
	long long int x=b[n/2-1];
	long long int y=b[n/2];
	for(int i=0;i<n;i++){
		if(a[i]<=x)printf("%lld\n",y);
		else printf("%lld\n",x);
	}
	return 0;
}

Measured memory_bytes: 5248
#include <iostream>

int main() {
	
	int S;

	std::cin >> S;

	int h = S / 3600;
	int m = S % 3600 / 60;
	int s = S % 3600 % 60;

	std::cout << h << ":" << m << ":" << s << "\n";

	return 0;
}


Measured memory_bytes: 3092
#include <iostream>
#include <string>
using namespace std;
int main(){
  int n;
  int a,b;
  int total = 0;
  cin >> n >> a >> b;
    for(int i=1;i<=n;i++){
        int x = i%10;
        for(int j = 10;j < 10e5;j= j*10){
        if(i/j > 0){
            int l = i/j;
            x += l%10;
            }else{
             break;
            }
          }
        if( (a<=x) && (b>=x) ){
            total += i;
        }
      }
      cout << total << endl;
      return 0;
    }



Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>

using namespace std;

int n, m;
vector<string> ids;

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        ids.push_back(s);
    }

    cin >> m;
    bool locked = true;
    for (int i = 0; i < m; ++i) {
        string s;
        cin >> s;
        auto itr = find(ids.begin(), ids.end(), s);
        if (itr != ids.end()) {
            if (locked) cout << "Opened by " << s << endl;
            else cout << "Closed by " << s << endl;
            locked = !locked;
        } else {
            cout << "Unknown " << s << endl;
        }
    }
}

Measured memory_bytes: 3204
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
typedef long long ll;
int main() {
  int ans=0;
  string s,t;
  cin>>s>>t;
  rep(i,s.length()){
    if(s[i]!=t[i])ans++;
  }
  cout<<ans;
}

Measured memory_bytes: 3908
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define reps(i,s,n) for(int i=s;i<n;i++)
#define rep_bit(n) for (int bit = 0; bit < (1<<n); ++bit)
#define all(x) (x).begin(),(x).end()
#define ll long long
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
using namespace std;
typedef vector<vector<int> > Graph;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
//条件式 ? 真の場合の文 : 偽の場合の文
//abs(x) = (x の絶対値)
//string S  S[i],S += T,S += c,S.size(),S.substr(l),S.substr(l, r)
//*min_element(all(x)) *max_element(all(x))
//vi x; x.back(),x.front(),x.push_back(),x.pop_back()
//swap(a, b)
//gcd(a, b)最大公約数
//sort(all(x)),reverse(all(x)),sort(x.begin()+l,a.begin()+r)lからrまで
//stack<int> a; a.push(x),a.pop(),a.top(),a.empty()bool
//queue<int> b; b.push(x),b.pop(),b.front(),b.empty()bool,b.size() 要素が小さい順
//priority_queue<int, vector<int>, greater<int>> c,c.top()
//map<int, int> M1; 変数[key] = value; 変数.erase(key); 変数.at(key); 変数.count(key)所属判定　変数.size()
//find(all(x), key)boolソート済みのベクトル
//*lower_bound(all(x),k)以上の最小の要素,*uppper_bound(all(x),k)より大きい最小の要素
Graph G(200005);
vi ans;

void dfs(int v,int p = -1) {
    for(int u : G.at(v)){
        if(u == p) continue;
        ans.at(u) += ans.at(v);
        dfs(u,v);
    }
}

int main(){

    int n,q;
    cin >> n >> q;
    rep(i,n-1){
        int a,b;
        cin >> a >> b;
        --a;--b;
        G.at(a).push_back(b);
        G.at(b).push_back(a);
    }
    ans.resize(n);
    rep(i,q){
        int p,x;
        cin >> p >> x;
        --p;
        ans.at(p) += x;
    }
    dfs(0);
    rep(i,n){
        cout << ans.at(i) << endl;
    }
    return 0;
}


Measured memory_bytes: 26624
import sys;input=lambda:sys.stdin.readline().rstrip();aint=lambda:int(input());ints=lambda:list(map(int,input().split()))
import math;floor,ceil=lambda x:int(math.floor(x)),lambda x:int(math.ceil(x))
from functools import reduce;gcd=lambda*x:reduce(math.gcd,x);lcm=lambda*x:reduce(lambda x,y:(x*y)//gcd(x,y),x,1)
from collections import deque
import bisect
Yes=lambda b:print("Yes"if b else"No");YES=lambda b:print("YES"if b else"NO")
is_even=lambda x:True if x%2==0 else False

def main():
  s=input()
  if s=='ABC':
    print('ARC')
  else:
    print('ABC')

if __name__ == '__main__':
    main()

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}


struct UnionFindTree{
    vector<int>par,sz;
    UnionFindTree(int n=0){
        par.resize(n);
        sz.resize(n);
        for(int i=0;i<n;i++){
            par[i]=i;
            sz[i]=1;
        }
    }
    int find(int x){
        return x==par[x]?x:par[x]=find(par[x]);
    }
    void unite(int x,int y){
        x=find(x);y=find(y);
        if(x==y)return;
        if(sz[x]<sz[y])swap(x,y);
        sz[x]+=sz[y];
        par[y]=x;
    }
    bool areSame(int x,int y){
        return find(x)==find(y);
    }
    int size(int x){
        return sz[find(x)];
    }
};

vector<int>G[111111];
vector<pint>bridge;

int ord[111111],low[111111];
bool vis[111111];

UnionFindTree uf;

void dfs(int v,int p,int &k){
    vis[v]=true;
    ord[v]=k++;
    low[v]=ord[v];

    for(auto &u:G[v]){
        if(!vis[u]){
            dfs(u,v,k);
            chmin(low[v],low[u]);
            if(ord[v]<low[u])bridge.pb({v,u});
            else uf.unite(v,u);
        }
        else if(u!=p){
            chmin(low[v],ord[u]);
        }
    }
}

int N,M;

vint GG[111111];

int dp[111111][2];

void calc(int v,int p){
    vis[v]=1;
    dp[v][0]=0;
    dp[v][1]=uf.size(v);
    for(auto &u:GG[v]){
        if(u==p)continue;
        calc(u,v);
        dp[v][1]+=dp[u][0];
        dp[v][0]+=max(dp[u][0],dp[u][1]);
    }

}

signed main(){
    cin>>N>>M;
    rep(i,M){
        int a,b;cin>>a>>b;
        G[a].pb(b);G[b].pb(a);
    }
    uf=UnionFindTree(N);

    int K=0;
    rep(i,N)if(!vis[i])dfs(i,-1,K);

    for(auto &e:bridge){
        GG[uf.find(e.fi)].pb(uf.find(e.se));
        GG[uf.find(e.se)].pb(uf.find(e.fi));

    }


    int ans=0;
    memset(vis,0,sizeof(vis));
    rep(i,N){
        if(uf.find(i)!=i||vis[i])continue;
        calc(i,-1);
        ans+=max(dp[i][0],dp[i][1]);
    }
    cout<<ans<<endl;
    return 0;
}

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

int main() {
  int n, m;
  cin >> n >> m;
  int ans = n*(n-1)/2 + m*(m-1)/2;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3604
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <vector>
#define ll long long 
using namespace std;

int main() {
	int n, sum = 0;;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		sum += i;
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import java.nio.charset.StandardCharsets;

public class Main {

	public static void main(String[] args) throws IOException {
		InputStreamReader reader = new InputStreamReader(System.in, StandardCharsets.UTF_8);
		BufferedReader in = new BufferedReader(reader);
		String[] tokens = in.readLine().split(" ");
		int N = Integer.parseInt(tokens[0]);
		int K = Integer.parseInt(tokens[1]);
		in.close();
		System.out.println((N - K + 1));
	}

}

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

bool search(int a){
	if(a==1) return false;
	else if(a%2==0) return true;
	else return false;
}

int main() {
	int a,b;
	cin >> a >> b;
	if(search(a*b)) cout << "Even" << endl;
	else cout << "Odd" << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define pi M_PI
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int a[100][100], b[100], c[100];

int main() {
    int n, m;
    cin >> n >> m;
    REP(i,n) REP(j,m) cin >> a[i][j];
    REP(i,m) cin >> b[i];
    REP(i,n) REP(j,m) c[i] += a[i][j] * b[j];
    REP(i,n) cout << c[i] << endl;
    return 0;
}

Measured memory_bytes: 3112
# ABC068C - Cat Snuke and a Voyage (ARC079C)
import sys
input = sys.stdin.readline

def main():
    N, M = tuple(map(int, input().split()))
    A = tuple(tuple(map(int, input().split())) for _ in range(M))
    S, D = set(), set()  # start, destination
    for a, b in A:
        if a == 1:
            S |= {b}
        if b == N:
            D |= {a}
    print("POSSIBLE" if S & D else "IMPOSSIBLE")


if __name__ == "__main__":
    main()

Measured memory_bytes: 37224
#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
#define inf 10000000
using namespace std;
typedef long long int ll;

int main(){

    int N,A,B;
    cin >> N;

    if(N == 2){
        cin >> A >> B;
        cout << A+B << endl;
    }else{
        cout << "Hello World" << endl;
    }

}

Measured memory_bytes: 256
N = int(input())
L = list(map(int, input().split()))

if (N < 3):
    print(0)
    exit(0)
count = 0

for i in range(N-2):
    for j in range(i + 1, N-1):
        for k in range(j + 1, N):
            a = L[i]
            b = L[j]
            c = L[k]

            if (a != b and b != c and c != a and a + b > c and b + c > a and c + a > b):
                count += 1

print(count)


Measured memory_bytes: 68276
#include <stdio.h>
#define M 1000

int main(){
  int a[M],i,j,n,v;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
  }
  
  for(j=1;j<n+1;j++){
    for(i=0;i<n;i++){
      printf("%d",a[i]);
      if(i!=n-1) printf(" ");
    }
    v=a[j];
    i=j-1;
    while(i>=0&&a[i]>v){
      a[i+1]=a[i];
      i=i-1;
      a[i+1]=v;
    }
    printf("\n");
  }
  return 0;
}
    



Measured memory_bytes: 2064
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner scanner = new Scanner(System.in);
		int listCount = scanner.nextInt();
		int[] listSort = new int[listCount];
		for(int i = 0; i < listCount; i++){
			listSort[i] = scanner.nextInt();
		}
		trace(listSort, listCount);
		insertionSort(listSort, listCount);
	}

	private static void insertionSort(int[] listSort, int listCount){
		for(int i = 1; i < listCount; i++){
			int v = listSort[i];
			int j = i - 1;
			while((j >= 0) && (listSort[j] > v)){
				listSort[j + 1] = listSort[j];
				j--;
			}
			listSort[j + 1] = v;
			trace(listSort, listCount);
		}
	}

	private static void trace(int[] listSort, int listCount){
		int jugeCount = listCount - 1;
		for(int i = 0; i < listCount; i++){
			System.out.print(listSort[i]);
			if(i < jugeCount){
				System.out.print(" ");
			}
		}
		System.out.print("\n");
	}
}

Measured memory_bytes: 27820
require 'matrix'
require 'set'
loop {
    m = gets.to_i
    break if m == 0
    target = (1..m).map { Vector[*gets.split.map(&:to_i)] }.sort_by{|v| v[0]}
    n = gets.to_i
    stars = Set[*(1..n).map { Vector[*gets.split.map(&:to_i)] }]
    stars.each{|s|
        diff = s - target[0]
        if target.all?{|c| stars.include?(c + diff)}
            puts diff.to_a.join(" ")
            break
        end
    }
}

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

#ifdef DEBUG
#include <Mylib/Debug/debug.cpp>
#else
#define dump(...) ((void)0)
#endif

template <typename T, typename U>
bool chmin(T &a, const U &b){
  return (a > b ? a = b, true : false);
}

template <typename T, typename U>
bool chmax(T &a, const U &b){
  return (a < b ? a = b, true : false);
}

template <typename T, size_t N, typename U>
void fill_array(T (&a)[N], const U &v){
  std::fill((U*)a, (U*)(a + N), v);
}

template <typename T, size_t N, size_t I = N>
auto make_vector(const std::array<int, N> &a, T value = T()){
  static_assert(I >= 1);
  static_assert(N >= 1);
  if constexpr (I == 1){
    return std::vector<T>(a[N - I], value);
  }else{
    return std::vector(a[N - I], make_vector<T, N, I - 1>(a, value));
  }
}

template <typename T>
std::ostream& operator<<(std::ostream &s, const std::vector<T> &a){
  for(auto it = a.begin(); it != a.end(); ++it){
    if(it != a.begin()) s << " ";
    s << *it;
  }
  return s;
}

template <typename T>
std::istream& operator>>(std::istream &s, std::vector<T> &a){
  for(auto &x : a) s >> x;
  return s;
}


namespace haar_lib {}

namespace solver {
  using namespace haar_lib;

  void init(){
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(12);
    std::cerr << std::fixed << std::setprecision(12);
    std::cin.exceptions(std::ios_base::failbit);
  }

  void solve(){
    int64_t a, b, c, d; std::cin >> a >> b >> c >> d;

    int64_t ans = LLONG_MIN;

    for(auto x : {a, b}){
      for(auto y : {c, d}){
        chmax(ans, x * y);
      }
    }

    std::cout << ans << "\n";
  }
}

int main(){
  solver::init();
  while(true){
    try{
      solver::solve();
    }catch(const std::istream::failure &e){
      break;
    }
  }
  return 0;
}


Measured memory_bytes: 3912
#include <stdio.h>

int main(void)
{
    int n, a[100], i, max, min;
    scanf ("%d", &n);
    for (i = 0; i < n; i++)
    {
        scanf ("%d", &a[i]);
    }
    max = a[0];
    min = a[0];
    for (i = 1; i < n; i++)
    {
        if (max <= a[i]) max = a[i];
        if (min >= a[i]) min = a[i];
    }
    printf ("%d\n", max - min);
    return (0);
}


Measured memory_bytes: 128
#include<stdio.h>

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

		int i, j;
		for (j = 1; j <= H; j++)
		{
			for (i = 1; i <= W - 1; i++)
			{
				printf("#");
			}
			printf("#\n");
		}
		printf("\n");
	}

	return 0;
}

Measured memory_bytes: 1016
#include <iostream>
#include <algorithm>
#include <vector>
#include <bitset>

using namespace std;

int a, b, c, x, y;

int main()
{
    cin >> a >> b >> c >> x >> y;
    int ans = 1 << 30;
    for (int i = 0; i <= 100000; i++)
    {
        int price = 2 * c * i + max(0, x - i) * a + max(0, y - i) * b;
        ans = min(ans, price);
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long 
#define rep(i,a,b) for(ll i=a; i<b; ++i)
#define BOOST std::ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define all(v) v.begin(),v.end()
#define sl(a) a.size()
#define mod 1000000007 
#define lcm(a,b) (a*b)/__gcd(a,b)
#define MAX 10000003
using namespace std;
ll count(ll arr[], ll n, ll i, ll k, vector<ll> &dp)
{
    if(i>=n-1) return 0;
    if(dp[i]!=-1) return dp[i];
    if(i<n-k and n>=k) 
    {
        ll m=INT_MAX;
        rep(j,1,k+1)
        {
            m=min(m,abs(arr[i+j]-arr[i])+count(arr,n,i+j,k,dp));
        }return dp[i]=m;
    }
    return dp[i]=abs(arr[n-1]-arr[i]);
}
void solve()
{
    ll n,k;  cin>>n>>k;
    ll arr[n];
    vector<ll> dp(n+1,-1);
    rep(i,0,n)  cin>>arr[i];
    cout<<count(arr,n,0,k,dp);
}
int main()
{
    BOOST
    int T=1;  //cin>>T;
    while(T--) solve();
    return 0;
}

Measured memory_bytes: 14288
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
using namespace std;

//typedefリスト
typedef vector<int> vint;
typedef vector<string> vstr;

int main(void) {
	int N;
	cin >> N;
	if (N%2==0) {
		cout << N << endl;
	}
	else cout << 2 * N << endl;
}

Measured memory_bytes: 256
/*
 * author: calgagi
 *         Calvin Gagliano 
 */
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long
#define ii pair<int, int>
#define ar array
#define f first
#define s second
#define dd long double

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

    int ans = 0;
    for (ll i = 2; i*i <= n; i++) {
        if (n % i == 0) {
            int counter = 1, j = 0;
            while (n % i == 0) {       
                n /= i;
                j++;
                if (j == counter) {
                    counter++;
                    j = 0;
                    ans++;
                }
            }
        }
    }
         
    bool prime = n != 1;
    for (ll i = 2; i*i <= n; i++) {
        if (n % i == 0) {
            prime = 0;
        }
    }

    if (prime) {
        ans++;
    }

    cout << ans << endl;

    return;
}

int main() {
    ios_base::sync_with_stdio(false);  
    cin.tie(NULL);
    srand(chrono::steady_clock::now().time_since_epoch().count()); 
    
    int t = 1;
    /* cin >> t; */
    while (t--) {
        solve();
    }

    return 0;
}


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

Measured memory_bytes: 2732
import os
import heapq
import sys
import math
from collections import defaultdict
from io import BytesIO, IOBase
def main():
    
    #for _ in range(int(input())):
    n=int(input())
    st=input()
    if len(st)<=n:
        print(st)
    else:
        print(st[0:n]+"...")
   
        
    
       
                            


BUFSIZE = 8192

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == "__main__":
    main()


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

using namespace std;

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

int n, q;
int A[20];
int M[200];

bool dfs(int i, int m, int sum){
    if(i == n) return sum == m;

    if(dfs(i+1, m, sum)) return true;
    if(dfs(i+1, m, sum + A[i])) return true;

    return false;
}

void solve(){
    for (int i = 0; i < q; i++)
    {
        if(dfs(0, M[i], 0)) puts("yes");
        else puts("no");
    }
    
}


int main(){

    cin >> n;
    for (int i = 0; i < n; i++) cin >> A[i];
    cin >> q;
    for (int i = 0; i < q; i++) cin >> M[i];
    

    solve();

    return 0;

}


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

int main() {
    int N, M, X, i;
    int cost1 = 0, cost2 = 0;
    cin >> N >> M >> X;
    vector<int> toll(M);
    for (i = 0; i < M; i++){
        cin >> toll.at(i);
    }
    for (i = 0; i < M; i++) {
        if (toll.at(i) < X) cost1++;
        else break;
    }
    cost2 = M - cost1;
    cout << min(cost1, cost2) << endl;
}

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

ll count(string &S) {
    ll x = 0;
    int even = 1;
    rep(i,S.size()-1) {
        if (S.at(i) == S.at(i + 1)) {
            if (even == 1) ++x;
            even *= -1;
        } else {
            even = 1;
        }
    }
    return x;
}

int main() {
    string S;
    ll K;
    cin >> S >> K;
    string S2 = S + S; 
    ll ans;
    if (S.size() == 1) {
        ans = K / 2;
    } else {
        bool same = true;
        rep(i,S.size()) {
            if (S.at(i) != S.at(0)) {
                same = false;
                break;
            }
        }
        if (same == true) {
            ans = S.size() * K / 2;
        } else {
            ans = count(S) + (K - 1) * (count(S2) - count(S));
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 3632
use proconio::input;

#[allow(unused_imports)]
use proconio::marker::{Bytes, Chars, Usize1};
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
#[allow(unused_imports)]
use std::ops::*;

#[derive(Clone, Debug, Default)]
struct Struct;

//#[proconio::fastout]
fn main() {
    input! {
        n: usize,
        m: usize,
    }

    let al = 0;
    let ah = (n - 1) / 2;
    let bl = n / 2 + 1;
    let bh = n - 1;

    let mut v = Vec::new();
    for i in 0..=m / 2 {
        v.push((al + i, ah - i));
        v.push((bl + i, bh - i));
    }

    for ab in v.iter().take(m) {
        println!("{} {}", ab.0 + 1, ab.1 + 1);
        //println!("{} {} {} ", ab.0 + 1, ab.1 + 1, (ab.1-ab.0+n)%n);
    }
}


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

int main() {
    long long ans;
    int n, tmp;
    vector<int> a;
    cin >> n;
    for(int i=0; i<n; i++)
    {
        cin >> tmp;
        a.push_back(tmp);
    }
    // sort
    sort(a.begin(), a.end(), greater<int>());
    ans = a[0];
    for(int i=2; i<n; i++)
    {
        ans += a[i/2];
    }
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 4244
#include<bits/stdc++.h>
#define ll long long int
#define M 1000000007
#define mod 998244353
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pi pair<ll,ll>
using namespace std;
const ll N=250001;

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

    string s;
    cin>>s;
    for(int i=1;i<4;++i)
    {
        if(s[i]==s[i-1])
        {
            cout<<"Bad";return(0);
        }
    }
    cout<<"Good";

	return(0);
}


Measured memory_bytes: 256
/*Author : Hrishi*/

/*When I wrote this, only God and I understood what I was doing.
Now, only God knows.*/

#include <bits/stdc++.h>

#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll> 
#define PB push_back
#define F(i,L,R) for(auto i=L; i<R ;i++)
#define FR(i,L,R) for(auto i=R-1;i>=L;i--)
#define show(x) cout<<(#x)<<" is "<<(x)<<"\n";
#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M 1000000007

using namespace std;

vl val(101,0);
vi w(101);
vector<vl> dp(101,vl(1e5 + 1,0));

int main() 
{
	int test;
//	cin>>test;/
//	while(test--)
	{
	    int n,wt;
	    cin>>n>>wt;
	    F(i,0,n)
	        cin>>w[i]>>val[i];
        F(i,(w[0]),(wt+1))
            dp[0][i] = val[0];
        F(i,1,n)
        {
            F(j,1,wt+1)
            {
                if(j>=w[i])
                {
                    dp[i][j] = max(dp[i-1][j-w[i]] + val[i], dp[i-1][j]);
                }
                else
                    dp[i][j] = dp[i-1][j];
            }
        }
	cout<<dp[n-1][wt]<<"\n";    
    	    
	}

}




Measured memory_bytes: 80256
#include <iostream>
using namespace std;
int main()
{
    int a,b,c,d;
    while(cin>>a>>b>>c>>d)
    {
        if(d<=a||b<=c){cout<<0<<endl;continue;}
        if(c>=a)
        {
            if(d>=b)
            {
                cout<<b-c<<endl;
            }
            else
            {
                cout<<d-c<<endl;
            }
        }
        else
        {
            if(d>=b)
            {
                cout<<b-a<<endl;
            }
            else
            {
                cout<<d-a<<endl;
            }
        }

    }
}


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

int main(){
    int a, b;
    cin >> a >> b;
    int d = a / b;
    int r = a % b;
    double f = 1.0 *a / b;
    
    cout << d << " "  << r  << " ";
    cout << fixed << f << endl;
return 0;
}
    

Measured memory_bytes: 3216
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const LL mod=1000000007;
const LL LINF=1LL<<62;
const int INF=1<<30;
int dx[]={1,0,-1,0,1,-1,1,-1};
int dy[]={0,1,0,-1,1,-1,-1,1};


int main(){
    int a,b;cin >> a >> b;
    cout << setprecision(30) << fixed << 1. * a * b / (a + b) << endl;
    return 0;
}


Measured memory_bytes: 256
//
// Created by ryo on 2019/11/17.
//

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
using namespace std;

typedef long long ll;

#define INF 10e17
#define rep(i,n) for(long long i=0; i<n; i++)
#define repr(i,n,m) for(long long i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<long long>())
#define debug(x) std::cerr << (x) << std::endl;
#define roll(x) for (auto&& itr : x) { debug(itr); }

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

const ll MAX = 1000100;

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

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

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

    ll x, y;
    cin >> x >> y;

    COMinit();

    if ((x + y) % 3 != 0) {
        cout << 0 << endl;
    } else {
        ll t = (-x + 2 * y) / 3;
        ll s = (2 * x - y) / 3;

    //    cout << t << " " << s << endl;

        if (t < 0 || s < 0) {
            cout << 0 << endl;
            return 0;
        }

        cout << COM(t + s, t) << endl;
    }

}

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

#define pb push_back

struct point
{
	int r,v;
	bool operator < (const point& that) const
	{
		return this->v < that.v;
	}
};

struct edge
{
	int to,fr,val;
	bool operator < (const edge& that) const
	{
		return this->val < that.val;
	}
	edge(int _to,int _fr,int _val):to(_to),fr(_fr),val(_val){}
};

int N;
point a[100010],b[100010];
vector<edge> e;

int father[100010];
int FIND(int aa)
{
	if(father[aa]!=aa) father[aa]=FIND(father[aa]);
	return father[aa];
}

int main()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++)
	{
		scanf("%d%d",&a[i].v,&b[i].v);
		a[i].r=b[i].r=i;
	}
	sort(a+1,a+1+N);
	for(int i=1;i<N;i++)
	{
		e.pb(edge(a[i].r,a[i+1].r,a[i+1].v-a[i].v));
	}
	
	for(int i=1;i<=N;i++)
	{
		a[i]=b[i];
	}
	sort(a+1,a+1+N);
	for(int i=1;i<N;i++)
	{
		e.pb(edge(a[i].r,a[i+1].r,a[i+1].v-a[i].v));
	}
	
	sort(e.begin(),e.end());
	
//	for(auto i:e)
//	{
//		cout<<"EDGES: "<<i.fr<<" "<<i.to<<" "<<i.val<<endl;
//	}
	
	for(int i=1;i<=N;i++)
	{
		father[i]=i;
	}
	
	int ans=0;
	for(int i=0;i<e.size();i++)
	{
		int& aa=e[i].to;
		int& bb=e[i].fr;
		int& vv=e[i].val;
		int ra=FIND(aa);
		int rb=FIND(bb);
		if(ra!=rb)
		{
			father[ra]=rb;
//			cout<<"link:::"<<vv<<endl;
//			cout<<"father:";
//			for(int i=1;i<=N;i++) cout<<father[i]<<" ";
//			cout<<endl;
			ans+=vv;
		}
	}
	cout<<ans;
	return 0;
}


Measured memory_bytes: 6388
#pragma GCC target ("avx2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")
#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
const ll MOD = /*1'000'000'007LL;*/ 998'244'353LL;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
const int dx[4]={ 1,0,-1,0 };
const int dy[4]={ 0,1,0,-1 };

struct UnionFind{
private:
    vector<int> par;
    vector<int> siz;
public:
    void init(int N){
        par.resize(N);
        siz.resize(N);
        for(int i=0; i<N; i++) par[i] = i;
        for(int i=0; i<N; i++) siz[i] = 1;
    }
    void unite(int a, int b){
        int rootA = root(a);
        int rootB = root(b);
        if(rootA == rootB) return;
        if(siz[rootA] < siz[rootB]) swap(rootA, rootB);
        par[rootB] = rootA;
        siz[rootA] += siz[rootB];
    }
    int root(int a){
        if(par[a] == a) return a;
        return par[a] = root(par[a]);
    }
    bool same(int a, int b){
        return root(a) == root(b);
    }
    int size(int a){
        return siz[root(a)];
    }
};

int N;
pair<int, int> BA[100000];
pair<int, int> A[100000];
UnionFind uf;
int sum[100000] ={};

signed main(){
    cin >> N;
    rep(i, N) cin >> BA[i].second;
    rep(i, N) cin >> BA[i].first;
    sort(BA, BA+N);
    rep(i, N){
        A[i] ={ BA[i].second, i };
    }
    sort(A, A+N);

    rep(i, N){
        if(BA[i].first < A[i].first){
            cout << "No" << endl;
            return 0;
        }
    }

    uf.init(N);
    rep(i, N){
        uf.unite(i, A[i].second);
    }
    int cnt = 0;
    rep(i, N){
        if(uf.root(i) == i) cnt += uf.size(i)-1;
    }
    if(cnt <= N-2){
        cout << "Yes" << endl;
        return 0;
    }

    for(int i=1; i<N; i++){
        sum[i] = sum[i-1];
        if(BA[i-1].first < A[i].first){
            sum[i]++;
        }
    }
    rep(i, N){
        if(A[i].second <= i){
            if(A[i].first <= BA[A[i].second].first){
                cout << "Yes" << endl;
                return 0;
            }
        }
        else{
            if(sum[A[i].second] - sum[i] == 0){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
}

Measured memory_bytes: 5856
import java.util.*;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();
		char[][] field = new char[h][];
		for (int i = 0; i < h; i++) {
			field[i] = sc.next().toCharArray();
		}
		int count = 0;
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (field[i][j] == '#') {
					count++;
					if (i == 0 && j == 0) {
						
					} else if ((i != 0 && field[i - 1][j] == '#') ^ (j != 0 && field[i][j - 1] == '#')) {
						
					} else {
						System.out.println("Impossible");
						return;
					}
					if (i == h - 1 && j == w - 1) {
						
					} else if ((i != h - 1 && field[i + 1][j] == '#') ^ (j != w - 1 && field[i][j + 1] == '#')) {
						
					} else {
						System.out.println("Impossible");
						return;
					}
				}
			}
		}
		if (count == h + w - 1) {
			System.out.println("Possible");
		} else {
			System.out.println("Impossible");
		}
	}
}


Measured memory_bytes: 23124
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#define N 601000
typedef long long ll; 
template<typename T> inline void read(T &x) { 
  x = 0; char  c = getchar();
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) { x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); }
}
using namespace std;
const int P = 924844033;
const int G = 5;
int Gi; 
inline ll quickpow(ll x, int k) {
  ll res = 1;
  while (k) {
    if (k & 1)  res = res * x % P;  
    x = x *x  % P;
    k >>= 1;
  }
  return res;
}
int n;
struct edge{
  int nxt, to; 
}e[N << 1]; 
int head[N], ecnt;
inline void addedge(int from, int to) {
  e[++ecnt] = (edge){head[from], to};
  head[from] = ecnt;
}

int siz[N], dep[N], fa[N];
void dfs_son(int cur, int faa) {
  siz[cur] = 1, fa[cur] = faa;
  for (int i = head[cur]; i; i = e[i].nxt) {
    int to = e[i].to; if (to == faa)  continue;
    dfs_son(to, cur);
    siz[cur] += siz[to];
  }
}

int cnt[N];
ll f[N], g[N], A[N], ans[N];
int limi, L, r[N];
inline void ntt(ll *a, int type) {
  for (int i = 1; i < limi; ++i)
    if (i < r[i]) swap(a[i], a[r[i]]);
  for (int i = 1; i < limi; i <<= 1) {
    ll T = quickpow(type == 1 ? G : Gi, (P - 1) / (i << 1));
    for (int j = 0; j < limi; j += (i << 1)) {
      ll t = 1;
      for (int k = 0; k < i; ++k, t = t * T % P) {
        ll nx = a[j + k], ny = t * a[j + k + i] % P;
        a[j + k] = (nx + ny) % P;
        a[j + k + i] = (nx - ny + P) % P;
      }   
    }   
  }
  if (type == -1) {
    ll inv = quickpow(limi, P - 2); 
    for (int i = 0; i < limi; ++i)  a[i] = a[i] * inv % P;
  }
}

ll jie[N], jieni[N];
inline ll get_c(int n, int m) {
  if (n < 0 || m < 0 || n - m < 0)  return 0;
  return jie[n] * jieni[m] % P * jieni[n - m] % P;
}
inline void work() {
  limi = 1;
  while (limi <= n + n + 2) limi <<= 1, ++L;
  for (int i = 0; i <= limi; ++i)
    r[i] = (r[i >> 1] >> 1) | ((i & 1) << (L - 1));
  ntt(f, 1), ntt(g, 1); 
  for (int i = 0; i < limi; ++i)  A[i] = f[i] * g[i] % P;
  ntt(A, -1);
//  for (int i= 0; i <= n; ++i)	printf("A(yuan)[%d] = %lld\n", i, A[n - i]);
  for (int k = 1; k <= n; ++k) {
    ll ans = (1ll * n * get_c(n, k) % P - jieni[k] * A[n - k] % P) % P;
//    printf("%d * %lld - %lld * %lld = \n", n, get_c(n, k), jie[k], A[n - k]);
    printf("%lld\n", (ans % P + P) % P); 
  }
}

inline void init() {
  jie[0] = jieni[0] = 1;
  int up = n + 10; 
  for (int i = 1; i <= up; ++i) jie[i] = jie[i - 1] * i % P;
  jieni[up] = quickpow(jie[up], P - 2); 
  for (int i = up - 1; i; --i)  jieni[i] = jieni[i + 1] * (i + 1) % P;
  Gi = quickpow(G, P - 2); 
}

int main() {
  read(n); init();
  for (int i = 1; i < n; ++i) {
    int u, v; read(u), read(v); addedge(u, v), addedge(v, u); 
  }
  dfs_son(1, 0); 
  for (int i = 2; i <= n; ++i) {
    ++cnt[siz[i]], ++cnt[n - siz[i]];
  }
  for (int i = 0; i <= n; ++i)  f[i] = 1ll * cnt[n - i] * jie[n - i] % P;
  for (int i = 0; i <= n; ++i)  g[i] = jieni[i];
//  for (int i = 0; i <= n; ++i)	printf("f[%d] = %lld, g = %lld\n", i, f[i], g[i]);
  work();
  return 0;
}

/*
3
1 2
2 3
//3 7 3
*/

Measured memory_bytes: 34776
#include <iostream>
#include <cstdio>
#include <cstdint>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
typedef	long long ll;

int main() {
	ll a;
	cin >> a;
	cout << (a / 2) * (a - a / 2) << endl;
}


Measured memory_bytes: 256
import * as fs from "fs";

export default class Queue<T> {
	private _in: Array<T>;
	private _out: Array<T>;

	get length(): number {
		return this._in.length + this._out.length;
	}

	constructor(iterable?: Iterable<T>) {
		this._in = iterable === undefined ? new Array<T>() : [...iterable];
		this._out = new Array<T>();
	}

	private _fix() {
		this._out = this._in.reverse().concat(this._out);
		this._in = new Array<T>();
	}

	push(value: T): void {
		this._in.push(value);
	}

	shift(): T | undefined {
		if (this._out.length == 0) this._fix();
		return this._out.pop();
	}

	toArray(): Array<T> {
		this._fix();
		return this._out.slice().reverse();
	}
}

let input = (fs.readFileSync("/dev/stdin", "utf8") as string).split("\n");
const [n, k, l] = input[0].split(" ").map((x: string): number => +x);

const ways: Array<Array<number>> = [];
for (let i = 0; i < n; i++) {
	ways.push([]);
}

for (let i = 1; i < 1 + k; i++) {
	const [p, q] = input[i].split(" ").map((x: string): number => +x);
	ways[p - 1].push(q - 1);
	ways[q - 1].push(p - 1);
}

const rails: Array<Array<number>> = [];
for (let i = 0; i < n; i++) {
	rails.push([]);
}

for (let i = 1 + k; i < 1 + k + l; i++) {
	const [r, s] = input[i].split(" ").map((x: string): number => +x);
	rails[r - 1].push(s - 1);
	rails[s - 1].push(r - 1);
}

const findIslands = (n: number, g: Array<Array<number>>): Array<number> => {
	const result: Array<number> = new Array(n);
	const queue: Queue<number> = new Queue();
	const checked: Array<boolean> = new Array(n).fill(false);
	const bfs = (node: number, island_id: number) => {
		if (checked[node]) return;
		result[node] = island_id;
		checked[node] = true;
		for (const to of g[node]) {
			queue.push(to);
		}
	};
	let island_id = 0;
	for (let i = 0; i < n; i++) {
		if (checked[i]) continue;
		queue.push(i);
		while (queue.length > 0) {
			bfs(queue.shift()!, island_id);
		}
		island_id += 1;
	}
	return result;
};

const w_islands = findIslands(n, ways);
const r_islands = findIslands(n, rails);

const counts = new Map();
for (let i = 0; i < n; i++) {
	const label = w_islands[i] + "|" + r_islands[i];
	if (counts.has(label)) {
		counts.set(label, counts.get(label) + 1);
	}
	else {
		counts.set(label, 1);
	}
}

let result = "";
for (let i = 0; i < n; i++) {
	result += counts.get(w_islands[i] + "|" + r_islands[i]);
	result += " ";
}
console.log(result);


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

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long

void solve()
{
    int n;
    cin >> n;
    int a[n][3];

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

    int dp[n][3] = {0};

    for(int i = 1; i < n; i++)
    {
        dp[i][0] = max(dp[i-1][1]+a[i-1][1],dp[i-1][2]+a[i-1][2]);
        dp[i][1] = max(dp[i-1][0]+a[i-1][0],dp[i-1][2]+a[i-1][2]);
        dp[i][2] = max(dp[i-1][0]+a[i-1][0],dp[i-1][1]+a[i-1][1]);
    }

    dp[n-1][0] += a[n-1][0];
    dp[n-1][1] += a[n-1][1];
    dp[n-1][2] += a[n-1][2];

    cout << max(dp[n-1][0], max(dp[n-1][1],dp[n-1][2]));
}

int main()
{
    fastio;
    solve();
}

Measured memory_bytes: 2560
///Bankai: Getsuga Tenshou
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
ll a[5*100005],kq;
string s;
vector<int> g;
void xuli()
{
    s=" "+s;
    memset(a,-1,sizeof(a));
    for(int i=1;i<=s.size();i++)
    {
        if(s[i]=='>' && s[i+1]=='<')
        {
            a[i]=0;
            g.push_back(i);
        }
        if(s[i]=='<' && s[i-1]!='<')
        {
            a[i-1]=0;
            g.push_back(i-1);
        }
        if(s[i]=='>' && s[i+1]!='>')
        {
            a[i]=0;
            g.push_back(i+1);
        }
    }
    for(int i=0;i<g.size();i++)
    {
        int tg=g[i];
        while(tg>=0 && s[tg]=='>' && s[tg-1]=='>')
        {
            a[tg-1]=a[tg]+1;
            tg--;
        }
        int tg2=g[i];
        while(tg2<s.size() && s[tg2+1]=='<' && s[tg2+2]=='<')
        {
            a[tg2+1]=a[tg2]+1;
            tg2++;
        }
    }
    kq=0;
    for(int i=0;i<s.size();i++)
    {
        if(a[i]==-1) a[i]=max(a[i-1],a[i+1])+1;
        kq+=a[i];
    }
    cout<<kq;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("agc040.inp","r",stdin);
    //freopen("agc040.out","w",stdout);
    cin>>s;
    xuli();
    return 0;
}


Measured memory_bytes: 7752
/*
    ALWAYS REMMEMBER:
        NEVER GIVE UP !
        DON'T MESS WITH ME !!!
        "" THE EXPERT IN ANYTHING WAS ONCE A BEGINNER ""
*/

#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long int
#define ull unsigned long long int
#define ld long double
#define f(i,a,b) for(ll i=a; i<=b; i++)
#define fi(i,a,b) for(ll i=a; i>=b; i--)
#define fa(x,b) for(auto x:b)
#define TC ll test_case; cin>>test_case; for(ll number=1 ; number <= test_case ; number ++ )
#define vll vector<ll>
#define pb push_back
#define pll pair<ll,ll>
#define mp make_pair
#define ff first
#define ss second
#define sz(a) (ll)(a).size()
#define sp(x) cout << fixed << setprecision(x);
#define ReadFile freopen("input.txt","r",stdin)
#define WriteFile freopen("output.txt","w",stdout)
#define endl "\n"

const ld pi = acos(-1);
const ll M=1e9+7,N=1e7+5,INF=1e18;

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

    if(s[0]=='A' && s[1]=='A' && s[2]=='A')
        cout << "No" << endl;
    else if(s[0]=='B' && s[1]=='B' && s[2]=='B')
        cout << "No" << endl;
    else 
        cout << "Yes" << endl;
}

int32_t main()
{
    FIO
    solve();
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>

using namespace std;

int check(double xa,double ya,double ra,double xb,double yb,double rb){
  double dist = sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb));
  double minr = min(ra,rb);
  if(ra+rb<dist){
    return 0;
  }else{
    if(ra>rb&&dist<ra-rb){
      return 2;
    }else if(ra<rb&&dist<rb-ra){
      return -2;
    }else{
      return 1;
    }
  }
}

int main(){
  int N;
  cin >> N;
  for(int i=0;i<N;++i){
    double xa,ya,ra,xb,yb,rb;
    cin >> xa >> ya >> ra >> xb >> yb >> rb;
    cout << check(xa,ya,ra,xb,yb,rb) << endl;
  }
}

Measured memory_bytes: 3064
#include <stdio.h>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <list>
#include <iterator>
#include <assert.h>
#pragma warning(disable:4996) 
 
typedef long long ll;
#define MIN(a, b) ((a)>(b)? (b): (a))
#define MAX(a, b) ((a)<(b)? (b): (a))
#define LINF 9223300000000000000
#define INF 2140000000
const long long MOD = 1000000007;
using namespace std;

int main(int argc, char* argv[])
{
    int n, Q;
    scanf("%d%d", &n, &Q);

    vector<int> a(n);
    int i;
    for(i=0; i<n; i++) {
        scanf("%d", &a[i]);
    }

    int q;
    for(q=0; q<Q; q++) {
        ll x;
        scanf("%lld", &x);

        ll sum=0;
        ll cnt=0;
        int k=0;
        for(i=0; i<n; i++) {
            while(k<n && sum+a[k]<=x) {
                sum+=a[k];
                k++;
                //printf("%d %d %lld\n", i, k, sum);
            }
            cnt += (k-i);

            sum -= a[i];
            if(i+1<n && i+1>k) {
                sum += a[k];
                k++;
            }
        }
        printf("%lld\n", cnt);
    }


    return 0;
}




Measured memory_bytes: 2844