akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, j, n) for (ll i = j; i < n; i++)
#define all(x) (x).begin(),(x).end()
#define INF (1000000000)
#define MOD (1000000007)

/////////////////////////////////////////////////////////

void Main(){
  ll N; cin >> N;
  vector<ll> a(N);
  rep(i, 0, N) cin >> a[i];

  ll res = INF;
  rep(y, -100, 101){
    ll sum = 0;
    rep(i, 0, N) sum += (a[i] - y) * (a[i] - y);
    if(sum < res) res = sum;
  }
  
  cout << res << endl;
}

/////////////////////////////////////////////////////////

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

  Main();
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

long long s(long long n) {
    long long ans = 0;

    while (n) {
        ans += n % 10;
        n /= 10;
    }

    return ans;
}

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

    long long n = 1, d = 1;
    cout << 1 << endl;

    for (int i = 1; i < k; i++) {
        if (s(n+d) * (n+d*10) < s(n+d*10) * (n+d)) {
            d *= 10;
        }
        n += d;
        cout << n << endl;
    }
}


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

int main(){
  int t,m;
  string str,com,arg;

  cin >> t;
  cin.ignore();
  while(t--){
    getline(cin,str);
    cin >> m;

    int pos = 0;
    for(int i=0;i<m;i++){
      cin >> com;
      cin.ignore();
      getline(cin,arg);
      //cout << com << " " << arg <<endl;
      if(com == "forward"){
	if(arg == "char"){
	  if(pos<(int)str.size())pos++;	  
	}else{
	  while(pos<(int)str.size() && str[pos]==' ')pos++;
	  while(pos<(int)str.size() && str[pos]!=' ')pos++;
	}
      }
      if(com == "backward"){
	if(arg == "char"){
	  if(pos)pos--;
	}else{
	  while(pos && str[pos-1]==' ')pos--;
	  while(pos && str[pos-1]!=' ')pos--;
	}
      }
      if(com == "delete"){
	if(arg == "char"){
	  if(pos!=(int)str.size())str.erase(str.begin()+pos);
	}else{
	  bool f=false;
	  int d = 0;
	  while(pos+d<(int)str.size()){
	    if(str[pos+d]!=' '){
	      f=true;
	      break;
	    }
	    d++;
	  }
	  if(f){
	    while(pos<(int)str.size() && str[pos]==' ')str.erase(str.begin()+pos);
	    while(pos<(int)str.size() && str[pos]!=' ')str.erase(str.begin()+pos);
	  }
	}
      }
      if(com == "insert"){
	for(int j=1;j<(int)arg.size()-1;j++){
	  str.insert(str.begin()+pos++,arg[j]);
	}
      }
      //cout << pos << " " << str << endl;
    }
    if(pos==(int)str.size())str.push_back('^');
    else str.insert(str.begin()+pos,'^');
    cout << str << endl;
  }
}

Measured memory_bytes: 0
import sys 
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
ans = 0
for i in range(1,N+1):
    if i % 3 == 0 or i % 5 == 0:
        continue
    ans += i
print(ans)

Measured memory_bytes: 27076
#include<iostream>
using namespace std;
int main() {
  int w,a,b; cin >> w >> a >> b;
  if(b>=a && b<=a+w){
    cout << 0 << endl;
  }else if(b>a+w){
    cout << b-a-w << endl;
  }else if(b<a-w){
    cout << a-b-w << endl;
  }else if(b>=a-w && b<=a){
    cout << 0 << endl;
  }
  return 0;
}

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

// #define ANS  //for answer
#define CMP  //for compe

#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) v.begin(), v.end()
#define nv(x) #x,(x)
#define ncv(x) #x,":",(x)
#define ncvc(x) #x,":",(x),","
using ll = long long;
void pPRINT(std::ostream& ost) {}
template <class T, class... U>void pPRINT(std::ostream& ost,const T t,const U... u) {ost<<t<<" ";pPRINT(ost, u...);}
template <class... T>void PRINT(const T... t) {pPRINT(std::cout, t...);}
template <class... T>void PRINTl(const T... t){pPRINT(std::cout,t...);std::cout<<"\n";}
template <class T>void PRINTa(const T* const t,const ll size){REP(i,size)PRINT(t[i]);PRINTl();}
template <class T>void PRINTal(const T* const t,const ll size){REP(i,size)PRINTl(i,":",t[i]);}
#ifdef CMP
using namespace std;
#else
#endif
#ifndef DBG
#define DEBUG(...)
void init(){}
#else
#define DEBUG(...) PRINT("##DEBUG##","file :",__FILE__,", line :",__LINE__,"[");PRINT(__VA_ARGS__);PRINTl("]");
void init(){
  cin.tie(0);
  ios::sync_with_stdio(false);
}
#endif
#ifdef ANS
#else
#endif

void solve();

int main(int argc, char *argv[]) {

  init();
  DEBUG();
  solve();

  return 0;
}

void solve(){

  DEBUG("SOLVE START");
  ll n,m,X,Y;cin>>n>>m>>X>>Y;
  ll x[n];REP(i,n)cin>>x[i];
  ll y[m];REP(i,m)cin>>y[i];
  ll mxx=X,mny=Y;
  REP(i,n)mxx=max(mxx,x[i]);
  REP(i,m)mny=min(mny,y[i]);
  if(mxx<mny)PRINT("No");PRINTl("War");



}

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

void Main() {
    // input
    int N;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        int A;
        cin >> A;
        if (A % 2 == 0) {
            if (!((A % 3 == 0) || (A % 5 == 0))) {
                cout << "DENIED";
                return;
            }
        }
    }

    cout << "APPROVED";
    


    // translate


    // output

}

int main() {
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 3612
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int n,k; cin >>n>>k;
  string s;cin>>s;
  for (int i=0;i<n;i++){
    if (i== k-1) cout << (char)tolower(s[i]);
    else cout << s[i];
  }
  cout << endl;
}


Measured memory_bytes: 256
let N = Int(readLine()!)!
let AN = readLine()!.split(separator: " ").compactMap { Int($0) }
let mod = 1000000007

var sumList: [Int] = []
for i in 0..<N-1 {
    let element = ((sumList.last ?? 0) + AN[N-i-1]) % mod
    sumList.append(element)
}

var result = 0
for i in 0..<N-1 {
    result += AN[i] * sumList[N-i-2]
    result %= mod
}
print(result)


Measured memory_bytes: 21260
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

int n, l, q;
int x[100010];
int d[100010];
int u[21][100010];

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    rep(i, 0, n) cin >> x[i];
    cin >> l >> q;
    int sum = 0, right = 0;
    for(int left = 0; left < n; left++){
        while(x[right] - x[left] <= l && right < n){
            right++;
        }
        d[left] = right - 1;
        // cout << left << " " << right << " " << d[left] << endl;
    }
    rep(i, 0, n) u[0][i] = d[i];
    rep(i, 0, 20){
        rep(j, 0, n){
            u[i + 1][j] = u[i][u[i][j]];
        }
    }
    rep(i, 0, q){
        int a, b;
        cin >> a >> b;
        a--; b--;
        if(a > b) swap(a, b);
        int now = a;
        int ans = 0;
        rep(k, 0, 30){
            // cout << now << endl;
            rep(j, 0, 20){
                if(u[j][now] >= b){
                    if(j != 0){
                        now = u[j - 1][now];
                        ans += pow(2, j - 1);
                    }else{
                        ans += 1;
                        k = 114514;
                    }
                    break;
                }
            }
        }
        cout << ans << endl;
    }
}

Measured memory_bytes: 18816
// C.

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>

using namespace std;

static const int MOD = 1000000007;

int main(int argc, char *argv[]) {
	int n, m;
	cin >> n >> m;
	vector<int> broken(100002), dp(n + 2);
	for (int i = 0; i < m; ++i) {
		int a;
		cin >> a;
		broken[a] = 1;
	}
	dp[0] = 1;
	for (int i = 0; i < n; ++i) {
		if (dp[i] && !broken[i + 1]) {
			dp[i + 1] += dp[i];
			dp[i + 1] %= MOD;
		}
		if (dp[i] && !broken[i + 2]) {
			dp[i + 2] += dp[i];
			dp[i + 2] %= MOD;
		}
	}
	cout << dp[n] << endl;
	return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>

int main(void)

{


         int a,b;


         scanf("%d %d",&a,&b);


         if(a<b)


         {


                     printf("a < b\n");


         }


         if(a>b)


         {


                     printf("a > b\n");


         }


         if(a==b)


         {


                     printf("a == b\n");


         }


         return 0;


}

Measured memory_bytes: 580
#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i= (a); i < (b); ++i)
typedef long long ll;
typedef pair<int,int> P;
const int INF = 100100100;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;
int main() { ll N;
  cin >> N;
  ll n = N,ans=0;

  while(0<n){
    ans += n % 10;
    n /= 10;
  }
  if(N%ans==0){
    puts("Yes");
  }else{
    puts("No");
  }
}

Measured memory_bytes: 256
n,m = map(int,input().split())
cand_1 = []
cand_n = []
for i in range(m):
  a,b = map(int,input().split())
  if a == 1:
    cand_1.append(b)
  elif b == n:
    cand_n.append(a)
flag = set(cand_1) & set(cand_n)

print('POSSIBLE' if flag else 'IMPOSSIBLE')

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

long long MOD = 1e9+7;
int MAX_INT = 1e9;

// 最大公約数
long long gcd(long long a, long long b){
  if(b == 0) return a;
  return gcd(b, a % b);
}
// 最小公倍数
long long lcm(long long a, long long b) {
  return a / gcd(a, b) * b;
}

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

  int n;
  cin >> n;
  vector<string> S(n);
  for (int i = 0; i < n; ++i) {
    cin >> S[i];
  }

  vector<int> alphabet(26, 0);
  for(int i = 0; i < n; ++i) {
    for(int j = 'a'; j <= 'z'; ++j) {
      int cnt = 0;
      for(int k = 0; k < S[i].size(); ++k) {
        if(S[i][k] == (char)j) {
          if(i == 0) {
            alphabet[j-'a']++;
          }
          else{
            cnt++;
          }
        }
      }
      // cout <<j-'a' << (char)j << " : " << alphabet[j-'a'] << " : " << cnt << endl;
      if(i != 0) {
        alphabet[j-'a'] = min(alphabet[j-'a'], cnt);
      }
    }
  }

  for(int i = 0; i < alphabet.size(); ++i) {
    for(int j = 0; j < alphabet[i]; ++j) {
      cout << (char)(i + 'a');
    }
    // cout << (char)(i + 'a') << ": " << alphabet[i] << endl;
  }
  cout << endl;

  return 0;
}


Measured memory_bytes: 3620
//
//  main.cpp
//  ABC087B_coins
//
//  Created by 岡本 朋大 on 2019/06/01.
//  Copyright © 2019年 岡本　朋大. All rights reserved.
//

#include <iostream>
#include <string>
#include <fstream>

using namespace std;

int main(){
    int count = 0;
    int a,b,c,x;
    cin >> a >> b >> c >> x;
    for(int i = 0; i<= a; i++){
        for(int j = 0; j <= b; j++){
            for(int k= 0; k<= c; k++){
                if(x == 500*i+100*j+50*k) count++;
            }
        }
    }
    cout << count << endl;
}


Measured memory_bytes: 256
R,C = map(int,input().split())
sy,sx = 1,1
gy,gx = R,C
maze = [list(input()) for _ in range(R)]
mx = 0
for m in maze:
  mx += m.count('.')


sx,sy = sx-1, sy-1
gx,gy = gx-1, gy-1

def bfs(R,C,sy,sx,gy,gx,maze):
    from collections import deque
    import numpy as np
    INF = np.inf
    visited = [[INF]*C for _ in range(R)]
    visited[sy][sx] = 0
    que = deque([(sy,sx)])
    while que:
        y,x = que.popleft()
        for i,j in ((1,0),(0,1),(-1,0),(0,-1)):
            ny,nx = y+i, x+j
            if 0<=ny<R and 0<=nx<C:
                if (maze[ny][nx]!='#') and visited[ny][nx]==INF:
                    visited[ny][nx] = visited[y][x] + 1
                    que.append((ny,nx))
    if visited[gy][gx]!=INF:
      return visited[gy][gx]
    else:
      return -1

ans = bfs(R,C,sy,sx,gy,gx,maze)
print(mx-ans-1 if ans!=-1 else -1)

Measured memory_bytes: 12496
import heapq
N = int(input())
AB = [[int(_) for _ in input().split()] for _ in range(N - 1)]
G = {}
for a, b in AB:
    a -= 1
    b -= 1
    #0-indexed
    G[a] = G.get(a, set())
    G[b] = G.get(b, set())
    G[a].add(b)
    G[b].add(a)


def dijkstra_stack(i):
    D = [-1] * N
    D[i] = 0
    stack = [i]
    while True:
        i = stack.pop(0)
        update = False
        for j in G[i]:
            if D[j] == -1:
                update = True
                D[j] = D[i] + 1
                stack += [j]
        if not stack:
            break
    return D


D_Fennec = dijkstra_stack(0)
D_Snuke = dijkstra_stack(N - 1)

f = 0
s = 0
for i in range(N):
    if D_Fennec[i] <= D_Snuke[i]:
        f += 1
    else:
        s += 1
if f > s:
    print('Fennec')
else:
    print('Snuke')


Measured memory_bytes: 63844
#include <bits/stdc++.h>
#include "unistd.h"
using namespace std;
#define WA cout<<"char134217728";exit(0)
#define RE throw
#define TLE sleep(1000)
#define FOR(i,a,b) for(int i=(a),i##formax=(b);i<i##formax;i++)
#define FORR(i,a,b) for(int i=(a),i##formax=(b);i>=i##formax;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define pcnt __builtin_popcount
#define sz(x) (int)(x).size()
#define maxs(x,y) x=max(x,y)
#define mins(x,y) x=min(x,y)
#define show(x) cout<<#x<<" = "<<x<<endl;
#define all(a) (a.begin()),(a.end())
#define each(it,c) for(__typeof((c).begin()) it=(c).begin();it!=(c).end();it++)
#define perm(c) sort(all(c));for(bool c##p=1;c##p;c##p=next_permutation(all(c)))
#define uniq(v) sort(all(v));v.erase(unique(all(v)), v.end());
#define bit(n) (1LL<<(n))
#define randInt(l,r) (uniform_int_distribution<ll>(l,r)(rnd))
#define randDouble(l,r) (uniform_real_distribution<double>(l,r)(rnd))
#define dout(d) printf("%.12f\n",d)

typedef long long ll;
typedef __int128_t lll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
template<class T>using V=vector<T>;
template<class T>using VV=V<V<T>>;
template<class T,class Y>ostream& operator<<(ostream& o,const pair<T,Y>& p){return o<<"("<<p.fi<<", "<<p.se<<")";}
template<typename A,size_t N,typename T>void Fill(A (&array)[N],const T&v){fill((T*)array,(T*)(array+N),v);}
lll gcd(lll a,lll b,lll &x,lll &y){if(!b){x=1;y=0;return a;}lll d=gcd(b,a%b,y,x);y-=a/b*x;return d;}
ll gcd(ll a,ll b){lll x=0,y=0;return gcd(a,b,x,y);}
ll modInv(ll a,ll m){lll x,y;gcd(a,m,x,y);return (x%m+m)%m;}
ll modPow(lll a,lll n,ll m){if(!a)return a;lll p=1;for(;n>0;n>>=1,a=a*a%m)if(n&1)p=p*a%m;return(ll)p;}
bool isPrime(ll n){if(n<2||n%2==0)return n==2;lll t=n-1,d=t/(t&-t);for(lll a:{2,325,9375,28178,450775,9780504,1795265022})if(a%n){for(t=d,a=modPow(a,t,n);t!=n-1&&a!=1&&a!=n-1;a=a*a%n,t=t*2%n);if(a!=n-1&&t%2==0)return 0;}return 1;}
const int IINF = 1e9+6;
const ll LINF = 1e18;
const int MOD = 1e9+7;
const double PI = acos(-1);
const double EPS = 1e-10;
static random_device rd;
static mt19937 rnd(rd());

const int N = 1e5;
int n;
ll m[26];
char c;
main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> n;
  FOR(i, 0, n){
    cin >> c;
    m[c-'a']++;
  }
  ll ans = 1;
  FOR(i, 0, 26) ans = ans * (m[i]+1) % MOD;
  cout << (ans + MOD - 1) % MOD << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int x[] = new int[n];
		int y[] = new int[n];
		int d[] = new int[n];
		for (int i = 0; i < n; i++)
			x[i] = sc.nextInt();
		for (int i = 0; i < n; i++)
			y[i] = sc.nextInt();
		double p1 = 0, p2 = 0, p3 = 0, pm = 0;
		for (int i = 0; i < n; i++) {
			d[i] = Math.abs(x[i] - y[i]);
			p1 += d[i];
			p2 += d[i] * d[i];
			p3 += d[i] * d[i] * d[i];
			if (d[i] > pm) {
				pm = d[i];
			}
		}
		p2 = Math.sqrt(p2);
		p3 = Math.pow(p3, (1.0 * 1 / 3));
		System.out.println(p1);
		System.out.println(p2);
		System.out.println(p3);
		System.out.println(pm);
	}
}


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

int main()
{
	int N, M;
	cin >> N >> M;
	vector<ll> x(N), y(N), z(N);
	for (int i = 0; i < N; i++) {
		cin >> x[i] >> y[i] >> z[i];
	}
	ll res = 0;
	for (int b1 = 0; b1 < 2; b1++) {
		for (int b2 = 0; b2 < 2; b2++) {
			for (int b3 = 0; b3 < 2; b3++) {
				vector<ll> val(N);
				ll sum = 0;
				for (int i = 0; i < N; i++) {
					val[i] = x[i] + y[i] + z[i];
				}
				sort(val.rbegin(), val.rend());
				for (int i = 0; i < M; i++) {
					sum += val[i];
				}
				res = max(res, sum);
				for (int i = 0; i < N; i++) {
					z[i] = -z[i];
				}
			}
			for (int i = 0; i < N; i++) {
				y[i] = -y[i];
			}
		}
		for (int i = 0; i < N; i++) {
			x[i] = -x[i];
		}
	}
	cout << res << endl;
	return 0;
}


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

int main() {
    ll n;
    cin>>n;
    V a(n);
    rep(i,n)cin>>a[i];
    if(n%2==1){
        VVV dp(n+1,VV(3,V(2,-1e10)));
        rep(i,n){
            rep(j,3){
                if(i+1==2&&j>0)continue;
                if(i+1==3&&j>1)continue;
                dp[i+1][j][0]=dp[i][j][1];
                if(j>0)dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j-1][0]);
                if(dp[i][j][0]==-1e10){
                    dp[i+1][j][1]=a[i];
                }else{
                    dp[i+1][j][1]=dp[i][j][0]+a[i];
                }
            }
        }
        cout<<max({dp[n][0][0],dp[n][1][0],dp[n][1][1],dp[n][2][1]})<<endl;
    }else{
        VVV dp(n+1,VV(2,V(2,-1e10)));
        rep(i,n){
            rep(j,2){
                if(i+1==2&&j>0)continue;
                dp[i+1][j][0]=dp[i][j][1];
                if(j>0)dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j-1][0]);
                if(dp[i][j][0]==-1e10){
                    dp[i+1][j][1]=a[i];
                }else{
                    dp[i+1][j][1]=dp[i][j][0]+a[i];
                }
            }
        }
        cout<<max({dp[n][0][0],dp[n][0][1],dp[n][1][1]})<<endl;
    }
}


Measured memory_bytes: 43924
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
 
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
 
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
 
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a,x) for (auto& a : x)
#define uid(a, b) uniform_int_distribution<int>(a, b)(rng)
 
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
#define ins insert

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 100001; //check the limits, dummy
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);  

/*#ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r+", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w+", stdout);
#endif  */
	
    int D,T,S;
    cin >>D>>T>>S;
    cout << (S*T>=D ? "Yes" : "No") << '\n';
}
 
// read the question correctly (ll vs int)
// template by bqi343

Measured memory_bytes: 3648
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int INF = (1<<30);
const ll INFLL = (1ll<<60);
const ll MOD = (ll)(1e9+7);

#define l_ength size

void mul_mod(ll& a, ll b){
	a *= b;
	a %= MOD;
}

void add_mod(ll& a, ll b){
	a = (a<MOD)?a:(a-MOD);
	b = (b<MOD)?b:(b-MOD);
	a += b;
	a = (a<MOD)?a:(a-MOD);
}

int main(void){
	int n,m,i,j,ans=-INF;
	string s;
	bool flag;
	cin >> s;
	n = s.l_ength();
	n /= 2;
	for(i=0; i<n; ++i){
		flag = true;
		for(j=0; j<i; ++j){
			if(s[j]!=s[i+j]){
				flag = false;
				break;
			}
		}
		if(flag){
			ans = max(ans,i*2);
		}
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100;
int n;
double v[N];
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> v[i]; 
  }
  sort(v + 1, v + 1 + n);
  for (int i = 2; i <= n; i++) {
    v[i] = (v[i] + v[i - 1])/2;
  }
  printf("%.5lf\n", v[n]);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

#define COUT(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl
template<class T1, class T2> ostream& operator << (ostream &s, pair<T1,T2> P)
{ return s << '<' << P.first << ", " << P.second << '>'; }
template<class T> ostream& operator << (ostream &s, vector<T> P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T> ostream& operator << (ostream &s, vector<vector<T> > P)
{ for (int i = 0; i < P.size(); ++i) { s << endl << P[i]; } return s << endl; }
template<class T> ostream& operator << (ostream &s, set<T> P)
{ for(auto it : P) { s << "<" << it << "> "; } return s << endl; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> P)
{ for(auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s << endl; }


const vector<int> dx = {1, 0, -1, 0};
const vector<int> dy = {0, 1, 0, -1};
const long long INF = 1LL<<60;
int H, W;
vector<string> fi;
long long dp[110][110][3];

long long solve() {
    vector<vector<vector<long long>>> dp(H, vector<vector<long long>>(W, vector<long long>(2, INF)));
    if (fi[0][0] == '#') {
        dp[0][0][1] = 1;
    }
    else {
        dp[0][0][0] = 0;
    }

    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            for (int dir = 0; dir < 4; ++dir) {
                int ni = i + dx[dir], nj = j + dy[dir];
                if (ni < 0 || ni >= H || nj < 0 || nj >= W) continue;
                if (fi[ni][nj] == '#') {
                    chmin(dp[ni][nj][1], dp[i][j][0] + 1);
                    chmin(dp[ni][nj][1], dp[i][j][1]);
                }
                else {
                    chmin(dp[ni][nj][0], dp[i][j][0]);
                    chmin(dp[ni][nj][0], dp[i][j][1]);
                }
            }
        }
    }
    return min(dp[H-1][W-1][0], dp[H-1][W-1][1]);
}

int main() {
    while (cin >> H >> W) {
        fi.resize(H);
        for (int i = 0; i < H; ++i) cin >> fi[i];
        cout << solve() << endl;
    }
}

















Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000


int main(){
	
	int N,K;
	cin>>N>>K;
	
	vector<long long> A(N);
	for(int i=0;i<N;i++)cin>>A[i];
	
	sort(A.begin(),A.end());
	
	long long ans = 0;
	
	for(int i=0;i<max(0,N-K);i++){
		ans += A[i];
	}
	
	cout<<ans<<endl;
	
	
	return 0;
}

Measured memory_bytes: 1792
using System;

namespace AizuOnline
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            var ar = new int[10001];
            var i = 0;
            while (true)
            {
                var x = Convert.ToInt32(Console.ReadLine());
                ar[i] = x;
                i++;
                if (x == 0)
                {
                    break;
                }
            }

            for (int j = 0; j < ar.Length; j++)
            {
                if (ar[j] != 0)
                {
                    Console.WriteLine("Case " + (j + 1) + ": " + ar[j]);
                }
                else
                {
                    break;
                }
            }
            Console.ReadLine();
        }
    }
}

Measured memory_bytes: 9368
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<map>
#include<list>
#include<set>
using namespace std;

int main(){
  int n,ba=0,hito;
  char c[101];
  int h[12];

  while(cin >> n && n){
    ba = 0;
    memset(h,0,sizeof(h));
    //入力
   // scanf("%s",c);
   for(int i=1;i<=100;i++){
     cin >> c[i];
   }
    for(int i=1;i<=100;i++){
      hito = i%n;
      if(hito == 0)hito = n;
      hito-=1;
      if(c[i] == 'M'){ //男
        h[hito]++;
      }else if(c[i] == 'S'){//坊主
        h[hito]++;
        ba += h[hito];
        h[hito]=0;
      }else if(c[i] == 'L'){//姫
        h[hito]++;
        h[hito]+=ba;
        ba = 0;
      }
    }
    sort(h,h+n);
    h[n] = ba;
    for(int i=0;i<=n;i++){
      cout << h[i];
      if(i != n){
        cout <<" ";
      }else{
        cout << endl;
      }
    }


  }

  return 0;
}




Measured memory_bytes: 3148
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define sz(x) (int)(x).size()
#define uni(x) x.erase(unique(rng(x)),x.end())
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
  
int main() {
  int N,M;
  cin >> N >> M;
  vi A(N,-1);
  rep(i,M) {
    int s,c;
    cin >> s >> c;
    s--;
    if(A[s]>=0 && A[s] != c) {
      cout << -1 << endl;
      return 0;
    }
    A[s] = c;
  }
  if(N==1) {
    if(A[0]<=0) {
      cout << 0 << endl;
      return 0;
    } else {
      cout << A[0] << endl;
      return 0;
    }
  }
  bool b = false;
  rep(i,N) {
    if(A[i] < 0) {
      if(b) {
        cout << 0;
      } else {
        b = true;
        cout << 1;
      }
    } else if(A[i]==0) {
      if(!b) {
        cout << -1 << endl;
        return 0;
      } else {
        cout << 0;
      }
    } else {
      b = true;
      cout << A[i];
    }
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 256
//In The Name Of Allah
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define sz(x) (int)(x.size())
#define double long double 
#define fi first
#define se second
#define pii pair<int, int>

signed main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);
  int n;
  cin >> n;
  int a[n];
  vector<int> neg, pos;
  int zero = 0;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (a[i] == 0) zero++;
    else if (a[i] > 0) pos.push_back(a[i]);
    else neg.push_back(a[i]);
  }
  if (sz(pos) > 0) {
    sort(pos.begin(), pos.end());
  }
  if (sz(neg) > 0) {
    sort(neg.rbegin(), neg.rend());
  }
  vector<pii> ans;
  if (sz(neg) == 0 && sz(pos) > 1 && zero > 0) {
    ans.push_back({0ll, pos.back()});
    neg.push_back(-pos.back());
    pos.pop_back();
    zero--;
  }
  if (sz(pos) == 0 && sz(neg) > 1 && zero > 0) {
    ans.push_back({0ll, neg.back()});
    pos.push_back(-neg.back());
    neg.pop_back();
    zero--;
  }
  if (sz(pos) > 0 && sz(neg) > 0) {
    for (int i = 0; i < sz(neg) - 1; i++) {
      ans.push_back({pos[0], neg[i]});
      pos[0] -= neg[i];
    }
    if (sz(pos) == 1) {
      ans.push_back({pos[0], neg.back()});
    } else {
      ans.push_back({neg.back(), pos[0]});
      neg.back() -= pos[0];
      for (int i = 1; i < sz(pos) - 1; i++) {
        ans.push_back({neg.back(), pos[i]});
        neg.back() -= pos[i];
      }
      ans.push_back({pos.back(), neg.back()});
    }
  } else if (sz(pos) == 0 && sz(neg) > 0) {
    if (sz(neg) == 2) {
      ans.push_back({neg[0], neg[1]});
    } else {
      for (int i = 1; i < sz(neg); i++) {
        ans.push_back({neg[0], neg[i]});
        neg[0] -= neg[i];
      }
    }
  } else if (sz(neg) == 0 && sz(pos) > 0) {
    if (sz(pos) == 2) {
      ans.push_back({pos[1], pos[0]});
    } else {
      for (int i = 1; i < sz(pos) - 1; i++) {
        ans.push_back({pos[0], pos[i]});
        pos[0] -= pos[i];
      }
      ans.push_back({pos.back(), pos[0]});
    }
  }
  if (sz(ans) == 0) {
    for (int i = 1; i < zero; i++) {
      ans.push_back({0ll, 0ll});
    }
  } else {
    int adad = ans.back().fi - ans.back().se;
    for (int i = 0; i < zero; i++) {
      ans.push_back({adad, 0ll});
    }
  }
  cout << ans.back().fi - ans.back().se << "\n";
  for (int i = 0; i < sz(ans); i++) {
    cout << ans[i].fi << " " << ans[i].se << "\n";
  }
}



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

"""
参考：https://img.atcoder.jp/abc082/editorial.pdf
　　　https://atcoder.jp/contests/abc082/submissions/3930644
・メモリ節約のため、dictをsetにした。
・さらに使い終わった1つ前はもういらないので消すことにした。
"""

S = input()
X, Y = map(int, input().split())

S2 = []
tmp = 0
# 連続するF毎にまとまるように文字列Sを変形させる
for i in range(len(S)):
    if S[i] == 'F':
        tmp += 1
    # T毎に区切る
    else:
        S2.append(tmp)
        tmp = 0
S2.append(tmp)

# 文字列がFのみだとこの後のDPできないので別処理
if len(S2) == 1:
    if X == S2[0] and Y == 0:
        print('Yes')
    else:
        print('No')
    exit()

# あるかないか分かればいいので、dictじゃなくてsetにする
dpx = [set() for _ in range(len(S2))]
dpy = [set() for _ in range(len(S2))]
# xの初期化：step0は右移動、step1ではそのまま
dpx[0].add(S2[0])
dpx[1].add(S2[0])
# yの初期化：step0は何もなし、step1で上下どちらかに移動
dpy[0].add(0)
dpy[1].add(S2[1])
dpy[1].add(-S2[1])
for i in range(2, len(S2)):
    # 左右に移動する
    for v in dpx[i-1]:
        if i % 2 == 0:
            # 到達可能な位置から+-した位置に送る
            dpx[i].add(v-S2[i])
            dpx[i].add(v+S2[i])
        else:
            # yをやる時はxはそのまま
            dpx[i].add(v)
    # 1つ前は使い終わったので削除
    dpx[i-1] = set()
    # 上下に移動する
    for v in dpy[i-1]:
        if i % 2 == 1:
            dpy[i].add(v-S2[i])
            dpy[i].add(v+S2[i])
        else:
            dpy[i].add(v)
    dpy[i-1] = set()
# 最後のstepでXとYが到達可能ならOK
if X in dpx[len(S2)-1] and Y in dpy[len(S2)-1]:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 158856
import java.util.Scanner;

public class Main {
	static int[][] bingo = new int[3][3];

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int a = Integer.parseInt(sc.next());
		int b = Integer.parseInt(sc.next());
		if(a*b%2==0) {
			System.out.println("Even");
		}else {
			System.out.println("Odd");
		}
	}


}


Measured memory_bytes: 20948
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int N,M;
int A, B, C;
struct edge {
  int to;
  ll t;
  edge(){

  }
  edge(int to,ll t):to(to),t(t){}
};
struct state{
  int id,v,f;
  ll c;
  state(){

  }
  state(int id,int v,int f,ll c):id(id),v(v),f(f),c(c){}
  bool operator<(const state &st) const {
    return c > st.c;
  }
};

ll H[555][55][2];
const ll INF = (ll)(1<<29)*(ll)(1<<29);
vector<edge> G[555];

ll dijk(int v0){
  priority_queue<state> q;
  fill( H[0][0], H[553][51], INF );
  q.push( state(0,v0,0,0) );
  H[0][v0][0] = 0LL;
  while( !q.empty() ){
    state p = q.top(); q.pop();
    if( H[p.id][p.v][p.f] < p.c ) continue;
    for( edge e : G[p.id] ){
      int nv = (A * p.v + B)%C;

      int nf = p.f; if( e.to == N-1 ) nf = 1;
      ll nc = (ll)p.v * e.t + p.c;
      if( H[e.to][nv][nf] > nc ){
        H[e.to][nv][nf] = nc;
        q.push( state( e.to, nv, nf, nc ) );
      }
    }
  }
  ll res = INF;
  for(int i=0;i<=C;i++)
    res = min( res, H[0][i][1] );
  return res;
}

int main(){
  cin >> N >> M;
  for(int i=0;i<M;i++){
    int x,y; ll t;
    cin >> x >> y >> t; --x; --y;
    G[x].emplace_back( y, t );
    G[y].emplace_back( x, t );
  }
  int v0; cin >> v0;
  cin >> A >> B >> C;
  cout << dijk(v0) << endl;
}

Measured memory_bytes: 9656
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
using namespace std;

int main(){
    int N;
    float ans=0;
    cin >> N;
    float v[N];
    for(int i=0;i<N;i++){
        cin >> v[i];
    }
    sort(v,v+N,greater<float>());
    for(int i=0;i<N-2;i++){
        v[i]=v[i]/pow(2,i+1);
        ans+=v[i];
    }
    v[N-2]=v[N-2]/pow(2,N-1);
    ans+=v[N-2];
    v[N-1]=v[N-1]/pow(2,N-1);
    ans+=v[N-1];

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
 
int main() {
  int buff;
  int cnt = 0;
  std::cin >> buff;
  for(int i=0; i<3; i++){
  	cnt += buff%2;
    buff /= 2;
  }
  std::cout << cnt << std::endl;
  return 0;
}

Measured memory_bytes: 256
#!/mnt/c/Users/moiki/bash/env/bin/python

N = int(input())
inp_list = [ list(map(int , input().split()))  for i in range(N)]

A = [ x[0] for x in inp_list]
B = [ x[1] for x in inp_list]

sum_list = [ A[i] + B[i] for i in range(N)] 

w_sum = sorted([ (sum_list[i], A[i], B[i]) for i in range(N)], reverse=True)

takahashi_sum = sum( [x[1] for x in w_sum[::2]] , 0)
aoki_sum =      sum( [x[2] for x in w_sum[1::2]], 0)

print(takahashi_sum - aoki_sum)



Measured memory_bytes: 42136
import java.io.*;
import java.util.*;


public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		Printer pr = new Printer(System.out);

		int a = sc.nextInt();
		int b = sc.nextInt();

		if (a <= 0 && b >= 0) {
			pr.println("Zero");
		} else if (a > 0) {
			pr.println("Positive");
		} else {
			if ((b - a) % 2 == 0) {
				pr.println("Negative");
			} else if ((b - a) % 2 != 0) {
				pr.println("Positive");
			}
		}

		pr.close();
		sc.close();
	}

	@SuppressWarnings("unused")
	private static class Scanner {
		BufferedReader br;
		Iterator<String> it;

		Scanner (InputStream in) {
			br = new BufferedReader(new InputStreamReader(in));
		}

		String next() throws RuntimeException  {
			try {
				if (it == null || !it.hasNext()) {
//					it = Arrays.asList(br.readLine().split(" ")).iterator();
					it = Arrays.asList(br.readLine().split("\\p{javaWhitespace}+")).iterator();
				}
				return it.next();
			} catch (IOException e) {
				throw new IllegalStateException();
			}
		}

		int nextInt() throws RuntimeException {
			return Integer.parseInt(next());
		}

		long nextLong() throws RuntimeException {
			return Long.parseLong(next());
		}

		float nextFloat() throws RuntimeException {
			return Float.parseFloat(next());
		}

		double nextDouble() throws RuntimeException {
			return Double.parseDouble(next());
		}

		void close() {
			try {
				br.close();
			} catch (IOException e) {
//				throw new IllegalStateException();
			}
		}
	}

	private static class Printer extends PrintWriter {
		Printer(PrintStream out) {
			super(out);
		}
	}
}


Measured memory_bytes: 8404
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
	while(cin>>n){
		int cnt=0;
		int x;
		for(int i=1;i<=n;i++){
			cin>>x;
			if(i&1&&x&1)cnt++;
		}
		cout<<cnt<<endl;
	}
	
	
	return 0;
}

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

money=1000
kabu=0
for i in range(N):
    money=money+A[i]*kabu
    kabu=0

    if i!=(N-1):
        if A[i]<A[i+1]:
            kabu=money//A[i]
            money-=kabu*A[i]

print(money)

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

int main(){
  int A,B;
  cin >> A >> B;
  if((A*B*1%2)==1){
    cout << "Yes" << endl;
  }else if((A*B*2)%2==1){
    cout << "Yes" << endl;
  }else if((A*B*3)%2==1){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  } 
}

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

using namespace std;
using LL = long long;

int main(){
    int h,w;
    vector<pair<int, pair<int, int>>> list;
    for(int i = 1;i <= 150;i++){
        for(int j = 1;j <= 150;j++){
            if(j > i)list.push_back(make_pair(i * i + j * j, make_pair(i, j)));
        }
    }
    sort(list.begin(), list.end());
    while(cin >> h >> w){
        if(h == 0 && w == 0)return 0;
        pair<int, pair<int, int>> p(h * h + w * w, make_pair(h, w));
        int i = 0;
        while(list.at(i) <= p){
            i++;
        }
        cout<<list[i].second.first<<" "<<list[i].second.second<<endl;
    }
}



Measured memory_bytes: 3160
#include <bits/stdc++.h>
#define rep(a,b) for(int a=0; a<b; ++a)
#define ran(a,b) for(auto &a:b)
using namespace std;

template<typename T>
using vec = vector<T>;

using ll = long long;
using pi = pair<int,int>;
using ti = tuple<int,int,int>;
using tup = tuple<string,int,int>;

ll MOD=1000000007;

int main(){
	int N; cin>>N;
	vec<ti> tra(N+1);
	tra[0]=ti(0,0,0);
	rep(i,N){
		int t,x,y; cin>>t>>x>>y;
		tra[i+1]=ti(t,x,y);
	}
	
	bool able=true;
	rep(i,N){
		int tb,xb,yb; tie(tb,xb,yb)=tra[i];
		int ta,xa,ya; tie(ta,xa,ya)=tra[i+1];
		int md=abs(xa-xb)+abs(ya-yb);
		int tn=ta-tb;
		able&=((md%2==tn%2)&&(md<=tn));
	}
	if(able) cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
}

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

using namespace std;

int main()
{
    int n, k, i, j, flag, temp, v;
    cin>>n>>k;
    int d[10]= {};
    for(i=0; i<k; i++)
    {
        cin>>d[i];
    }
    v=n;
    while(true)
    {
        flag=1;
        j=v;
        while(j>0)
        {
            temp=j%10;
            for(int l=0; l<k; l++)
            {
                if(temp==d[l])
                {
                    flag=0;
                }
            }
            j/=10;
        }
        if(flag)
        {
            cout<<v<<endl;
            return 0;
        }
        v++;
    }
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <memory>
#include <complex>
#include <numeric>
#include <cstdio>
#include <iomanip>

#define REP(i,m,n) for(int i=int(m);i<int(n);i++)
#define RREP(i,m,n) for(int i=int(n)-1;i>=int(m);--i)
#define EACH(i,c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())

#ifdef LOCAL
#define DEBUG(s) cout << (s) << endl
#define dump(x)  cerr << #x << " = " << (x) << endl
#define BR cout << endl;
#else
#define DEBUG(s) do{}while(0)
#define dump(x) do{}while(0)
#define BR 
#endif
using namespace std;

using UI = unsigned int;
using UL = unsigned long;
using LL = long long int;
using ULL = unsigned long long;
using VI = vector<int>;
using VVI = vector<VI>;
using VLL = vector<LL>;
using VVLL = vector<VLL>;
using VS = vector<string>;
using PII = pair<int,int>;
using VP = vector<PII>;

//struct edge {int from, to, cost;};

constexpr double EPS = 1e-10;
//constexpr double PI  = acos(-1.0);
//constexpr int INF = INT_MAX;
constexpr int MOD = 1'000'000'007;
//inline void modAdd(LL &l, LL &r) {l = (l + r) % MOD;}

template<class T> inline T sqr(T x) {return x*x;}

class UnionFind {
    struct UFNode {
        int par;
        int rank;
        LL cnt;
    };
    vector<UFNode> nodes;
public:
    UnionFind(int n): nodes(n) {
        for (int i = 0; i < n; i++) {
            nodes[i].par = i;
            nodes[i].rank = 0;
            nodes[i].cnt = 1;
        }
    };
    int root(int x) {
        return nodes[x].par == x ? x : root(nodes[x].par);
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    void unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return;
        if (nodes[x].rank < nodes[y].rank) {
            nodes[x].par = y;
            nodes[y].cnt += nodes[x].cnt;
        } else {
            nodes[y].par = x;
            nodes[x].cnt += nodes[y].cnt;
            if (nodes[x].rank == nodes[y].rank) nodes[x].rank++;
        }
    }
    LL getCount(int x) {
        return nodes[root(x)].cnt;
    }
    //~UnionFind() {cout << nodes.size() << endl;}
};

void solve() {
    LL n,m;
    cin >> n >> m;
    VI a(m), b(m);
    REP(i,0,m) cin >> a[i] >> b[i];
    LL sum = n * (n-1) / 2;
    VLL ans(m);
    UnionFind uf(n);
    RREP(i,0,m) {
        --a[i];--b[i];
        if (uf.same(a[i],b[i])) ans[i] = ans[i+1];
        else {
            LL add = uf.getCount(a[i]) * uf.getCount(b[i]);
            ans[i] = (i == m - 1 ? 0LL : ans[i+1]) + add;
            uf.unite(a[i], b[i]);
        }
    }
    REP(i,1,m) cout << sum - ans[i] << endl;
    cout << sum << endl;
}

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

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

int cnt[26];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string s;
	cin>>s;
	long long int ans=1;
	for(int i=0;i<s.size();i++){
		for(int j=0;j<26;j++)
			if((s[i]-'a')!=j)
				ans+=cnt[j];
		cnt[s[i]-'a']++;
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 720
#include <bits/stdc++.h>
using namespace std; 
    
int main(){
  int N;
  cin >> N;
  bool a=false,b=false,c=false;
  for(int i=0;i<N;i++){
    int D1,D2;
    cin >> D1 >> D2;
    if(i%3==0 && D1==D2){
      a=true;
    }
    else if(i%3==0){
      a=false;
    }
    if(i%3==1 && D1==D2){
      b=true;
    }
    else if(i%3==1){
      b=false;
    }
    if(i%3==2 && D1==D2){
      c=true;
    }
    else if(i%3==2){
      c=false;
    }
    if(a && b && c){
      cout << "Yes" << endl;
      return 0;
    }
  }
  cout << "No" << endl;
  
}
    
    

Measured memory_bytes: 3616
#include <bits/stdc++.h>
using namespace std;
#define Hello ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define endl '\n'
void trace(int n, ll arr[]){for(int i = 0; i < n; i++){cout << arr[i] << " ";} cout << endl << endl;}
const ll mod = 1e9 + 7;
int main()
{
    Hello
    int x, n;
    cin >> x >> n;
    int arr[n + 5];
    map<int, bool> vis;
    for(int i = 0; i < n; i++){
        cin >> arr[i];
        vis[arr[i]] = 1;
    }
    int r = 0, l = 0;
    for(int i = x; ; i++){
        if(!vis[i]){
            r = i;
            break;
        }
    }
    for(int i = x; ; i--){
        if(!vis[i]){
            l = i;
            break;
        }
    }
    if(abs(x - l) <= abs(x - r)) cout << l;
    else cout << r;
    return 0;
}


Measured memory_bytes: 3616
N = gets.to_i
A = gets.chomp.split(" ").map(&:to_i)

A << 0
wk, bef = [0, 0]
ac = A.map{|a| wk += (a - bef).abs; bef = a; wk}


bef = 0
ac << 0
N.times{|n|
  puts (A[n+1] - A[n-1]).abs + ac[N] - ac[n+1] + ac[n-1]
}


Measured memory_bytes: 12932
#include<bits/stdc++.h>
using namespace std;
#define Maxn 100010
int n, m, Occur[Maxn];

int main()
{
	scanf("%d%d", &n, &m);
	if (n%2 == 1)
	{
		for (int i=1; i<=m; i++) printf("%d %d\n", i, n - i + 1);
	}
	else
	{
		int Nep = n + 1;
		for (int i=1; i<=m; i++)
		{
			while (Occur[min(Nep - i - i - 1, n - (Nep - i) + i - 1)]) Nep--;
			if (Nep - i - i == n / 2) Nep--;
			Occur[min(Nep - i - i - 1, n - (Nep - i) + i - 1)]=1;
			printf("%d %d\n", i, Nep - i);
		}
	}
}

Measured memory_bytes: 3984
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
int main(){
    ll n,x,t;
    cin >> n >> x >> t;
    ll k = n / x;
    if(n % x != 0)k++;
    cout << t * k << endl;
}

Measured memory_bytes: 3640
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
long long int mod = (long long int)1000000007;
using namespace std;

void solve()
{
    ll i,j,k,n;
    std::cout.precision(10);
    int yes=0;
  	ll x;
  cin>>x>>n;
  ll vis[1001]={0};
  ll a[n];
  for(i=0;i<n;i++)
  {
   	cin>>a[i];
    vis[a[i]]=1;
  }
  ll p,q=-1;
  for(i=x;i<1001;i++)
  {
   	if(vis[i]==0)
    {
     	p=i;
      break;
    }
  }
  for(i=x;i>=0;i--)
  {
   	if(vis[i]==0)
    {
     	q=i;
      break;
    }
  }
  if(p-x<x-q)
  {
   	cout<<p; 
  }
  else
  {
   	cout<<q; 
  }
}

int main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    int i,j,k;
    int t;
    std::cout.precision(10);
    t=1;
    while(t--)
    {
        solve();
        cout<<"\n";
    }
}

Measured memory_bytes: 3620
using System;
namespace csharptest
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] str = Console.ReadLine().Split(' ');
            int a = int.Parse(str[0]);
            int b = int.Parse(str[1]);
            int c = int.Parse(str[2]);
            int count=0;
            for (int n = a; n <= b; n++)
                if (c % n == 0)
                    count++;
            Console.WriteLine(count);
        }
    }
}

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

//typedefs
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ull> vull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pii> vpii;
typedef map<int, int> mii;
typedef priority_queue<pii, vpii, greater<pii> > pq;
typedef tuple<int, int, int> tp;

//Constants
const int INF = (int)2 * 1e9;
const ll MOD = 1000000007;
const long double PI = 3.1415926;
const long double EPS = 1e-6;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define what(x) cerr << #x << " => " << x << endl;
#define print_r(x) for(auto i = 0; i < x.size(); i++) what(x[i]);
#define print_grid(x) for(auto i = 0; i < x.size(); i++){for(auto j = 0; j < x[0].size(); j++){cout << x[i][j];}cout << endl;}
#define gridM(type, n, m) vector<vector<type>> grid(n, vector<type>(m))

template <typename T>vector<T> prefix_sum(vector<T> nums){vector<T> pre_sum(nums.size());partial_sum(nums.begin(), nums.end(), pre_sum.begin());return pre_sum;}
vector<string> split(string s, char sep){int prev_index = 0;int i = 0;vector<string> words;for(i = 0; i < s.size(); i++){if(s[i] == sep){words.push_back(s.substr(prev_index, i - prev_index));prev_index = i + 1;}}words.push_back(s.substr(prev_index, (s.size() - prev_index )));return words;}

void read(){
  //stime = clock();
  #ifdef DEBUG
    freopen("in.txt", "r", stdin);
   #endif // DEBUG
   cin.sync_with_stdio(false);
   cin.tie(0);
}


int main(){
 read();
 int k, a,  b;
 cin >> k >> a >> b;
 bool flag = false;
 for(int i = 1; k * i <= b; i++){
  if(k * i >= a && k * i <= b){
    cout << "OK";
    return 0;
  }
 }
 cout << "NG";

 return 0;
}


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

int main(){
    int N;
    cin >> N;
    int calc = N;
    int sum = 0;
    
    while(calc != 0){
        sum += calc % 10;
        calc /= 10;
    }
    if(N % sum == 0){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
N = int(input())
*h, = map(int, input().split())
dp = [float("inf") for _ in range(N)]
dp[0] = 0
for i in range(N - 1):
	dp[i + 1] = min(dp[i + 1], dp[i] + abs(h[i + 1] - h[i]))
	if i < N - 2:
		dp[i + 2] = min(dp[i + 2], dp[i] + abs(h[i + 2] - h[i]))
print(dp[N - 1])

Measured memory_bytes: 13928
#include <stdio.h>
#define MAX 600
int main()
{
 int s, d, x;
 while (scanf("%d", &d) == 1) {
  s = 0, x = d;
  while (x < MAX) {
   s += d * x*x;
   x += d;
  }
  printf("%d\n", s);
 }
 return 0;
} 


Measured memory_bytes: 2036
import sys
import numpy as np

h, w = list(map(int, input().split()))
field = np.array([[c == '.' for c in line.rstrip()] for line in sys.stdin], dtype=np.int32)
li, ri, ui, di = (field.copy() for _ in [0] * 4)

for i in range(1, h):
    ui[i] = (ui[i - 1] + 1) * field[i]
    di[h - i - 1] = (di[h - i] + 1) * field[h - i - 1]
field = field.T
li, ri = li.T, ri.T
for j in range(1, w):
    li[j] = (li[j - 1] + 1) * field[j]
    ri[w - j - 1] = (ri[w - j] + 1) * field[w - j - 1]
li, ri = li.T, ri.T
print((li + ri + ui + di).max() - 3)


Measured memory_bytes: 121972
import math

N = int(input())

ans = 0
for n in range(1, N + 1):
    if n % 2 != 0:
        yaku = 0
        for m in range(1, n + 1):
            if n % m == 0:
                yaku += 1

        if yaku == 8:
            ans += 1

print(ans)

Measured memory_bytes: 3060