akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
using namespace std;

#define F first
#define S second
typedef pair<int, int> P;

int n;
P dat[100010 * 4];

void update(int id, int a){
  int k = id;
  k += n - 1;
  dat[k].F += a;
  dat[k].S = -id;

  while(k > 0){
    k = (k - 1) / 2;
    dat[k] = max(dat[k * 2 + 1], dat[k * 2 + 2]);
  }
}

void init(int n_){
  n = 1;
  while(n < n_) n *= 2;

  for(int i = 0;i < n_; i++) update(i, 0);
}
/*
P query(int a, int b, int k, int l, int r){
  P p;
  p.F = 0; p.S = 0;
  if(r <= a || b <= l) return p;

  if(a <= l && r <= b) return dat[k];
  else{
    P vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
    P vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
    return max(vl, vr);
  }
}
*/

int main(void)
{
  int N, r, l;
  int d, t, x;
  int max_idx = 0;
  int prev_t = 0, time[100010] = {0};
  P p; //p.S = -1;

  scanf("%d %d %d", &N, &r, &l);
  init(N);

  for(int i = 0;i < r; i++){
    scanf("%d %d %d", &d, &t, &x);
    d--;
    //p = query(1, N + 1, 0, 0, n);
    p = dat[0];
    time[-p.S] += t - prev_t;
    update(d, x);
    prev_t = t;
  }
  //p = query(1, N + 1, 0, 0, n);
  p = dat[0];
  time[-p.S] += l - prev_t;
  for(int i = 0;i < N; i++){
    //printf("%d\n", time[i]);
    if(time[max_idx] < time[i])
      max_idx = i;
  }
  printf("%d\n", max_idx + 1);
}


Measured memory_bytes: 4552
#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N,K = LMIIS()
    H = [0]*N
    for i in range(N):
        H[i] = II()
    H.sort(reverse=True)
    mindiff = 10**9
    for i in range(N-K+1):
        mindiff = min(H[i] - H[i+K-1], mindiff)
    print(mindiff)

if __name__ == '__main__':
    main()

Measured memory_bytes: 67672
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
#include<string>

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

using namespace std;

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


int main(){
  int n;
  while(cin >> n,n){
    int r[1024];
    int w[1024];
    int dp[1024];
    const int INF = -100000000;
    int rsum = 0;
    int wsum = 0;
    int mx = -10000000;
    int ind = -1;

    rep(i,n){
      cin >> r[i] >> w[i];
      rsum += r[i];
      wsum += w[i];
      if( r[i] > mx){
        ind = i;
        mx = r[i];
      }
    }

    rsum -= mx;

    if(mx > rsum){
      //length = mx*2
      // pad = mx - rsum;
      int pad = mx -rsum;
      int dp[1024];
      rep(i,1024) dp[i] = -INF;
      dp[0] = 0;

      rep(i,n){
        if(ind != i){
          for(int j = 1024; j >= 0; j--){
            if(dp[j] != -INF && j + w[i] < 1024){
              dp[j+w[i]] = 1;
            }
          }
        }
      }

      for(int i = pad;i > 0; --i){
        if(dp[i] != -INF){
          wsum -= i;
          break;
        }
      }
      cout << 2 * mx + wsum << endl;
    }else{
      cout << rsum + wsum + mx << endl;
    }
  }

  return 0;
}

Measured memory_bytes: 3012
#include <iostream>
#include <cmath>
#include <vector>
#include <set>
using namespace std;
class UnionFind{
    public:
    vector<int> par; //親は何番ですか
    vector<int> size; //集合の要素数を得る

    UnionFind(int n) : par(n),size(n,1){
        for(int i = 0; i < n; i++){
            par[i] = i; //最初の親は自分自身
        }
    }
    void init(int n){
        par.resize(n); 
        size.assign(n,1);
        for(int i = 0; i < n; i++){
            par[i] = i; //最初の親は自分自身
        }
    }

    int root(int x){ //根の検索を再帰的にやります
        if(par[x] == x) return x; //自分が根なら自分が根だと返す
        return par[x] = root(par[x]); //そうでないならxの親はxの親の親
    }

    bool unite(int x, int y){ //併合します
        x = root(x); //xの根
        y = root(y); //yの根
        if(x == y) return false; //根が同じならもう併合済み
        //併合するときは"小さい方"を"大きい方"に併合させる
        if(size[x] < size[y]) swap(x,y); 
        size[x] += size[y];
        par[y] = x; //併合するので親を変える
        return true;
    }

    bool isSame(int x,int y){ //2つの頂点が同じ集合に属するか
        return root(x) == root(y);
    }
    
    int getSize(int x){ //集合の要素の大きさを返します
        return size[root(x)];
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin >> n >> m;
    UnionFind uf(n);
    for(int i = 0; i < m; i++){
        int a,b;
        cin >> a >> b;
        a--; b--;
        if(!(uf.isSame(a,b))) uf.unite(a,b);
    }
    int cnt = 0;
    set<int> st;
    for(int i = 0; i < n; i++){
        int k = uf.root(i);
        if(uf.getSize(i) == 1) cnt++;
        else st.insert(k);
    }
    int sz = st.size();
    cout << abs(sz-cnt) << endl;
    return 0;
}


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

int main()
{
    int n,k;
    cin>>n>>k;
    int arr[n+10];
    for(int i=0; i<n; i++)
        cin>>arr[i];
    sort(arr,arr+n);
    long long sum=0;
    for(int i=0; i<k; i++)
        sum=sum+arr[i];
    cout<<sum<<endl;
}


Measured memory_bytes: 3592
import java.util.Scanner;
import java.time.Year;
import java.util.Random;
import java.math.*;

public class Main{
    public static void main(String[] args){
        Scanner sc =new Scanner(System.in);
        String s = sc.next();
        String t = sc.next();
        String s2="";
        int s_length = s.length();
        int t_length = t.length();
        int count = 0;
        int max=0;
        for(int i = 0;i<(s_length-t_length+1);i++){
            s2=s.substring(i, t_length+i);  
            for(int j=0;j<t_length;j++){
                if(s2.charAt(j)==t.charAt(j)){
                    count++;
                    if(max<count){
                        max = count;
                    }
                }
            }count=0;
        }
    System.out.println(t_length-max);    
    }
}

Measured memory_bytes: 36548
import sys
sys.setrecursionlimit(10**8)
input = lambda: sys.stdin.readline()[:-1]
n,q=map(int,input().split())
ab=[tuple(map(int,input().split())) for i in range(n-1)]
px=[tuple(map(int,input().split())) for i in range(q)]
# ab.sort(key=lambda tup:(tup[0],tup[1]))

cnt=[0]*(n+1)
data=[[] for i in range(n+1)]

for i in ab:
	data[i[0]].append(i[1])
	data[i[1]].append(i[0])
for j in px:
	cnt[j[0]]+=j[1]


stack=[(1,0)]

while stack:
	v,parent=stack.pop()
	for to in data[v]:
		if to == parent:
			continue
		cnt[to]+=cnt[v]
		stack.append((to,v))

	
print(*cnt[1:])

Measured memory_bytes: 130856
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll, ll> P;
using VP = vector<P>;
using VVP = vector<VP>;
using VI = vector<ll>;
using VVI = vector<VI>;
using VVVI = vector<VVI>;
const int inf = 1e9 + 7;
const ll INF = 1LL << 61;
const ll mod = 1e9 + 7;

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

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

int gcd(int a, int b) {
    if (a < b) swap(a, b);
    if (a % b == 0) return b;
    return gcd(a % b, b);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int i, j;
    ll n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;
    int g = gcd(n, m);
    for (i = 0; i < n; i++) {
        if (i * m % n == 0) {
            if (s[i] != t[i * m / n]) {
                cout << -1 << endl;
                return 0;
            }
        }
    }
    cout << n / g * m << endl;
}

Measured memory_bytes: 3776
#include <math.h>

#include <cmath>
#include <iostream>
using namespace std;
int main() {
    string s,t;
    int l,n=0;
    cin >> s>>t;
    l=s.size();
    for (int i = 0; i < l;i++){
        char u = s[i],v=t[i];
        if(u!=v){
            n++;
        }
    }
    cout << n << endl;
    return 0;
}

Measured memory_bytes: 3808
import numpy as np
N = int(input())
a = list(map(int, input().split()))

res = np.cumsum(a)
# print(res)
sum_a = np.sum(a)
ans = 100000000000
for i in range(N - 1):
    tmp = abs((sum_a - res[i]) - res[i])
    # print(tmp)
    if tmp < ans:
        ans = tmp

print(ans)

Measured memory_bytes: 33064
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007;
// const int MOD = 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
const int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
  IOSetup() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
  }
} iosetup;

int main() {
  string s; cin >> s;
  deque<char> deq;
  for (char c : s) deq.emplace_back(c);
  int q; cin >> q;
  bool rev = false;
  while (q--) {
    int t; cin >> t;
    if (t == 1) {
      rev = !rev;
    } else if (t == 2) {
      int f; char c; cin >> f >> c;
      if (f == 1) {
        if (rev) {
          deq.emplace_back(c);
        } else {
          deq.emplace_front(c);
        }
      } else if (f == 2) {
        if (rev) {
          deq.emplace_front(c);
        } else {
          deq.emplace_back(c);
        }
      }
    }
  }
  if (rev) {
    while (!deq.empty()) {
      cout << deq.back();
      deq.pop_back();
    }
  } else {
    while (!deq.empty()) {
      cout << deq.front();
      deq.pop_front();
    }
  }
  cout << '\n';
  return 0;
}


Measured memory_bytes: 976
def main():
    n=int(input())
    aa=list(map(int,input().split()))
    ll={}
    c=0
    for i,a in enumerate(aa,1):
        x=i-a
        if x in ll:
            c+=len(ll[x])
        y=i+a
        if y in ll:
            ll[y].append(i)
        else:
            ll[y]=[i]
    print(c)
main()

Measured memory_bytes: 60756
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>

using namespace std;

int main(void){
	int n;

	cin >> n;

	vector<long long int> a(n);

	long long int sum = 0;
	
	for (int i = 0; i < n; i++){
		cin >> a[i];
		sum += a[i];
	}

	long long int tempsum = 0;


	long long int m = 10000000000000;
	for (int i = 0; i < n - 1; i++){
		tempsum += a[i];
		m = min(m, abs(2*tempsum-sum));
	}


	cout << m << endl;



}

Measured memory_bytes: 1792
package main

import (
	"fmt"
	"strconv"
)

func main() {
	var x string
	fmt.Scan(&x)
	rest := map[int]int{
		0: 1,
	}
	ten := 1
	sum := 0
	for i := len(x) - 1; i >= 0; i-- {
		val, _ := strconv.Atoi(string(x[i]))
		sum = ((ten%2019)*val + sum) % 2019
		ten *= 10
		ten %= 2019
		rest[sum]++
	}
	ans := 0
	for _, v := range rest {
		ans += v * (v - 1) / 2
	}
	fmt.Println(ans)
}


Measured memory_bytes: 3468
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <iostream>
#include <utility>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;

#define ll long long

int main()
{
    ll S, W;
    scanf("%lld %lld", &S, &W);
    if (S > W)
        printf("safe");
    else
        printf("unsafe");
}


Measured memory_bytes: 3720
#define DEB
#include<bits/stdc++.h>
#define REP(i,m) for(int i=0;i<(m);++i)
#define REPN(i,m,in) for(int i=(in);i<(m);++i)
#define ALL(t) (t).begin(),(t).end()
#define CLR(a) memset((a),0,sizeof(a))
#define pb push_back
#define mp make_pair
#define fr first
#define sc second

using namespace std;


#ifdef DEB
#define dump(x)  cerr << #x << " = " << (x) << endl
#define prl cerr<<"called:"<< __LINE__<<endl
#define dumpR(x) cerr<<"\x1b[31m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpY(x) cerr<<"\x1b[33m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
#define dumpG(x) cerr<<"\x1b[32m"<<#x<<" = " <<(x)<<"\x1b[39m"<<endl
template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
#else
#define dump(x) ;
#define dumpR(x) ;
#define dumpY(x) ;
#define dumpG(x) ;
#define prl ;
template<class T> void debug(T a,T b){ ;}
#endif

template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; }
template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; }

typedef long long int lint;
typedef pair<int,int> pi;

namespace std{
  template<class S,class T>
  ostream &operator <<(ostream& out,const pair<S,T>& a){
    out<<'('<<a.fr<<','<<a.sc<<')';
    return out;
  }
}

//const int INF=5e8;

int main(){
#ifdef LOCAL_REDIR
  freopen("/home/hog/Dropbox/pg/working/in.txt","r",stdin);
#endif
  lint a,b,c,d;
  lint n;
  cin>>a>>b>>c>>d>>n;
  lint one=min({a*4,b*2,c});
  lint two=min({a*8,b*4,c*2,d});
  lint res=min(one*n,two*(n/2)+one*(n%2));
  cout<<res<<endl;
  return 0;
}






Measured memory_bytes: 256
// Optimise
#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 MULTI_TEST
#ifdef LOCAL
#include "/home/shahraaz/bin/debug.h"
#else
#define db(...)
#define pc(...)
#endif

#define f first
#define s second
#define pb push_back
#define all(v) v.begin(), v.end()
auto TimeStart = chrono::steady_clock::now();
auto seed = TimeStart.time_since_epoch().count();
std::mt19937 rng(seed);
using ll = long long;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using Random = std::uniform_int_distribution<T>;

const int NAX = 2e5 + 5, MOD = 1000000007;

class Solution
{
private:
public:
    Solution() {}
    ~Solution() {}
    void solveCase()
    {
        int n, m;
        cin >> n >> m;
        cout << (n * (n - 1) / 2) + (m * (m - 1) / 2) << '\n';
    }
};

int32_t main()
{
#ifndef LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif
    int t = 1;
#ifdef MULTI_TEST
    cin >> t;
#endif
    Solution mySolver;
    for (int i = 1; i <= t; ++i)
    {
        mySolver.solveCase();
#ifdef TIME
        cerr << "Case #" << i << ": Time " << chrono::duration<double>(chrono::steady_clock::now() - TimeStart).count() << " s.\n";
        TimeStart = chrono::steady_clock::now();
#endif
    }
    return 0;
}

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

using namespace std;

struct Initializer {
  Initializer() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(15);
  }
} initializer;

int main() {
  int n, a = 0;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    string s;
    cin >> s;
    if (s == "A") {
      ++a;
    } else {
      --a;
      if (a < 0) break;
    }
  }
  cout << (a == 0 ? "YES" : "NO") << endl;
}

Measured memory_bytes: 3180
#include <iostream>
#include <string>
#include <stdlib.h>
using namespace std;

int main(){
  int n,m,A[10000],ans;
  cin>>n>>m;
  ans=n;
  for(int i=0;i<m;i++){
    cin>>A[i];
    ans=ans-A[i];
  }
  if(ans<0) ans=-1;
  cout<<ans;
  return 0;
}

Measured memory_bytes: 3672
n = int(input())
l = sorted(list(map(int,input().split())),reverse=True)
mod = 10**9+7

ans = 0

for i in range(n-1,-1,-1):
    ans += ((2+i)*l[i])
b = pow(2,2*n-2,mod)
print(ans*b%mod)

Measured memory_bytes: 26024
#include <bits/stdc++.h>
#define mem(ar,num) memset(ar,num,sizeof(ar))
#define me(ar) memset(ar,0,sizeof(ar))
#define lowbit(x) (x&(-x))
#define Pb push_back
#define  FI first
#define  SE second
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define IOS ios::sync_with_stdio(false)
#define DEBUG cout<<endl<<"DEBUG"<<endl; 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int    prime = 999983;
const int    INF = 0x7FFFFFFF;
const LL     INFF =0x7FFFFFFFFFFFFFFF;
const double pi = acos(-1.0);
const double inf = 1e18;
const double eps = 1e-6;
const LL     mod = 1e9 + 7;
LL qpow(LL a,LL b){LL s=1;while(b>0){if(b&1)s=s*a%mod;a=a*a%mod;b>>=1;}return s;}
LL gcd(LL a,LL b) {return b?gcd(b,a%b):a;}
int dr[2][4] = {1,-1,0,0,0,0,-1,1};
typedef pair<int,int> P;
const int maxn = 2e5+10;
int a[maxn],b[maxn];
int main(void)
{
	int n;cin>>n;
	for(int i = 1;i <= n; ++i)
		cin>>a[i];
	for(int i = n;i >= 1; --i){
		int t = 0;
		for(int j = i+i;j <= n; j += i)
			t += b[j];
		if(t%2 == a[i])
			b[i] = 0;
		else
			b[i] = 1;
	}
    

   int cnt = 0;
   for(int i = 1;i <= n; ++i)
   	if(b[i])
   		cnt++;
   cout<<cnt<<endl;
   for(int i=1;i <= n; ++i)
   	if(b[i])
   		cout<<i<<" ";

   return 0;
}

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

int main(void){
    int n;
    cin >> n;
    vector<int> a(n);
    int f = 0;
    int s = 0;
    for(int i = 0;i < n;i++){
        cin >> a[i];
        if(a[i] > f){
            s = f;
            f = a[i];
        }else if(a[i] > s){
            s = a[i];
        }
    }
    for(int i = 0;i < n;i++){
        if(a[i] == f){
            cout << s << endl;
        }else{
            cout << f << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 2432
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int h = sc.nextInt();
    int w = sc.nextInt();
    int[][] dp = new int[10][10];
    for(int i = 0; i < 10; i++) {
      for(int j = 0; j < 10; j++) {
        dp[i][j] = sc.nextInt();
      }
    }
    for(int k = 0; k < 10; k++) {
      for(int i = 0; i < 10; i++) {
        for(int j = 0; j < 10; j++) {
          dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
        }
      }
    }
    int ans = 0;
    for(int i = 0; i < h; i++) {
      for(int j = 0; j < w; j++) {
        int a = sc.nextInt();
        if(a != -1) ans += dp[a][1];
      }
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 56248
import sys
sys.setrecursionlimit(505050)

class Combination:
    def __init__(self, n_max, mod=10**9+7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

N = int(input())
G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

Siz = [0] * (N+1)
A = [0] * (N+1)
mod = 10**9 + 7
comb = Combination(202020)
def dfs1(v, p):
    siz = 1
    an_prod = 1
    an_numer = 0
    an_denom = 1
    for u in G[v]:
        if u != p:
            s, a = dfs1(u, v)
            siz += s
            an_prod = an_prod * a % mod
            an_numer += s
            an_denom = an_denom * comb.facinv[s] % mod
    an_numer = comb.fac[an_numer]
    an = an_numer * an_denom % mod * an_prod % mod
    Siz[v] = siz
    A[v] = an
    return siz, an

_, ans = dfs1(1, 0)
# for i in range(1, N+1):
#     print(i, dfs1(i, 0))

Ans = [0] * (N+1)
Ans[1] = ans

def dfs2(v, p, an_p):
    siz_v = Siz[v]
    if v==1:
        ans = A[v]
    else:
        ans = A[v] * comb.fac[N-1] % mod * comb.facinv[siz_v-1] % mod * an_p % mod * comb.facinv[N-siz_v] % mod
        Ans[v] = ans
    for u in G[v]:
        if p != u:
            siz_u = Siz[u]
            an = ans * comb.facinv[N-1] % mod * comb.fac[N-1-siz_u] % mod * comb.fac[siz_u] % mod * pow(A[u], mod-2, mod) % mod
            dfs2(u, v, an)

dfs2(1, 0, None)
print("\n".join(map(str, Ans[1:])))


Measured memory_bytes: 88220
#include<bits/stdc++.h>
using namespace std;
#define nn 3003
#define ll long long
vector<ll> ps;int isp[nn];
void ini()
{
	for(int i=2;i<nn;i++)
	{
		if(!isp[i]) ps.push_back(i);
		for(int j=i+i;j<nn;j+=i) isp[j]=1;
	}
}

ll iss(ll n)
{
	ll t=sqrt(n);
	for(ll i=t-2;i<=t+2;i++) if(i>0)if(i*i==n) return i;
	return 0;
}

map<ll,ll> m,rev;ll cnt1;
void solve(ll n)
{
	if(n==1) 
	{
		cnt1++;
		return ;
	}
	ll nr=1,rr=1;ll cn=n;
	for(int i=0;i<ps.size();i++)
	{
		ll p=ps[i];
		if(n%p==0)
		{
			ll cnt=0;
			while(n%p==0) n/=p,cnt++;
			cnt%=3;
			if(cnt==0) continue;
			if(cnt==1) nr=nr*p,rr=rr*p*p;
			else nr=nr*p*p,rr=rr*p;
		}
	}
	ll tp=iss(n);
	if(tp)
		nr=nr*n,rr=rr*tp;
	else
		nr=nr*n,rr=rr*n*n;
	if(nr==1)
	{
		cnt1++;
		return ;
	}

	rev[nr]=rr,m[nr]++;
}
int main()
{
	ini();
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		ll x;scanf("%lld",&x);
		solve(x);
	}
	ll ans=0;
	for(map<ll,ll>::iterator it=m.begin();it!=m.end();it++)
	{
		ll rr=rev[it->first];
		if(m.count(rr))
			ans+=max(it->second,m[rr]),it->second=m[rr]=0;
		else ans+=it->second,it->second=0;
	}
	cout<<ans+(cnt1>0);
	return 0;
} 


Measured memory_bytes: 12800
#include <bits/stdc++.h>
using namespace std;
#define fo(int, i, a, b)        for (int i=a; i<(b); i++)
#define forev(int, i, b, a)     for (int i = (b)-1; i >= a; i--)
#define uns                     unsigned
#define lli                     long long int
#define ld                      long double
#define all(x)                  x.begin(), x.end()
#define sortall(x)              sort(all(x))
#define enl                     "\n"
// #define PI 3.1415926535897932384626
// const int MOD = 1000000007; const lli INF = 1e18; const int MX = 100001;
//==================================================================================

void solve() {
    string s, t; cin >> s >> t;
    lli cnt = 0;
    for (int i = 0; i < (int)s.length(); ++i) {
        if (s[i] != t[i]) cnt++;
    }

    cout << cnt;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    // int testcase; cin >> testcase; for (int i = 1; i <= testcase; ++i)
    solve();
    return 0;
}

Measured memory_bytes: 3800
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

#define REP(i,n) for(ll (i) = (0); (i) < (n); ++i)
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define ALL(v) v.begin(),v.end()
#define INF 1100000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007
#define Decimal fixed << setpresicion(20)
#define SHOWP(x) cerr<<"["<<(x).FI<<", "<<(x).SE<<"]";
#define SHOWX(x) cerr<<#x<<": "<<x<<endl;
#define SHOWVEC(v, e) REP(i, e) cerr << (v[i]) << ' '; cerr << endl;
#define SHOW2D(a, h, w) REP(i, h){REP(j, w)cerr<<setw(3)<<(a[i][j])<<' ';cerr<<endl;}

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

int main()
{
  string S; cin >> S;
  int y = 0;
  for (int i = 0; i <= 3; i++) {
    y *= 10;
    y += S[i] - '0';
  }
  int m = 0;
  for (int i = 5; i <= 6; i++) {
    m *= 10;
    m += S[i] - '0';
  }
  int d = 0;
  for (int i = 8; i <= 9; i++) {
    d *= 10;
    d += S[i] - '0';
  }
  if (y > 2019) cout << "TBD" << endl;
  else if (y == 2019 && m > 4) cout << "TBD" << endl;
  else if (y == 2019 && m == 4 && d > 30) cout << "TBD" << endl;
  else cout << "Heisei" << endl;

  return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
int main() {
    int a,b,c,v;
    cin >> a >> b >> c;
    v = 1;
    if(a == b && b == c && a == c){
        v = 1; 
    }
    else if(a != b && b != c && a != c){
        v = 3;
    }
    else{
        v = 2;
    }
    cout << v << endl;
}

Measured memory_bytes: 256
N = int(input())
S = [sorted(str(input())) for _ in range(N)]
S.sort()

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

L = []
c = 1
for i in range(N):
    if i == 0:
        pass
    else:
        if S[i-1]==S[i]:
            c += 1
            if i == N-1:
                L.append(c)
        else:
            if c >= 2:
                L.append(c)
            c = 1
res = 0
for x in L:
    res += cmb(x,2)
print(res)

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

int main(){
    ll A;
    double b;
    cin >> A >> b;
    ll ib = b * 100 +.000001; //暗黙の型変換をするが切り捨て
    cout << (A * ib)/100 << endl;
}


Measured memory_bytes: 3700
#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,k;
  cin >> n >> k;
  vector<ll> a(n);
  for(int i = 0;i < n;i++)cin >> a[i];
  sort(a.rbegin(),a.rend());
  ll res = 0;
  for(int i = 0;i < k;i++)res += a[i];
  cout << res << endl;
}

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

using namespace std;

#define ll long long
#define ld long double
#define pll pair <ll , ll>

#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define mp make_pair

#define X first
#define Y second

#define LB(x) ((x) & -(x))
#define BIT(a , b) (((a)>>(b)) & 1)

const ll MAXN=1e5+10;

vector <pll> w[MAXN];

ll pos[MAXN];
ll head[MAXN];

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

	ll n , m;
	cin>>n>>m;

	for(ll i=1;i<=n;i++)
    {
        pos[i]=0;
        head[i]=i;
        w[i].pb(mp(0 , i));
    }

    for(ll i=0;i<m;i++)
    {
        ll v , u , d;
        cin>>v>>u>>d;

        if (head[v]==head[u])
        {
            if (w[head[v]][pos[v]].X-w[head[u]][pos[u]].X!=d)
            {
                cout<<"No";
                return 0;
            }
        }
        else
        {
            ll x=head[v] , y=head[u];

            if (w[x].size()<w[y].size())
            {
                ll k=w[y][pos[u]].X-w[x][pos[v]].X+d;

                while (w[x].size()>0)
                {
                    pos[w[x].back().Y]=w[y].size();
                    head[w[x].back().Y]=y;
                    w[y].pb(mp(w[x].back().X+k , w[x].back().Y));
                    w[x].pob();
                }
            }
            else
            {
                ll k=w[x][pos[v]].X-w[y][pos[u]].X-d;

                while (w[y].size()>0)
                {
                    pos[w[y].back().Y]=w[x].size();
                    head[w[y].back().Y]=x;
                    w[x].pb(mp(w[y].back().X+k , w[y].back().Y));
                    w[y].pob();
                }
            }
        }
    }

    cout<<"Yes";
}


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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

// 最小公倍数
ll lcm(ll a, ll b){
    return a*b/gcd(a, b);
}

ll dp[100010][2];
// i : 調べている桁
// smaller : 対象の数字未満であることが確定しているならば1、そうでなければ0

int main()
{
    cout << fixed << setprecision(15);
    string L;
    cin >> L;

    ll l = L.size();  //Lの長さ
    
    Fill(dp, 0);
    dp[0][0] = 1; //初期条件

    for(int i = 0; i < l; i++){
        for(int smaller = 0; smaller < 2; smaller++){
                if(L[i] == '1'){
                    if(smaller){
                        dp[i+1][1] += dp[i][1] * 3; 
                        dp[i+1][1] = dp[i+1][1]%MOD;
                    }
                    else{
                        dp[i+1][1] += dp[i][0];
                        dp[i+1][1] = dp[i+1][1]%MOD;
                        dp[i+1][0] += dp[i][0]*2;
                        dp[i+1][0] = dp[i+1][0]%MOD;
                    }
                }
                if(L[i] == '0'){
                    if(smaller){
                        dp[i+1][1] += dp[i][1] * 3; 
                        dp[i+1][1] = dp[i+1][1]%MOD;
                    }
                    else{
                        dp[i+1][0] += dp[i][0];
                        dp[i+1][0] = dp[i+1][0]%MOD;
                    }
                }
        }
    }

    cout << (dp[l][0] + dp[l][1]) % MOD << endl;
    return 0;
}

Measured memory_bytes: 2048
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Scanner;
import java.util.Set;


public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int m = scan.nextInt();


		Set<Integer> adj[] = new HashSet[n+1];
		for(int i = 1; i<adj.length; i++) {
			adj[i] = new HashSet<Integer>();
		}


		for(int i = 0; i < m; i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();

			adj[a].add(b);
			adj[b].add(a);
		}

		int[] dist = new int[n+1];
		dist[0] = 0;
		int[] ans = new int[n+1];

		boolean[] end = new boolean[n+1];
		end[1] = true;
		ArrayDeque<Integer> q = new ArrayDeque<>();
		q.add(1);

		while(!q.isEmpty()) {

			int v1 = q.poll();

			int tdist = dist[v1] + 1;

			Iterator<Integer> adjit = adj[v1].iterator();
			while(adjit.hasNext()) {
				int v2 = adjit.next();
				if(!end[v2]) {
					q.add(v2);
					end[v2] = true;

					dist[v2] = tdist;
					ans[v2] = v1;
				}
			}
		}

		PrintWriter out = new PrintWriter(System.out);

		StringBuilder sb = new StringBuilder("Yes\n");
		for(int i = 2; i < n+1; i++) {
			sb.append(ans[i]+"\n");
		}

		out.println(sb);
		out.close();
	}

}


Measured memory_bytes: 98068
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define sz(v) (ll((v).size()))
#define forn(i,n) for(ll i=0;i<(n);i++)
#define forr(i,n) for(ll i=(n)-1;i>=0;i--)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
#define clr(x) memset(x,0,sizeof(x))

const ll mod = 1e9+7;
const ll N = 2e5+5;
ll a[N],b[N];

int main()
{
	ios_base::sync_with_stdio(false);

	ll n,m,k;cin>>n>>m>>k;
	forn(i,n){cin>>a[i];if(i!=0)a[i]+=a[i-1];}forn(i,m){cin>>b[i];if(i!=0)b[i]+=b[i-1];}

	ll ans =0;
	ll ix=0,jx=0;

	while(jx<m && b[jx]<=k)jx++;
	ans = jx;


	forn(i,n){
		if(a[i]>k)break;
		while(jx>0 && a[i]+b[jx-1]>k)jx--;
		ans = max(ans, i+1+jx);
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 6724
#include <iostream>
#include <string>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <ctime>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>
#include <cmath>
#include <assert.h>
#include <iomanip>
#include <bitset>
using namespace std;
#define vi vector<int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define rep(i,a,b) for(int i=a;i<b;i++)
#define per(i,a,b) for(int i=b-1;i>=a;i--)
#define inf 1000000007
#define mod 1000000007
#define x first
#define y second
#define pi acos(-1.0)
#define DBG(x) cerr<<(#x)<<"="<<x<<"\n";

#define FOREACH(it,x) for(__typeof(x.begin()) it=x.begin();it!=x.end();it++)
#define ull unsigned long long
#define ll long long
#define N 100005

template <class T,class U>inline void Max(T &a,U b){if(a<b)a=b;}
template <class T,class U>inline void Min(T &a,U b){if(a>b)a=b;}

//FILE* outFile;

inline void add(int &a,int b){a+=b;while(a>=mod)a-=mod;}
inline int gcd(int a, int b){if(b == 0)return a; return gcd(b, a%b);}
int pow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=ans*(ll)a%mod;
        a=(ll)a*a%mod;b>>=1;
    }
    return ans;
}

int a[N], b[N];
pii res[N];
int main(){
    int j,k,i,T,ca=0, m = 0, K = 0, n;
    scanf("%d", &n);
    rep(i, 0, n){
        scanf("%d", &k);
        if(k >= 0)a[m++] = k;
        else b[K++] = k;
    }
    sort(a, a+m);
    sort(b, b+K);
    int ans = 0, sz = 0;
    if(m == 0){
        ans += b[K-1];
        rep(i, 0, K-1)res[sz++]= {ans, b[i]}, ans -= b[i];
    }
    else if(K == 0){
        ans = a[0];
        rep(i, 2, m)res[sz++] = {ans, a[i]}, ans -= a[i];
        res[sz++] = {a[1], ans};
        ans = a[1] - ans;
    }
    else if(m == 1){
        ans = a[0];
        rep(i, 0, K)res[sz++] = {ans, b[i]}, ans -= b[i];
    }
    else{
        ans = b[0];
        rep(i, 1, m)res[sz++] = {ans, a[i]}, ans -= a[i];
        res[sz++] = {a[0], ans};
        ans = a[0] - ans;
        rep(i, 1, K)res[sz++] = {ans, b[i]}, ans -= b[i];
    }
    printf("%d\n", ans);
    rep(i, 0, sz)printf("%d %d\n",res[i].x, res[i].y);
}



Measured memory_bytes: 3072
h,w = map(int,input().split())
lis = [0 for i in range(26)]
s = [str(input()) for i in range(h)]
for i in range(h):
  for j in range(w):
    lis[ord(s[i][j])-ord("a")] += 1
lis.sort()
cnt1 = 0
cnt4 = 0
for num in lis:
  if num % 2 == 1:
    cnt1 += 1
  cnt4 += num//4
if h % 2 == 0:
  if w % 2 == 0:
    if cnt4 == (h//2)*(w//2):
      print("Yes")
    else:
      print("No")
  else:
    if cnt1 == 0 and cnt4 >= (h//2)*(w//2):
      print("Yes")
    else:
      print("No")
else:
  if w % 2 == 0:
    if cnt1 == 0 and cnt4 >= (h//2)*(w//2):
      print("Yes")
    else:
      print("No")
  else:
    if cnt1 == 1 and cnt4 >= (h//2)*(w//2):
      print("Yes")
    else:
      print("No")


Measured memory_bytes: 3064
n = int(input())
a = list(map(int, input().split()))
                                                                                                                           
fee_sum = 0

for i in range(len(a)):
  if i == 0:
    fee_sum += abs(a[i])
  else:
    fee_sum += abs(a[i] - a[i-1])
else:
  fee_sum += abs(a[i])

for i in range(len(a)):
  diff = 0
  if i == 0:
    diff = abs(a[i+1]) - abs(a[i]) - abs(a[i+1] - a[i])
  elif i == n-1:
    diff = abs(a[i-1]) - abs(a[i]) - abs(a[i] - a[i-1])
  else:
    diff = abs(a[i+1] - a[i-1]) - abs(a[i] - a[i-1]) - abs(a[i+1] - a[i])

  print(fee_sum + diff)

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

int main () {
  int A, B , K ;
  cin >> A >> B >> K ;
  for(int i = 0 ; i < K / 2 ; i ++ ){
    if(A%2==1) A-- ;
    A /= 2 ;
    B += A ;
    if(B%2==1) B-- ;
    B /= 2 ;
    A += B ;
  }
  if(K%2==1){
    if(A%2==1) A-- ;
    A /= 2 ;
    B += A ;
  }
  cout << A << ' ' << B << ' ' << endl ;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define pq priority_queue
using namespace std;
const ll INF=(ll)1e9;
const ll MOD=(ll)1e9+7;
const ll MAX=510000;
vector<int> dx={1,0,-1,0},dy={0,1,0,-1};
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; }

int main(){
    ll X,Y,Z;
    cin>>X>>Y>>Z;
    swap(X,Y);
    swap(X,Z);
    cout<<X<<" "<<Y<<" "<<Z<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("O3")
#define REP(i,n) for(int i=0;i<n;i++)
#define REPP(i,n) for(int i=1;i<=n;i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define EPS (1e-9)
#define INF (1e17)
#define PI (acos(-1))
//const double PI = acos(-1);
//const double EPS = 1e-15;
//long long INF=(long long)1E17;
#define i_7 (long long)(1e9+7)
//#define i_7 998'244'353
long mod(long a){
    long long c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
long long po(long a, long b){
    if(b==0){
        return 1;
    }
    
    long long z = po(a,b/2);
    z = mod(z*z);
    if(b%2!=0){
        z = mod(a*z);
    }
    return z;
}

bool prime_(int n){
  if(n==1){
    return false;
  }else if(n==2){
    return true;
  }else{
    for(int i=2;i<=std::sqrt(n);i++){
      if(n%i==0){
        return false;
      }
    }
    return true;
  }
}

long long gcd_(long long a, long long b){
  if(a<b){
    std::swap(a,b);
  }
  if(a%b==0){
    return b;
  }else{
    return gcd_(b,a%b);
  }
}
 
long long lcm_(long long x, long long y){
  return (x/gcd_(x,y))*y;
}

//using namespace std;
//using namespace boost::multiprecision;
//using namespace __gnu_pbds;

int main(){
  using namespace std;
  long long n, k;
  cin>>n>>k;
  int ans;
  long long temp = 1;
  REP(i, 31){
    if(temp <= n && n < k * temp){
      ans = i + 1;
      break;
    }
    temp *= k;
  }
  cout<<ans<<endl;
  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 a = sc.nextInt();
        int b = sc.nextInt();
        if (Math.abs(a - b) % 2 == 1) {
            System.out.println("IMPOSSIBLE");
        } else {
            System.out.println((a + b) / 2);
        }

    }

}

Measured memory_bytes: 22228
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	private static int N;
	private static int[] a;
	private static int max_sum;
	public static void main(String args[]) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String line;
		while ((line = br.readLine()) != null) {
			
			N = Integer.parseInt(line);
			if(N == 0){
				break;
			}
			
			a = new int[N];
			max_sum = 0;
			for (int i = 0; i < N; i++) {
				a[i] = Integer.parseInt(br.readLine());
				max_sum = max_sum + a[i];
			}

			for(int i=0;i<N;i++){
				if(a[i]<0 && (i == N-1 || a[i+1]>=a[i])){
					continue;
				}
				int sum = 0;
				for(int j=i;j<N;j++){
					sum = sum + a[j];
					if(sum > max_sum){
						max_sum = sum;
					}
				}
			}
			System.out.println(max_sum);
		}
	}
}

Measured memory_bytes: 21932
#include <iostream>
#include <vector>
using namespace std;
int main()
{
    int h, w;
    cin >> h >> w;
    vector<vector<char>> c(h+1, vector<char>(w+1, 0));
    for (int i = 1; i <= h; i++)
    {
        for (int j = 1; j <= w; j++)
        {
            cin >> c[i][j];
        }
    }
    for (int i = 1; i <= 2 * h; i++)
    {
        for (int j = 1; j <= w; j++)
        {
            cout << c[(i + 1) / 2][j];
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 256
N, M  = gets.split.map &:to_i
A = $<.map &:to_i
MOD = 10**9+7
if A.each_cons(2).any?{|a, b| b - a == 1 }
  p 0
  exit
end
NG = [false] * (N + 1)
A.each{|a| NG[a] = true }

dp = [0] * (N + 1)
dp[0] = 1

(1..N).each{|to|
  next if NG[to]
  from_1 = to - 1 >= 0 ? dp[to - 1] : 0
  from_2 = to - 2 >= 0 ? dp[to - 2] : 0
  dp[to] = (from_1 + from_2) % MOD
}
p dp[N]


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

ll gcd(ll a, ll b) {
    if (a < b) swap(a, b);
    return b ? gcd(b, a % b) : a;
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    ll ans = 1;
    for (int i = 0; i < n; ++i) {
        ll a;
        cin >> a;
        ans = lcm(ans, a);
    }
    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 3204
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <numeric>
#include <string>
#include <utility>
#include <vector>

using namespace std;

int main() {
  int n;
  scanf("%d", &n);

  vector<pair<int, int>> v(n);
  for (int i = 0; i < n; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    v[i] = make_pair(x, y);
  }

  vector<int> l(n);
  iota(l.begin(), l.end(), 0);
  
  double total = 0;
  int c = 0;
  do {
    for (int i = 0; i < n - 1; i++) {
      int i1 = l[i], i2 = l[i+1];
      int x1 = v[i1].first, y1 = v[i1].second, x2 = v[i2].first, y2 = v[i2].second;
      // tie(x1, y1) = v[i1];
      // tie(x2, y2) = v[i2];
      total += sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
    }
    c++;
  } while (next_permutation(l.begin(), l.end()));

  cout << setprecision(11) << total / c << endl;
  
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <sstream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>

using namespace std;

#define rep(i,a,n) for(int (i)=a;(i)<(int)(n);(i)++)
#define rrep(i,a,n) for(int (i)=(n)-1;(i)>=a;(i)--)
#define all(x) (x).begin(),(x).end()

typedef long long ll;

const int INF = 1e9;

int main() {
	while (true) {
		int n,x,cnt=0;
		cin >> n >> x;
		if(n==0 and x==0)return 0;
		rep(i,1,n+1) rep(j,i+1,n+1) rep(k,j+1,n+1) {
			if (i+j+k==x)cnt++;
		}
		cout<<cnt<<endl;
	}
}

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

using namespace std;

#define debug(n) cerr << #n << ':' << n << endl;
#define dline    cerr << __LINE__ << endl;

using ll = long long;
template<class T, class U> using P = pair<T,U>;
template<class T> using Heap = priority_queue<T>;
template<class T> using heaP = priority_queue<T,vector<T>,greater<T>>;
template<class T,class U> using umap = unordered_map<T,U>;
template<class T> using uset = unordered_set<T>;

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

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

template<class T, size_t N, class U>
void Fill(T (&a)[N], const U&v){
    fill((U*)a,(U*)(a+N),v);
}

template<class T>
istream& operator >> (istream&is, vector<T>&v){
  for(auto&e:v)is >> e;
  return is;
}



int main(){
  int n; cin >>  n;
  vector<P<int,int>>  v(n);
  for(auto&e:v)cin >> e.first >> e.second;
  double sum = 0;
  vector<ll> kai(10,1);kai[0] = 0;
  for(int i = 2; i < 10; ++i)kai[i] = kai[i-1] * i;
  for(int i = 0; i < n; ++i){
    for(int j = i+1; j < n; ++j){
      sum += sqrt(pow(v[i].first-v[j].first,2)+pow(v[i].second-v[j].second,2))*(2*kai[n-1]);
      debug(sum);
    }
  }
  cout << fixed << setprecision(10) << sum/kai[n] << endl;
  return 0;
}


Measured memory_bytes: 256
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,k = map(int, input().split())
    s = input().rstrip()
    cnt = 0
    for i in range(n-1):
        if s[i]!=s[i+1]:
            cnt += 1
    a = cnt // 2
    b = cnt % 2
    if k<=a:
        print(n-2*(a-k)-1-b)
    else:
        print(n-1)



if __name__ == '__main__':
    main()

Measured memory_bytes: 39408
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //GCC5.4.1で配列の範囲外アクセスをエラーにする

//cmdで g++ test.cpp とするとコンパイルできる
//制限1秒なら10^6は余裕 10^7は多分間に合う 10^8はよほど単純でないと厳しい

typedef long long ll; //long long
typedef pair<int,int> pii; //pair<int,int>

const int MOD=1000000007; //10^9+7
const double PI=3.1415926535;

int main(){
    int N;
    cin>>N;
    vector<string> s(N);
    for(int i=0;i<N;i++){
        cin>>s[i];
        sort(s[i].begin(),s[i].end());
    }
    sort(s.begin(),s.end());
    ll ans=0;
    string prev=s[0];
    ll count=1;
    for(int i=1;i<N;i++){
        if(prev==s[i]){
            count++;
        }else{
            ans+=count*(count-1)/2;
            prev=s[i];
            count=1;
        }
    }
    ans+=count*(count-1)/2;
    cout<<ans<<endl;
}

Measured memory_bytes: 7296
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
using namespace std;
typedef long long ll;
 
int main(){
  ll x,y;
  ll a;
  ll flag = 0;
  cin >> x >> y;
  
  rep(i, x+1){
    a = x - i;
    if((2*a + 4*i) == y) flag = 1;
  }
  if(flag == 0) cout << "No" << endl;
  if(flag == 1) cout << "Yes" << endl;
  return 0;
}

Measured memory_bytes: 3644
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <bitset>
#include <cassert>
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define srep(i,n,m) for(int i=n;i<m;i++)
#define elif else if
#define INF 1000000007
#define pi 3.141592653589793
#define first fi
#define second se
using namespace std;
int sdkys(int a,int b){
    if(b==0) return a;
    return sdkys(b,a%b);
}
int sskbs(int a,int b){
    return a*b/sdkys(a,b);
}
int sosu(int a){
    if(a==2){
        return 1;
    }
    for(int i=2;i<sqrt(a)+1;i++){
        if(a%i==0){
            return 0;
        }
    }
    return 1;
}
vector<int> v;
int n,m,cnt=0,ans=0,aa[220000],ab[220000];
pair<int,int> pp[220000];
string s,ss[220000],sa;
char ch[110][110];
queue<int> que;
signed main(){
    cin>>n>>m>>cnt;
    cout<<n*min(m-1,cnt)/m;
}

Measured memory_bytes: 10556
while True:
    n, m = map(int, input().split())
    if not n and not m:
        break

    votes = [[0] * n for _ in range(m)]
    for i in range(n):
        answer = tuple(map(int, input().split()))
        for j in range(m):
            votes[j][i] += answer[j]
    print(*[t[1] for t in sorted((-sum(s), i + 1) for i, s in enumerate(votes))])

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

/* define const */

/* finish defineing const */

int n, c;
int ad[35][35] = {};
int ac[510][510] = {};
int acnt[3][35] = {};

int main()
{
    cin >> n >> c;
    for (int i = 1; i <= c; i++)
    {
        for (int j = 1; j <= c; j++)
        {
            cin >> ad[i][j];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> ac[i][j];
            acnt[(i + j) % 3][ac[i][j]]++;
        }
    }
    // input

    int mn = (1 << 30);
    for (int i = 1; i <= c; i++)
    {
        for (int j = 1; j <= c; j++)
        {
            for (int k = 1; k <= c; k++)
            {
                /*
                if (i == 1 || j == 2 || k == 3)
                {
                    // cout << "!" << i << " " << j << " " << k << endl;
                    // cout << "yes" << endl;
                }
                */
                if (i == j || j == k || k == i)
                {
                    /*
                    if (i == 1 && j == 2 && k == 3)
                    {
                        // cout << "yes" << endl;
                    }*/
                    continue;
                }
                else
                {
                    int tmp = 0;
                    for (int a = 1; a <= c; a++)
                    {
                        /*
                        cout << "~" << i << " " << j << " " << k << endl;
                        cout << "=" << a << " " << acnt[0][a] << " " << acnt[1][a] << " " << acnt[2][a] << endl;
                        */
                        tmp += ad[a][i] * acnt[0][a];
                        tmp += ad[a][j] * acnt[1][a];
                        tmp += ad[a][k] * acnt[2][a];
                    }
                    mn = min(tmp, mn);
                }
            }
        }
    }
    cout << mn << endl;
}


Measured memory_bytes: 1280
//inlclude前用define 
#define _USE_MATH_DEFINES

//include
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<type_traits>
#include<numeric>
#include<limits>
using namespace std;
//typedef
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<char> VC;

//grobal変数


int main() {
	int n, m, X, Y;
	cin >> n >> m >> X >> Y;
	VI x(n), y(m);
	for (int i = 0; i < n; i++) cin >> x[i];
	for (int i = 0; i < m; i++) cin >> y[i];
	sort(x.begin(), x.end());
	sort(y.begin(), y.end());

	bool flag1 = false;
	bool flag2 = false;

	int memo = y[0];
	if (memo > Y || memo<=X) {
		flag1 = true;
	}

	for (int i = 0; i < n; i++) {
		if (memo <= x[i]) flag2 = true;
	}


	if (flag1 || flag2) cout << "War" << endl;
	else cout << "No War" << endl;

}

Measured memory_bytes: 256