akhauriyash/Code-Regression huggingface dataset:
import heapq
import itertools
import sys

sys.setrecursionlimit(10000)
INF = float('inf')

N, M, _ = list(map(int, sys.stdin.readline().split()))
R = list(map(int, sys.stdin.readline().split()))
A, B, C = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(M)]))


def dijkstra(graph, start):
    """
    マイナスの辺があっちゃダメ
    scipy.sparse.csgraph.dijkstra は内部で使われてるフィボナッチヒープが一部のケースでめっちゃ遅いのであんまり使わないほうがよさげ
    https://atcoder.jp/contests/soundhound2018-summer-qual/submissions/5311823

    :param list of (list of (int, int)) graph:
        graph[from_index]: (to_index, weight)
    :param int start:
    :return:
    """
    dist = [float('inf') for _ in range(len(graph))]
    dist[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))

    while len(heap) > 0:
        w, v = heapq.heappop(heap)
        if w > dist[v]:
            continue
        for u, dw in graph[v]:
            if w + dw < dist[u]:
                dist[u] = w + dw
                heapq.heappush(heap, (w + dw, u))
    return dist


#: :type: list of (list of (int, int))
graph = [[] for _ in range(N + 1)]
for a, b, c in zip(A, B, C):
    graph[a].append((b, c))
    graph[b].append((a, c))

dists = []
for r in R:
    dists.append(dijkstra(graph, r))

ans = INF
for indices in itertools.permutations(range(len(R))):
    s = 0
    for i, j in zip(indices[:-1], indices[1:]):
        s += dists[i][R[j]]
    ans = min(ans, s)
print(ans)


Measured memory_bytes: 59740
N, K = map(int, input().split())
arr = list(map(int, input().split()))
dp = [float('inf')] * N
dp[0] = 0
for i in range(0,N):
    k = 1
    while (i + k < N) and (k <= K):
        dp[i+k] = min(abs(arr[i]-arr[i+k])+dp[i],dp[i+k])
        k += 1
print(dp[N-1])

Measured memory_bytes: 55136
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
const double PI  = 3.1415926535897932384626433832795028841971;
const int    INF = 100000000;
const double EPS = 1e-10;
const int    MOD = 1000000007;
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int w,h,t,p;
int x[50],y[50],z[50];
int m[50][50];

int main(){
	cin >> w >> h >> t >> p;
    rep(i,p) cin >> x[i] >> y[i] >> z[i];
    rep(i,h){
        rep(j,w){
            int tmp;
            cin >> tmp;
            if(tmp) m[i][j] = 0;
            else m[i][j] = -1;
        }
    }
    int ans = 0;
    rep(i,p){
        if(m[y[i]][x[i]] != -1 && z[i] <= t){
           ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1172
from math import gcd, sqrt
def primes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
n = int(input())
a = list(map(int, input().split()))
b = a[0]
for i in range(1, n): b = gcd(b, a[i])
if b != 1: print("not coprime")
else:
    data = primes(10**6)
    c = [1]*(10**6+1)
    for i in range(1, 10**6+1):
        for j in range(len(data)):
            if i < data[j]**2: break
            if i%data[j] == 0: c[i] = data[j]; break
        if c[i] == 1: c[i] = i
    d = [0]*(10**6+1)
    for i in range(n):
        while a[i] > 1:
            d[c[a[i]]] += 1
            e = c[a[i]]
            while a[i]%e == 0: a[i] //= e
    print("setwise coprime") if max(d[2:]) > 1 else print("pairwise coprime")

Measured memory_bytes: 205380
#include<iostream>
using namespace std;
int main()
{
 int Time;
 int h,m,s;

 cin >> Time;

 h = Time / 3600;
 m = (Time % 3600) / 60;
 s = (Time % 3600) % 60;

 cout << h << ":"<<m<<":"<<s<<endl;
 return 0;
}

Measured memory_bytes: 1164
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ld long double
#define pb push_back
#define endl "\n"
#define ff first
#define ss second
#define inp(a) int a; cin>>a;
#define inpa(a,n) vector<int>a(n+2); FOR(i,1,n) cin>>a[i];
#define PI 3.141592653589793238
#define vec(x) vector<x>
#define pii pair<int,int>
#define mem(a,b) memset(a, b, sizeof a)
#define FOR(i,j,n) for(int i= j; i<=n; i++)
#define CASE int t; cin>>t; while(t--)
#define prec(n) fixed<<setprecision(n)
#define print(x) for(auto c : x) cout << c << " ";
#define dbg(x) cerr << #x << " :: "<< x << endl;
#define dbg2(x,y) cerr << #x << " :: "<<x <<"\t" << #y << " :: "<<y <<endl;
const int INF = 1e9 + 7;
const int maxn = 1e6 + 3;
const int MOD = 1e9 + 7; 
//////////// template ends here //////////////////////////



void solve(){

	inp(n);
	inpa(h,n);

	vec(int)dp(n+1, 0);
	dp[1] = 0;


	for(int i = 2; i <=n; i++){
		int sub1 = maxn, sub2 = maxn;
		if(i-1 > 0)
			 sub1 = dp[i-1] + abs(h[i]-h[i-1]);
		if(i-2 > 0)
			 sub2 = dp[i-2] + abs(h[i]-h[i-2]);

		dp[i] = min(sub1, sub2);
	}

	cout << dp[n] << endl;	



}




int32_t main(){
	#ifndef ONLINE_JUDGE 
		freopen ("input.txt","r",stdin);
		freopen ("output.txt","w",stdout);
	#endif	
	 ios::sync_with_stdio(0); 
	 cin.tie(0); cout.tie(0);
	//CASE{
		solve();
	//}

	cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
}

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

int a[5];
int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    int n,m; cin >> n >> m;
    memset(a,-1,sizeof a);
    int fg = 0;
    for(int i=1;i<=m;i++)
    {
        int p,q; cin >> p >> q;
        if(a[p]==-1)a[p] = q;
        else if(a[p]!=q)fg = 1;
    }
    if(fg)cout << "-1\n", exit(0);

    if(a[1]==0 && n>1)cout << "-1\n", exit(0);
    for(int i=1; i<=n; i++)
    {
        if(i==1)
        {
            if(a[i]==-1 && n>1)a[i] = 1;
            if(a[i]==-1 && n==1)a[i] = 0;
        }
        else
        {
            if(a[i]==-1)a[i] = 0;
        }
    }
    for(int i=1; i<=n; i++)cout<< a[i];cout<<"\n";
    return 0;
}


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


int fun(int *arr, int n, int k){
    if(n<=k){
        return 0;
    }
    
    int ans = 0;
    
    for(int i=0;i<n-k;++i)
        ans += *(arr+i);
    
    return ans;
    
}

signed main() {
	int n,k;
	cin>>n>>k;
	int arr[n];
	
	for(int i=0;i<n;++i)
	    cin>>arr[i];
	
	sort(arr,arr+n);
	cout<<fun(arr,n,k);
	return 0;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define Tsetso ios_base::sync_with_stdio(0) ; cin.tie(0) ;
using namespace std;
const ll N = 2e5+50, inf = 1e3+5, mod = 1e9+7, NN = 1e5+10;
ll a[N] , b[N];
int main()
{
    Tsetso
    int n ;
    cin >> n;
    for ( int i = 0 ; i <= n ; i++)
            cin >> a[i] ;
    for ( int i = 0 ; i < n ; i++)
            cin >> b[i] ;
    ll ans = 0 ;
    for ( int i = 0 ; i < n ; i++)
    {
        ans += min(a[i],b[i]);
        b[i] -= min(a[i],b[i]);
        ans += min(a[i+1],b[i]);
        a[i+1] -= min(a[i+1],b[i]);
    }
    cout << ans ;
}


Measured memory_bytes: 5184
#define rep(i, n) for (int i = 0; i < (n); i++)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int MOD = 1000000007;
// MAX int 2,147,483,647
// MAX O(n) 10^18

int main() {
    int N;
    cin >> N;
    vector<string> S(N);
    vector<int> P(N);
    rep(i, N) cin >> S.at(i) >> P.at(i);

    vector<tuple<string, int, int>> store(N);

    rep(i, N) {
        store.at(i) = make_tuple(S.at(i), -P.at(i), i);
    }

    sort(store.begin(), store.end());

    for(auto tmp : store) {
        int ans;
        tie(ignore, ignore, ans) = tmp;
        cout << ans + 1 << endl;
    }

    return 0;
}


Measured memory_bytes: 3644
import java.util.Scanner;
public class Main{
static int cnt=0;
static long SENTINEL=1000000001l;
static long []s;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
	int i;
     Scanner yomi=new Scanner(System.in);
     s=new long[yomi.nextInt()];
     for(i=0;i<s.length;i++) s[i]=yomi.nextLong();
     mergesort(s,0,s.length);
     for(i=0;i<s.length;i++){
    	 if(i!=s.length-1){
    	 System.out.print(s[i]+" ");
    	 }else{
         System.out.println(s[i]);
    	 }
     }
     System.out.println(cnt);
	}
public static void merge(long[] a,int left,int mid,int right){
	  int n1=mid-left,n2=right-mid,i,j,k;
	  long l[]=new long[n1+1];
	  long r[]= new long[n2+1];
	  for(i=0;i<n1;i++){
		  l[i]=a[left+i];
	  }
	  for(i=0;i<n2;i++){
		  r[i]=a[mid+i];
	  }
	  l[n1]=SENTINEL;
	  r[n2]=SENTINEL;
	  i=0;
	  j=0;
	  for(k=left;k<right;k++){
		  cnt++;
		  if(l[i]<=r[j]){
			  s[k]=l[i];
			  i++;
		  }else{
			  s[k]=r[j];
			  j++;
		  }
	  }
  }
  public static void mergesort(long[]a,int left,int right){
	  int mid;
	  if(left+1<right){
	  mid=(left + right)/2;
	  mergesort(a,left,mid);
	  mergesort(a,mid,right);
	  merge(a,left,mid,right);
	
	  }
  }

}


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

int main(){
    int a,b,c;
    cin>>a>>b>>c;
    if (b-a==c-b)
    {
        /* code */
        cout<<"YES"<<endl;
    }
    else
    {
        cout<<"NO"<<endl;
    }
    
    
    }


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
  int n,k[100005],count=1;
  cin>>n;
  for(int i=0;i<n;++i){
    cin>>k[i];
  }
  sort(k,k+n);
  for(int i=1;i<n;++i){
    if(k[i-1]!=k[i]) count++;
  }
  if(count%2==0) cout<<count-1<<endl;
  else cout<<count<<endl;
}

Measured memory_bytes: 640
n = $stdin.gets.to_i
a = $stdin.gets.split.map(&:to_i)

ary = []
r_ary = []
result = []

def gcd(x,y)
  if x % y == 0
    return y
  end
  return gcd(y,x%y)
end
ary[0] = a[0]
(1..n-1).each do |i|
  ary[i] = gcd(ary[i-1],a[i])
end

r_ary[n-1] = a[n-1]
(0..n-2).reverse_each do |i|
  r_ary[i] = gcd(a[i],r_ary[i+1])
end
result[0]=r_ary[1]
result[n-1]=ary[n-2]

(1..n-2).each do |i|
  result[i] = gcd(ary[i-1],r_ary[i+1])
end
    
puts result.max


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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

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

	vector<string> vs;
	for(int i=0;i<s.length();i++){
		for (int j=1;j<6;j++){
			if (i+j-1<s.length()){
				vs.push_back(s.substr(i, j));				
			}
		}
	}
	sort(vs.begin(), vs.end());
	unique(vs.begin(), vs.end());

	cout << vs[K-1] << endl;

    return 0;
}

Measured memory_bytes: 1660
#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 a,b,c;
  cin >> a >> b >> c;
  if(a==b){
    if(b==c)cout << "No" << endl;
    else cout << "Yes" << endl;
  }
  else if(b==c){
    if(a==b)cout << "No" << endl;
    else cout << "Yes" << endl;
  }
  else if(c==a){
    if(a==b)cout << "No" << endl;
    else cout << "Yes" << endl;
  }
  else cout << "No" << endl;
}


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

using namespace std;
typedef long long int LL;
typedef long long int ll;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SP << " " <<

LL mod = 1000000007;

//昇順ソート
int xcomp(pii& a, pii& b) {
	return a.first < b.first;
}

#define XSORT(c) sort((c).begin(),(c).end(),xcomp)

vector<pii> robot;

// index が条件を満たすかどうか
bool isOK(int index, LL key) {
    if (robot[index].first >= key) return true;
    else return false;
}

// 汎用的な二分探索のテンプレ
int binary_search(LL key) {
    int ng = -1; //「index = 0」が条件を満たすこともあるので、初期値は -1
    int ok = (int)robot.size(); // 「index = a.size()-1」が条件を満たさないこともあるので、初期値は a.size()

    /* ok と ng のどちらが大きいかわからないことを考慮 */
    while (abs(ok - ng) > 1) {
        int mid = (ok + ng) / 2;

        if (isOK(mid, key)) ok = mid;
        else ng = mid;
    }
    return ok;
}

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

  LL N;
  cin >> N;
  
  REP(i,N){
    LL X, L;
    cin >> X >> L;
    robot.push_back({X - L, X + L});
  }

  XSORT(robot);

  vector<LL> dp(N+1, 0);

  for (LL i = N - 1; i >= 0;--i){
    LL idx = binary_search(robot[i].second);
    
    dp[i] = max(dp[idx] + 1,dp[i+1]);
  }

  cout << dp[0] << endl;
}


Measured memory_bytes: 2672
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=100010;
const ll mod=1e9+7;


int main(){
  int a,b; cin >> a >> b;
  vector<int> c={a,b,a-1,b-1};
  sort(c.rbegin(),c.rend());
  cout << c[0]+c[1] << endl;
}


Measured memory_bytes: 256
import heapq as hp
n,m=map(int,input().split())
AB=[[] for i in range(m+1)]

for i in range(n):
  a,b=map(int,input().split())
  if a<=m:
    AB[a].append(-b)

ans=0
l=[]
hp.heapify(l)
for ab in AB:
  for t in ab:
    hp.heappush(l,t)
  if len(l)>0:
    ans-=hp.heappop(l)
print(ans)



Measured memory_bytes: 17604
#include <bits/stdc++.h>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    long long h,temp,k=0;
    
    cin>>h;
    if(h==1) cout<<1;
    else{
        temp=h;
    while(temp)
    {
        temp/=2;
        k++;
    }
    long long a=(pow(2,k))-1;
    cout<<a;
    }
    
	return 0;
}

Measured memory_bytes: 256
package main

import (
	"fmt"
	"os"
)

func main() {
	var N, Y int
	fmt.Scan(&N, &Y)
	for x := 0; x <= N; x++ {
		for y := 0; y <= N; y++ {
			z := N - x - y
			if z < 0 {
				continue
			}
			if 10000*x+5000*y+1000*z == Y {
				fmt.Println(x, y, z)
				os.Exit(0)
			}
		}
	}
	fmt.Println(-1, -1, -1)

}


Measured memory_bytes: 512
n = int(input())
A = list(map(int, input().split()))

cnt = 0


def bubble_sort(A, n):
    global cnt
    for _ in range(n):
        for i in range(n-1):
            if A[i] > A[i+1]:
                A[i], A[i+1] = A[i+1], A[i]
                cnt += 1


bubble_sort(A, n)
print(*A)
print(cnt)



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

using namespace std;

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PI;

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x = i;
		if (x % 3 == 0) {
			cout << " " << i;
			continue;
		}
		do {
			if (x % 10 == 3) {
				cout << " " << i;
				break;
			}
			x /= 10;
		} while (x);
	}
	cout << endl;
	return 0;
}


Measured memory_bytes: 3088
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9;
const int MOD = 1000000007;
const double PI = acos(-1);
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

void solve() {
  int n, d;
  cin >> n >> d;
  vector<vector<int>> v(n, vector<int>(d));
  rep(i,n) rep(j,d) cin >> v[i][j];

  int ans = 0;

  rep(i,n) {
    for (int j = i + 1; j < n; j++) {
      int naka = 0;
      rep(k, d) {
        naka += pow((v[i][k] - v[j][k]), 2);
      }
      for (int k = 1; k * k <= 16000; k++) {
        if (naka == k * k) {
          ans++;
          break;
        }
      }
    }
  }
  cout << ans << endl;
}

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

Measured memory_bytes: 3580
package main

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

func main() {
	io := newIo()
	defer io.Flush()
	N, Q := io.NextInt(), io.NextInt()
	points := map[int]int{}
	edges := map[int][]int{}
	for i := 0; i < N-1; i++ {
		a, b := io.NextInt(), io.NextInt()
		edges[a] = append(edges[a], b)
		edges[b] = append(edges[b], a)
	}
	for i := 0; i < Q; i++ {
		a, point := io.NextInt(), io.NextInt()
		points[a] = points[a] + point
	}
	visits := map[int]bool{}
	visits[1] = true
	totalPoints := make([]int, N+1)
	totalPoints[1] = points[1]
	q := []int{1}
	for len(q) > 0 {
		qq := q[0]
		q = q[1:]
		currentPoint := totalPoints[qq]
		for _, edge := range edges[qq] {
			_, exists := visits[edge]
			if exists {
				continue
			}
			visits[edge] = true
			totalPoints[edge] = currentPoint + points[edge]
			q = append(q, edge)
		}
	}
	io.PrintIntLn(totalPoints[1:])
}

type io struct {
	reader    *bufio.Reader
	writer    *bufio.Writer
	tokens    []string
	nextToken int
}

func newIo() *io {
	return &io{
		reader: bufio.NewReader(os.Stdin),
		writer: bufio.NewWriter(os.Stdout),
	}
}

func (io *io) Flush() {
	err := io.writer.Flush()
	if err != nil {
		panic(err)
	}
}

func (io *io) NextLine() string {
	var buffer []byte
	for {
		line, isPrefix, err := io.reader.ReadLine()
		if err != nil {
			panic(err)
		}
		buffer = append(buffer, line...)
		if !isPrefix {
			break
		}
	}
	return string(buffer)
}

func (io *io) Next() string {
	for io.nextToken >= len(io.tokens) {
		line := io.NextLine()
		io.tokens = strings.Fields(line)
		io.nextToken = 0
	}
	r := io.tokens[io.nextToken]
	io.nextToken++
	return r
}

func (io *io) NextInt() int {
	i, err := strconv.Atoi(io.Next())
	if err != nil {
		panic(err)
	}
	return i
}

func (io *io) NextFloat() float64 {
	i, err := strconv.ParseFloat(io.Next(), 64)
	if err != nil {
		panic(err)
	}
	return i
}

func (io *io) PrintLn(a ...interface{}) {
	fmt.Fprintln(io.writer, a...)
}

func (io *io) Printf(format string, a ...interface{}) {
	fmt.Fprintf(io.writer, format, a...)
}

func (io *io) PrintIntLn(a []int) {
	b := []interface{}{}
	for _, x := range a {
		b = append(b, x)
	}
	io.PrintLn(b...)
}

func (io *io) PrintStringLn(a []string) {
	b := []interface{}{}
	for _, x := range a {
		b = append(b, x)
	}
	io.PrintLn(b...)
}

func log(name string, value interface{}) {
	fmt.Fprintf(os.Stderr, "%s=%+v\n", name, value)
}


Measured memory_bytes: 55424
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

const long long mod = 1000000007;
const long long inf = 1e18;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,k;
    cin>>n>>k;
    vi a;
    for(int i=0;i<n;i++){
        ll p;
        cin>>p;
        a.pb(p);
    }
    sort(a.begin(),a.end());
    a.pb(-1);
    vi count;
    int c=1;
    int p=a[0];
    for(int i=1;i<=n;i++){
        if(a[i]==p){
            c+=1;
        }
        else{
            count.pb(c);
            c=1;
            p=a[i];
        }
    }
    sort(count.begin(),count.end());
    ll ans=0;
    if(count.size()>k){
        for(int i=0;i<count.size()-k;i++){
            ans+=count[i];
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 2548
#include<iostream>
using namespace std;
int main(){
  int x,y;
  cin>>x>>y;
  if(y<x*2||x*4<y){
    cout<<"No"<<endl;
  }else if(y%2==0){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
  return(0);
}

Measured memory_bytes: 3628
/*  Author:  Hariom_Pandey
    Created: 3/1/2020 5:42:38 PM
*/
 
 
#include <bits/stdc++.h>
using namespace std;
#define All(a)          (a).begin(), (a).end()
#define Lwb             lower_bound
#define Upb             upper_bound
#define Sz(a)           int((a).size())
#define u_map           unordered_map
#define Exist(a, b)     (find(All(a), (b)) != (a).end())
#define Sort(x)         sort(All(x))
#define Gsort(x)        sort(All(x), greater<typeof(*((x).begin()))>())
#define Unique(v)       Sort(v); (v).resize(unique(ALL(v)) - (v).begin())
#define ooi             INT_MAX
#define ool             LLONG_MAX
#define ll              long long int
#define ull             unsigned ll
#define ld              long double
#define pii             pair<int,int>
#define pll             pair<ll,ll> 
#define mem(x,y)    memset(x,y,sizeof x )
int cnt[30];
int32_t main(){
   ll arr[3][3];
   bool mrr[3][3];
   bool ok=0;
   for(ll i=0; i<3; i++)
    for(ll j=0; j<3; j++){
        cin>>arr[i][j]; mrr[i][j]=0;
    }
   ll num; cin>>num;
   while(num--){
        ll ht; cin>>ht;
        for(ll i=0; i<3; i++)
        for(ll j=0; j<3; j++)
        if(arr[i][j]==ht) mrr[i][j]=1;
   }
   
   for(ll i=0; i<3; i++){
     ll cp=0;
    for(ll j=0; j<3; j++)
        cp+=mrr[i][j];
        if(cp==3)  ok=1;
   }
   for(ll i=0; i<3; i++){
     ll cp=0;
     for(ll j=0; j<3; j++)
        cp+=mrr[j][i];
        if(cp==3) ok=1;
   }
   ll cp=0;
   for(ll i=0; i<3; i++) cp+=mrr[i][i];
   if(cp==3) ok=1;
   cp=0;
   for(ll i=0; i<3; i++)
   cp+=mrr[i][2-i];
   if(cp==3)
   ok=1;
   if(ok)
   cout<<"Yes";
   else
   cout<<"No";
    }

    
    


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<iomanip>
#include<vector>
#include<random>
#include<functional>
#include<algorithm>
#include<cstdio>
#include<bitset>
#include<unordered_map>
using namespace std;
//---------------------------------------------------
//ライブラリゾーン！！！！
typedef long long ll;
typedef long double ld;
#define str string
#define rep(i,j) for(ll i=0;i<(long long)(j);i++)
#define all(a) (a).begin(),(a).end()
const ll Mod = 1000000007;
const ll gosenchou = 5000000000000000;
short gh[2][4] = { { 0,0,-1,1 },{ -1,1,0,0 } };
struct P {
	ll pos, cost;
};
bool operator<(P a, P b) { return a.cost < b.cost; }
bool operator>(P a, P b) { return a.cost > b.cost; }
struct B {//隣接リスト表現
	ll to, cost;
};
struct E {//辺の情報を入れる変数
	ll from, to, cost;
};
bool operator<(E a, E b) {
	return a.cost < b.cost;
}
struct H {
	ll x, y;
};
bool operator<(H a, H b) {
	if (a.x != b.x) return a.x < b.x;
	return a.y < b.y;
}
bool operator>(H a, H b) {
	if (a.x != b.x) return a.x > b.x;
	return a.y > b.y;
}
bool operator==(H a, H b) {
	return a.x == b.x&&a.y == b.y;
}
bool operator!=(H a, H b) {
	return a.x != b.x || a.y != b.y;
}
ll gcm(ll i, ll j) {//最大公約数
	if (i > j) swap(i, j);
	if (i == 0) return j;
	return gcm(j%i, i);
}
ld rad(H a, H b) {
	return sqrt(pow(a.x - b.x, 2.0) + pow(a.y - b.y, 2.0));
}//rad＝座標上の2点間の距離
ll ari(ll a, ll b, ll c) {
	return (a + b)*c / 2;
}//等差数列の和
ll fact(ll x, ll k, ll p) {//最大値、個数、あまり
	ll sum = 1;
	for (int i = 0; i < k; i++) {
		sum *= (x--);
		sum %= p;
	}
	return sum;
}//階乗(正）
ll mod_pow(ll x, ll n, ll p) {
	ll res = 1;
	while (n > 0) {
		if (n & 1) res = res*x%p;
		x = x*x%p;
		n >>= 1;
	}
	return res;
}//x^n%p
short ctos(char a) {
	return (int)(a - '0');
}
#define int long long
const long long Inf = 4523372036854775807;
const int inf = 15000000000;
//----------------------------------------------------
//++++++++++++++++++++++++++++++++++++++++++++++++++++
signed main() {
	string a,b;
	cin>>a>>b;
	long double c=sqrt(stoi(a+b)),d=floor(sqrt(stoi(a+b)));
	if(c==d) cout<<"Yes\n";
	else cout<<"No\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const double pi = acos(-1);
#define FOR(i,a,b) for (ll i=(a),__last_##i=(b);i<__last_##i;i++)
#define RFOR(i,a,b) for (ll i=(b)-1,__last_##i=(a);i>=__last_##i;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define __GET_MACRO3(_1, _2, _3, NAME, ...) NAME
#define rep(...) __GET_MACRO3(__VA_ARGS__, FOR, REP)(__VA_ARGS__)
#define rrep(...) __GET_MACRO3(__VA_ARGS__, RFOR, RREP)(__VA_ARGS__)
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v) {
REP(i,v.size()){if(i)os<<" ";os<<v[i];}return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
REP(i,v.size()){if(i)os<<endl;os<<v[i];}return os;}

int main() {
    string S;cin>>S;
    if(S[0]==S[1]){cout<<"Bad"<<endl;}
    else if(S[1]==S[2]){cout<<"Bad"<<endl;}
    else if(S[2]==S[3]){cout<<"Bad"<<endl;}
    else{cout<<"Good"<<endl;}
    

}



Measured memory_bytes: 256
# nは3ケタなので、1000までの数すべてチェックしても時間は間に合う。
# 左端が0になるようなものは想定しない
def solve(n, A):
    for i in range(1000):
        s = str(i)
        if len(s) == n:
            ok = True
            for p in A:
                a, b = (p[0], p[1])
                if s[a-1] != str(b):
                    ok = False
                    break
            if ok:
                return i
    return -1

def main():
    n, m = map(int, input().split())
    A = []
    for _ in range(m):
        a, b = map(int, input().split())
        A.append([a, b])
    print(solve(n, A))

if __name__ == "__main__":
    main()

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

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


int main(){
    int N, W; cin >> N >> W;
    vector<vector<long>> dp(N+1, vector<long>(W+1, 0));
    for (int i = 0; i < N; i++)
    {
        int w, v; cin >> w >> v;
        for (int j = 0; j <= W; j++)
        {
            chmax(dp[i+1][j], dp[i][j]);
            if(j-w>=0) chmax(dp[i+1][j], dp[i][j-w]+v);
        }
    }
    cout << dp[N][W] << endl;
}


Measured memory_bytes: 80256
#include <bits/stdc++.h>
using namespace std;
#define finish(x) return cout << x << endl, 0;
#define ll long long

int n;

int sum(int x){
    int ret = 0;
    while(x){
        ret += x%10;
        x /= 10;
    }
    return ret;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n;
    if(n%sum(n) == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int main()
{
	int arr[3];
	cin >> arr[0] >> arr[1] >> arr[2];
	sort(arr,arr+3);
	cout << abs(arr[0]-arr[1]) + abs(arr[1]-arr[2]);
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) for (int i = (int)(n-1); i >= 0; i--)
#define sz(x) int(x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define INF 2e9
#define LINF 1e18
#define mod 1e9+7
template<class T> inline bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> P;

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

    int check = 1;
    rep(i,n) {
        if (a[i]==check) {
            check++;
        }
    }

    if (check==1) {
        cout << -1 << endl;
        return 0;
    }

    cout << n+1-check << endl;

}

Measured memory_bytes: 1024
def main():
  import sys
  input = sys.stdin.readline
  n, k = map(int, input().split())
  arr = list(map(int, input().split()))
  dp = [1000000000] * n
  dp[0] = 0
  for i in range(1, n):
    for j in range(max(0, i - k), i):
      dp[i] = min(dp[i], dp[j] + abs(arr[i] - arr[j]))
  print(dp[-1])
main()  

Measured memory_bytes: 52444
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 10 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N, X, M = map(int, input().split())

xs = [0] * M
cur = X
cicle = 0
A = []
for i in range(M + 5):
    v = cur % M 
    if xs[v] != 0:
        A.append(v)
        cicle = i
        break
    xs[v] += 1
    A.append(v)
    cur *= cur
    cur %= M

start = 0
for i in range(cicle):
    if A[i] == A[-1]:
        start = i
# print(start)
# print(A)
l = cicle - start
ans = sum(A[0:start])
ans += ((N - start) // l) * sum(A[start:-1])
ans += sum(A[start:start+((N - start) % l)])

print(ans)



Measured memory_bytes: 73260
from collections import defaultdict
from collections import deque
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = deque(); self.Q.append(s)
		self.dist = [INF] * N; self.dist[s] = 0
		while self.Q:
			v = self.Q.popleft()
			for i in self.g[v]:
				if self.dist[i] == INF:
					self.dist[i] = self.dist[v] + 1
					self.Q.append(i)

#処理内容
def main():
	N = int(input())
	X = list(map(int, list(input())))

	G = Graph()
	for i in range(1, 2 * (10 ** 5) + 1):
		cnt1 = 0
		n = i
		while True:
			if n % 2 == 1:
				cnt1 += 1
			n = int(n // 2)
			if n == 0:
				break
		a = i % cnt1; b = i
		G.add_edge(a, b)

	BF = BFS(G, 0, 2 * (10 ** 5) + 1)
	dist = BF.dist

	X1cnt = 0
	for i in X:
		if i == 1:
			X1cnt += 1

	if X1cnt == 0:
		for i in range(N):
			print(1)

	elif X1cnt == 1:
		Xplus = 0
		for i in range(N):
			Xplus += pow(2, i, X1cnt + 1) * X[-1 - i]

		for i in range(N):
			if X[i] == 1:
				print(0)
			else:
				val = Xplus
				val += pow(2, N - 1 - i, X1cnt + 1)
				val %= X1cnt + 1
				print(dist[val] + 1)

	else:
		Xplus = 0
		Xnone = 0
		Xminus = 0
		for i in range(N):
			Xplus += pow(2, i, X1cnt + 1) * X[-1 - i]
			Xnone += pow(2, i, X1cnt) * X[-1 - i]
			Xminus += pow(2, i, X1cnt - 1) * X[-1 - i]

		Xplus %= X1cnt + 1
		Xnone %= X1cnt
		Xminus %= X1cnt - 1
		for i in range(N):
			if X[i] == 1:
				val = Xminus
				val -= pow(2, N - 1 - i, X1cnt - 1)
				val %= X1cnt - 1
				print(dist[val] + 1)
			else:
				val = Xplus
				val += pow(2, N - 1 - i, X1cnt + 1)
				val %= X1cnt + 1
				print(dist[val] + 1)


if __name__ == '__main__':
	main()

Measured memory_bytes: 120552
#include <iostream>
#include <string>
bool is_month(int i) {
    return  i >= 1 && i <= 12;
}

int main()
{
    std::string str;
    std::cin >> str;
    int tmp = std::atoi(str.c_str());
    int up = tmp / 100;
    int down = tmp % 100;
    bool is_MMYY = is_month(up);
    bool is_YYMM = is_month(down);
    if (is_MMYY&is_YYMM) {
        std::cout << "AMBIGUOUS";
    }
    else if (!is_MMYY && !is_YYMM) {
        std::cout << "NA";
    }
    else if (is_MMYY) {
        std::cout << "MMYY";
    }
    else {
        std::cout << "YYMM";
    }



    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
int main(){
    int A,B,C,D; cin >> A >> B >> C >> D;
    if (B<C||D<A) cout << 0 << endl;
    else cout << min(B,D) - max(A,C) << endl;
}


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

int main(void){
  string st;
  int count = 0, type = -1;
  bool flag = true;
  cin >> st;
  size_t len = st.length();
  size_t i = 0;
  while(i < len){
    string sub = st.substr(i, 5);
    // cout << "*" << sub << i << endl;
    if(sub == "dream"){
      // cout << "!" << "dream" << endl;
      i += 5;
      // cout << "pos:" << i << endl;
      if(st.substr(i, 2) == "er"){
        if(st.substr(i, 3) != "era"){
          i += 2;
        }
        // cout << "pos:" << i << endl;
      }
    }else if(sub == "erase"){
      // cout << "!" << "erase" << endl;
      i += 5;
      // cout << "pos:" << i << endl;
      if(i < len && st.at(i) == 'r'){
        i++;
        // cout << "pos:" << i << endl;
      }
    }else{
      cout << "NO" << endl;
      return 0;
    }
  }
  cout << "YES" << endl;
  return 0;
}

Measured memory_bytes: 512
using System;
using System.Linq;

class
  Program
{
  static void Main(string[] args)
  {
    var x_y = Console.ReadLine().Split(' ');
    var rectangleResult = 1;
    foreach(var val in x_y)
    {
      rectangleResult *= int.Parse(val);
    }

    var areaResult = x_y.Select(x => int.Parse(x)*2).Sum();
    Console.WriteLine(rectangleResult + " " + areaResult);
  }
}

Measured memory_bytes: 9492
class Dice():
  def __init__ (self):
    # 1:ue 2:syomen 3:migi 4:hidari 5:oku 6:shita
    self.position = [0,0,0,0,0,0]
    self.search_result = []
  
  def setNumber (self, num):
    for i,x in enumerate(num):
      self.position[i] = x
    #print(self.position)
      
  def roll(self, roll):
    for i in range(len(roll)):
      s = roll[i:i+1]
      p = self.position
      if s == 'E':
        self.setNumber([p[3], p[1], p[0], p[5], p[4], p[2]])
      elif s == 'W':
        self.setNumber([p[2], p[1], p[5], p[0], p[4], p[3]])
      elif s == 'S':
        self.setNumber([p[4], p[0], p[2], p[3], p[5], p[1]])
      elif s == 'N':
        self.setNumber([p[1], p[5], p[2], p[3], p[0], p[4]])
      elif s == 'R':
        self.setNumber([p[0], p[2], p[4], p[1], p[3], p[5]])
      elif s == 'L':
        self.setNumber([p[0], p[3], p[1], p[4], p[4], p[5]])

  def printTop(self):
    print(self.position[0])

  def searchRight(self, a, b):
    i1 = self.position.index(a)
    i2 = self.position.index(b)
    #print("i1:" + str(i1) + " i2:" + str(i2) )
    
    # 0
    if (i1 == 1 and i2 == 2) or (i1 == 2 and i2 == 4) or (i1 == 4 and i2 == 3) or (i1 == 3 and i2 == 1):
      self.search_result.append(self.position[0])
    # 1
    elif (i1 == 0 and i2 == 3) or (i1 == 3 and i2 == 5) or (i1 == 5 and i2 == 2) or (i1 == 2 and i2 == 0):
      self.search_result.append(self.position[1])
    # 2
    elif (i1 == 0 and i2 == 1) or (i1 == 1 and i2 == 5) or (i1 == 5 and i2 == 4) or (i1 == 4 and i2 == 0):
      self.search_result.append(self.position[2])
    # 3
    elif (i1 == 1 and i2 == 0) or (i1 == 0 and i2 == 4) or (i1 == 4 and i2 == 5) or (i1 == 5 and i2 == 1):
      self.search_result.append(self.position[3])
    # 4
    elif (i1 == 0 and i2 == 2) or (i1 == 2 and i2 == 5) or (i1 == 5 and i2 == 3) or (i1 == 3 and i2 == 0):
      self.search_result.append(self.position[4])
    # 5
    elif (i1 == 2 and i2 == 1) or (i1 == 1 and i2 == 3) or (i1 == 3 and i2 == 4) or (i1 == 4 and i2 == 2):
      self.search_result.append(self.position[5])
    
  def printResult(self):
    for i in self.search_result:
      print (i)
  
  def isSame(self, d):
    for r in ["", "R", "R", "R", 
              "RE",  "R", "R", "R",
              "RE",  "R", "R", "R",
              "RE",  "R", "R", "R",
              "RS",  "R", "R", "R",
              "RNN", "R", "R", "R"]:
      self.roll(r)
      #print(self.position)
      if self.position == d.position:
        print("Yes")
        return
    print("No")
    


d1 = Dice()
d2 = Dice()

n = list(int(x) for x in input().split())
d1.setNumber(n)

n = list(int(x) for x in input().split())
d2.setNumber(n)

d1.isSame(d2)


Measured memory_bytes: 5636
#include<iostream>
using namespace std;
int main(){
  int n[3];
  cin >> n[0] >> n[1] >> n[2];
  if(n[0]==1&&n[1]==1&&n[2]==0||n[0]==0&&n[1]==0&&n[2]==1) cout << "Open" << endl;
  if(n[0]==1&&n[1]==0&&n[2]==0||n[0]==0&&n[1]==1&&n[2]==0||n[0]==0&&n[1]==0&&n[2]==0) cout << "Close" << endl;
  return 0;
}

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

int sum_d(int n) {
  int tot = 0;
  while (n) {
    tot += n % 10;
    n /= 10;
  }
  return tot;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  
  int n, a, b;
  cin >> n >> a >> b;
  
  int tot = 0;
  for (int i = 1; i <= n; i++) {
    int s = sum_d(i);
    if (s >= a && s <= b) tot += i;
  }
  cout << tot << '\n';
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
#define DOR(i,s,t) for(int i=(s),_t=(t); i>=_t; --i)
#define EOR(i,x) for(int i=Head[x]; ~i; i=Nxt[i])

typedef long long ll;

const int M=(int)2e5+50;
const int Mod=(int)1e9+7;

int col[M];
int pos[M];
ll f[M];
int main() {
	int n;
	scanf("%d",&n);
	FOR(i,1,n) {
		scanf("%d",&col[i]);
	}
	f[0]=1;
	FOR(i,1,n) {
		f[i]=f[i-1];
		if(pos[col[i]] && pos[col[i]]!=i-1) {
			f[i]+=f[pos[col[i]]];
		}
		f[i]%=Mod;
		pos[col[i]]=i;
	}
	printf("%lld\n",f[n]);
	return 0;
}

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

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
typedef long long ll;
using namespace std;

int main() {
    string s;
    char c;
    int q, t, f;
    cin >> s >> q;
    deque<char> d;
    for (char cc: s) d.push_back(cc);
    bool isReverse = false;
    rep(i, q) {
        cin >> t;
        if (t == 1) {
            isReverse = !isReverse;
        } else {
            cin >> f >> c;
            if (f == 1) {
                if (isReverse) d.push_back(c);
                else d.push_front(c);
            } else {
                if (isReverse) d.push_front(c);
                else d.push_back(c);
            }
        }
    }

    if (isReverse) {
        reverse(d.begin(), d.end());
    }

    string ans;
    for (char ss:d) ans += ss;

    cout << ans << endl;


    return 0;
}

Measured memory_bytes: 1412
#include <stdio.h>
#include <stdlib.h>
int min(int a, int b)
{
  if(a <= b)
  return a;
  else
  return b;
}

void swap(int *p_from, int *p_to) {
    int tmp;
    tmp = *p_from;
    *p_from = *p_to;
    *p_to = tmp;
}

int main(void)
{
  int a[5], k;
  int i, min, max;
  for(i = 0; i < 5; i++)
  scanf("%d", &a[i]);
  scanf("%d", &k);
  min = a[0];
  max = a[4];
  for(i = 0; i < 5; i++){
    if(min > a[i])
    min = a[i];
    if(a[i] > max)
    max = a[i];
  }
  if(max - min <= k)
  printf("Yay!\n");
  else
  printf(":(\n");
  return 0;
}


Measured memory_bytes: 128
INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))
def do():
    ans=0
    temp=0
    n=INT()
    s=STR()
    for i in s:
        if i=='I':
            temp+=1
            ans=max(ans,temp)
        else:
            temp-=1
    print(ans)
if __name__ == '__main__':
    do()

Measured memory_bytes: 3064
#include <stddef.h>
#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>
 
using namespace std;
int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    string s1, s2, s3 = "";
    cin >> s1 >> s2;
    size_t m = max(s1.size(), s2.size());
    while (s1.size() < m)
      s1.insert(s1.begin(), '0');
    while (s2.size() < m)
      s2.insert(s2.begin(), '0');
    char c = 0;
    auto it1 = s1.rbegin();
    auto it2 = s2.rbegin();
    for (; it1 != s1.rend(); it1++, it2++) {
      char add = *it1 - '0' + *it2 - '0' + c;
      char ch = add % 10 + '0';
      c = add / 10;
      s3.insert(s3.begin(), ch);
    }
    if (c) s3.insert(s3.begin(), c + '0');
    cout << ((s3.size() > 80) ? "overflow" :s3) << endl;
  }
}

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

int main() {
	float sum;
	int i,n,ans,ava;
	cin>>n;
	int in[n];
	sum-0;
	ans=0;
	for(i=0;i<n;i++){
		cin>>in[i];
		sum+=in[i];
	}
	ava=round(sum/n);
	
	for(i=0;i<n;i++){
		ans+=(in[i]-ava)*(in[i]-ava);
	}
	
	cout<<ans;
}

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

int main(){
  int n,a;
  cin >> n;
  int ball[n];
  int cnt[n+1] = {0};
  long long sum=0;
  rep(i,n){
    cin >> a;
    ball[i] = a;
    sum += cnt[a];
    cnt[a]++;
  }

  rep(i,n){
    printf("%lld\n",sum-cnt[ball[i]]+1);
  }
}

Measured memory_bytes: 4096
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
typedef long long int lli;

class exUnionFindTree{
public:
    vector<int> v;
    vector<int> rank;
    vector<lli> diff;
    
    exUnionFindTree(int n){
        v = vector<int>(n);
        rank = vector<int>(n, 0);
        diff = vector<lli>(n, 0);
        for(int i=0; i<n; i++) v[i]=i;
    }
    int Find(int x){
        return _find(x).first;
    }
    pair<int, lli> _find(int x){
        if(v[x] != x){
            pair<int, lli> ret = _find(v[x]);
            v[x] = ret.first;
            diff[x] += ret.second;
        }
        return make_pair(v[x], diff[x]);
    }
    void Union(int a, int b, lli w){
        int ra = Find(a);
        int rb = Find(b);
        if(ra == rb) return;
        if(rank[ra] < rank[rb]){
            v[ra] = rb;
            diff[ra] = diff[b] -diff[a] -w;
        }else{
            v[rb] = ra;
            diff[rb] = diff[a] -diff[b] +w;
            if(rank[ra] == rank[rb]){
                rank[ra]++;
            }
        }
    }
};

int main(){
	while(1){
		int n,m;
		cin >> n >> m;
		if(n==0) break;
		
		exUnionFindTree uft(n+1);
		for(int i=0; i<m; i++){
			char c;
			cin >> c;
			if(c=='?'){
				int a,b;
				cin >> a >> b;
				if(uft.Find(a) == uft.Find(b)){
					cout << uft.diff[b] -uft.diff[a] << endl;
				}else{
					cout << "UNKNOWN" << endl;
				}
			}else{
				int a,b;
				lli diff;
				cin >> a >> b >> diff;
				uft.Union(a, b, diff);
			}
		}
	}
	return 0;
}


Measured memory_bytes: 5592
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+6;
const ll MOD=1e9+7;
const ll Seed=2333;
ll Hash[N];
ll vs[500];
ll vt[500];
ll vis[500];
int main(){
    memset(vis,0,sizeof vis);
    Hash[0]=1;
    for(int i=1;i<=2e5+5;i++)   Hash[i]=Hash[i-1]*Seed%MOD;
    string s,t;
    cin >> s>>t;
    int flag=1;
    for(int i=0;i<(int)s.size();i++)    vs[s[i]]+=(i+1)*Hash[i]%MOD;
    for(int i=0;i<(int)t.size();i++)    vt[t[i]]+=(i+1)*Hash[i]%MOD;
    for(int i=0;i<(int)s.size();i++){
        if(vs[s[i]]==vt[t[i]]){
            if(s[i]==t[i]){
                vis[s[i]]=1;
            }
            else{
                vis[t[i]]=1;
            }
        }
        else{
            cout << "No"<<endl;
            return 0;
        }
    }
    cout <<"Yes"<<endl;

    return 0;
}


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

int main(){
  ll d,t,s;
  std::cin >> d>>t>>s;

  if(t*s>=d)std::cout << "Yes" << '\n';
  else std::cout << "No" << '\n';


  return 0;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
#define scf scanf
#define prf printf
using namespace std;
char a[10000],l;
int main()
{
	cin>>a;
	int k=strlen(a);
	for(int i=0;i<k;i++)
	{
		if(a[i]=='C')l=1;
		if(a[i]=='F'&&l==1){cout<<"Yes";return 0;}
	}
	cout<<"No";
	return 0;
} 
 

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int sum;
		while (true) {
			int T = sc.nextInt();
			int count = 0;
			int nplus = 0;
			if (T == 0)
				break;

			while (!(nplus == T-1)) {
				sum = 0;
				for (int i = 1 + nplus; i < T; i++) {
					sum += i;
					if (sum == T) {
						count++;
						nplus++;
						break;

					}
					if (i == T - 1) {
						nplus++;
					}
				}
			}
			System.out.println(count);
		}
		sc.close();

	}
}


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

typedef long long i64;

const int MAXN = 100000 + 5;
const int MOD = 1e9 + 7;

int N;
i64 answer, dp[MAXN];
int degree[MAXN], lenCnt[MAXN];
int pre[MAXN], nxt[MAXN];
bool vis[MAXN];

bool noSolution = false;

void findCycle()
{
	for (int i = 1; i <= N; i++)
	{
		if (degree[i] > 2)
			return noSolution = true, (void) 0;
		if (degree[i] != 2 || vis[i])
			continue;

		int cur = i;

		do
		{
			if (vis[cur])
				return noSolution = true, (void) 0;
			vis[cur] = true;
			pre[nxt[cur]] = cur;
			cur = nxt[cur];
		} while (cur != i);
	}
}

void processCircleBasedTree()
{
	for (int i = 1; i <= N; i++)
	{
		if (degree[i])
			continue;

		int cur = i, footLen = 0, cycleLen = 0;
		while (!vis[cur])
			vis[cur] = true,
			cur = nxt[cur],
			footLen++;
		do
			cur = pre[cur],
			cycleLen++;
		while (degree[cur] == 1);
		if (footLen < cycleLen)
			answer = answer * 2 % MOD;
		if (footLen > cycleLen)
			return noSolution = true, (void) 0;
	}
}

void countCycle()
{
	for (int i = 1; i <= N; i++)
	{
		if (vis[i])
			continue;
		int cur = i, len = 0;
		do
		{
			vis[cur] = true;
			cur = nxt[cur];
			len++;
		} while (cur != i);
		lenCnt[len]++;
	}
}

int main()
{
	answer = 1;
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> N;

	for (int i = 1; i <= N; i++)
		cin >> nxt[i], degree[nxt[i]]++;

	findCycle();
	if (noSolution)
		return cout << 0 << endl, 0;
	processCircleBasedTree();
	if (noSolution)
			return cout << 0 << endl, 0;
	countCycle();
	if (noSolution)
		return cout << 0 << endl, 0;

	for (int i = 1; i <= N; i++)
	{
		dp[0] = 1LL;
		for (int j = 1; j <= lenCnt[i]; j++)
		{
			dp[j] = dp[j - 1] * (((i % 2 == 0) || i == 1) ? 1 : 2);
			if (j >= 2)
				dp[j] = (dp[j] + ((((dp[j - 2] * (j - 1)) % MOD) * i) % MOD))
						% MOD;
		}

		answer = answer * dp[lenCnt[i]] % MOD;
	}
	cout << answer << endl;
}



Measured memory_bytes: 1920
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
 
#define N (ll)(1e6+3)
#define INF (ll)(1e18+3)
#define MOD (ll)(1e9+7)
 
#define ll long long
#define rep(i,a,n) for(ll i = a; i < n; i++)
#define per(i,a,n) for(ll i = n-1; i >= a; i--)
 
//using namespace __gnu_pbds;
using namespace std;
 
// typedef
// tree<
//     pair<ll,ll>,
//     null_type,
//     less<pair<ll,ll>>,
//     rb_tree_tag,
//     tree_order_statistics_node_update>
// ordered_set;
 
 
ll n, m;
ll cnt[N], dp[N];
ll a[N];
 
void solve() {
    cin >> n >> m;
    rep(i,0,n) {
        cin >> a[i];
        cnt[a[i]]++;
    }
    rep(i,1,n+1) {
        ll l = max(0LL,i-cnt[i]+1);
        rep(j,l,i+1)
            dp[j]++;
    }
    ll ans = 0;
    rep(i,1,n+1) {
        ans += !dp[i];
    }
    rep(i,0,m) {
        ll x, y; cin >> x >> y; x--;
 
        ll del = a[x]-cnt[a[x]]+1;
        cnt[a[x]]--;
        if (del > 0) {
            dp[del]--;
            if (dp[del] == 0)
                ans++;
        }
        ll add = y-cnt[y];
        cnt[y]++;
        if (add > 0) {
            dp[add]++;
            if (dp[add] == 1)
                ans--;
        }
        a[x] = y;
        cout << ans << endl;
    }
}
 
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

Measured memory_bytes: 11264
#!\usr\bin\env python3


def length_of_shotest_string(n, s, t):
    for i in range(n + 1)[::-1]:
        if s.endswith(t[:i]):
            return 2 * n - i


def main():
    n = int(input())
    s = input()
    t = input()
    print(length_of_shotest_string(n, s, t))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include<stdio.h>
int main()
{
  int N,M,i;
  scanf("%d %d",&N,&M);
  if(N<=M){
  for(i=0;i<M;i++){
    printf("%d",N);
  }
  }
  else{
    for(i=0;i<N;i++){
    printf("%d",M);
  }
  }
  return 0;
}
  


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

int main() {
    long long a, b, k;
    cin >> a >> b >> k;
    
    bool a_turn = true;
    
    while (k--) {
        if (a_turn) {
            if (a % 2 == 1)
                a--;
            b += a / 2;
            a /= 2;
            
            a_turn = false;
        }
        else {
            if (b % 2 == 1)
                b--;
            a += b / 2;
            b /= 2;
            
            a_turn = true;
        }
    }
    
    cout << a << " " << b;
}

Measured memory_bytes: 256
N, K, Q = map(int, input().split())
A = [0 for i in range(N)]
for i in range(Q):
    a = int(input())-1
    A[a] += 1

for i in range(N):
    if(K-Q+A[i]>0):
        print("Yes")
    else:
        print("No")

Measured memory_bytes: 4680