akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

const int INF = 1001001001;

int d[10][1010];

int main() {

  int H, W, K;
  cin >> H >> W >> K;

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

  int answer = INF;

  // 横で切るパターンを全部試す
  for (int bit = 0; bit < 1 << (H - 1); bit++) {

    // グループ番号
    int group = 0;
    
    // 各行がどのグループに属しているかを管理
    vector<int> id(H);
    for (int i = 0; i < H; i++) {
      id[i] = group;
      if (bit >> i & 1) {
        group++;
      }
    }

    // グループの個数は区切った数+1
    group++;

    // データ（グループ内に1が何個あるかを管理する）を初期化
    for (int i = 0; i < group; i++) {
      for (int j = 0; j < W; j++) {
        d[i][j] = 0;
      }
    }

    // 各グループの1の数を数える（まだ行しか見ていない）
    for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++) {
        d[id[i]][j] += (S[i][j] - '0');
      }
    }

    // 線を引いた数
    int count = group - 1;

    // 1が何個あるかを確認するための配列
    vector<int> now(group);

    // 線を引くべきか（false）必要ないか（true）を返す関数
    auto add = [&](int i) {

      // 全部のグループの1の数を数える
      for (int j = 0; j < group; j++) {
        now[j] += d[j][i];
      }

      // K以下かを判定するフラグ
      bool flg = true;
      
      // 全部のグループのうち1個でもKを超えているとダメ
      for (int j = 0; j < group; j++) {
        if (K < now[j]) {
          flg = false;
          break;
        }
      }

      return flg;
    
    };

    // 列（縦）を見ていく
    for (int i = 0; i < W; i++) {

      // Kを超えるグループがある場合はそこで区切る必要がある
      if (!add(i)) {

        // 線を加える
        count++;
        
        // 初期化
        now = vector<int>(group);
        
        // 区切った後もダメな場合はこの区切り方は無理
        if (!add(i)) {
          count = INF;
          break;
        }

      }
    }

    answer = min(answer, count);

  }

  cout << answer << endl;

  return 0;

}

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

Asum = sum(A)
sumdiflist = []

temp = 0
for i in range(N-1):
  temp += A[i]
  sumdif = 2*temp - Asum
  if(sumdif<0):
    sumdif = -sumdif
  sumdiflist.append(sumdif)

print(min(sumdiflist))

Measured memory_bytes: 26024
fun main() {
    val N = readLine()!!.toInt()
    val A = readLine()!!.split(" ").map { it.toInt() }.sorted().toIntArray()

    val max = A.max()!!

    val dp = BooleanArray(max + 1){ true }
    val searched = BooleanArray(max + 1){ false }
    A.forEach { it ->
        var a = it
        if(searched[a]){
            dp[a] = false
            return@forEach
        }
        searched[a] = true
        var i = a * 2
        while (i <= max){
            dp[i] = false
            i += a
        }
    }

    A.filter { a ->
        dp[a]
    }.size.let {
        println(it)
    }
}

Measured memory_bytes: 70432
n, m = map(int, input().split())
s = input()
imos = [0 for _ in range(n)]
for i in range(1, n):
    if s[i-1] == "A" and s[i] == "C":
        imos[i] = imos[i-1]+1
    else:
        imos[i] = imos[i - 1]
for _ in range(m):
    l, r = map(int, input().split())
    if l > 1:
        print(imos[r-1]-imos[l-1])
    else:
        print(imos[r-1])


Measured memory_bytes: 6180
// Bismillahir Rahmanir Rahim .Ya Allah...
#include<bits/stdc++.h>
using namespace std;
typedef long long int  ll;
typedef pair<int,int> PII;
const int mod = 1e9+7,INF = 1e9;
const int mx = 1e5+5;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n,x,t;
    cin>>n>>x>>t;
    int ans = (n+x-1)/x;
    cout<<ans*t<<endl;
    return 0;
}



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

int s(int x){
  int sum = 0;
  while(x>0){
    sum += x % 10;
    x /= 10;
  }
  return sum;
}

int main(){
  int n;
  cin >> n;
  if(n%s(n)==0){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
  return 0;
}

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

int main(){
  int y,m,d;

  char c1,c2;
  string ans = "Heisei";

  cin >>y>>c1>>m>>c2>>d;

  if(y > 2019){
    ans = "TBD";
  };
  if(m > 4){
    ans = "TBD";
  };
   cout <<ans<<endl;
  return 0;
  }


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int H,W;cin>>H>>W;
    vector<vector<char>>Grid(H+2,vector<char>(W+2));
    string s;
    for(int i=0;i<H+2;i++){
        if(i!=0&&i!=H+1)cin>>s;
        for(int j=0;j<W+2;j++){
            if(i==0||i==H+1)Grid[i][j]='.';
            else if(j==0||j==W+1)Grid[i][j]='.';
            else Grid[i][j]=s[j-1];
        }
    }
    int hf[4]={0,-1,0,1};
    int wf[4]={-1,0,1,0};
    bool ans=true;
    bool judge=true;
    for(int i=1;i<H+1;i++){
        for(int j=1;j<W+1;j++){
            if(Grid[i][j]=='#'){
                for(int k=0;k<4;k++){
                    if(Grid[i+hf[k]][j+wf[k]]=='#'){
                        judge=false;
                        break;
                    }
                }
                if(judge)ans=false;
                judge=true;
            }
        }
    }
    if(ans)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<vector>
#include<algorithm>
#include<unordered_map>
#include<map>
#include<iomanip>
using namespace std;
typedef long long ll;
const int maxn = 100005;
const int inf = 1000000007;

int main() {
   // freopen("in.cpp","r",stdin);
    int x,y;
    cin>>x>>y;
    cout<<setprecision(10)<<x*y*1.0/(x+y)<<endl;
    return 0;
}


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

#define eps (1e-10)
struct Point{
    double x,y;
    Point(){}
    Point(double x,double y):x(x),y(y){}
    Point operator+(Point p) {return Point(x+p.x,y+p.y);}
    Point operator-(Point p) {return Point(x-p.x,y-p.y);}
    Point operator*(double k){return Point(x*k,y*k);}
    double norm(){return x*x+y*y;}
    double abs(){return sqrt(norm());}
    bool operator == (const Point &p) const{
    return fabs(x-p.x)<eps && fabs(y-p.y)<eps;
  }
  double dot(Point p){return x*p.x+y*p.y;}
  double det(Point p){return x*p.y-y*p.x;}
};
int ccw(Point a,Point b,Point c){
  Point t1=b-a,t2=c-a;
  if(t1.det(t2)> eps) return 1;//counter clockwise
  if(t1.det(t2)< -eps) return -1;//clockwise
  if(t1.dot(t2)< -eps) return 2;//c-a-b online
  if(t1.norm()<t2.norm()) return -2;//a-b-c online
  return 0;//a-c-b online
}
Point a[101];
int main(){
    int n;
    cin>>n;
    double x,y;
    rep(i,n){
        cin>>x>>y;
        a[i]=Point(x,y);
    }
    bool flag=true;
    rep(i,n){
        if(ccw(a[(i+1)%n],a[i],a[(i+2)%n])==1) flag=false;
    }
    cout<<flag<<endl;
    return 0;
}


Measured memory_bytes: 3240
//ボールを移動させる操作を繰り返したときに、赤いボールが箱iにあることがあり得るか？を各iについて求めたい。
//実際の操作について考えると、赤1個なら絶対移すしかなくて、そうでないなら残すか移すかができる。
//ここら辺で分からなくなるので、今度は「探索」をイメージしてみる。と、実は各時刻について状態がN通りしかない
//と気付く。各箱のボールの個数は操作によらず、どの箱に赤があるか？のみが操作に依存する。
//
//よって、状態数M * NのDPができる。dp[i][j] = i回操作をおこなった直後に箱jに赤ボールがある状態、として考えられる。
//
//今度はdp[i] -> dp[i + 1]を観察する。
//まず、dp[i] -> dp[i + 1]について、dp[i + 1][x], dp[i + 1][y]だけが変化しうる。
//箱x -> y (x ≠ y)とボールを移すとき、箱xにボールが1個なら、次に箱xに(赤い)ボールはない。
//箱yには箱xに赤いボールがある可能性があれば、赤いボールが箱yに入りうる。
//
//よって、dp配列をインラインで持ち、ボールの個数cntも配列で管理しておけばO(N+M)で解くことができる。
//
//ボールが分裂？赤がコピーされて…、ただし1個のときは移動して…みたいに考えても解けるけど、上記の解き方の方が
//正当性も含めて堅実。

#include <iostream>
using namespace std;

int n, m;
int x[100000], y[100000];
int cnt[100000];
bool dp[100000];

int main() {
	int i;
	
	cin >> n >> m;
	for (i = 0; i < m; i++) {
		cin >> x[i] >> y[i];
		x[i]--; y[i]--;
	}
	
	dp[0] = true;
	for (i = 0; i < n; i++) cnt[i] = 1;
	
	for (i = 0; i < m; i++) {
		if (cnt[x[i]] == 1) {
			dp[y[i]] |= dp[x[i]];
			dp[x[i]] = false;
		}
		else {
			dp[y[i]] |= dp[x[i]];
		}
		cnt[x[i]]--;
		cnt[y[i]]++;
	}
	
	int ans = 0;
	for (i = 0; i < n; i++) {
		if (dp[i]) {
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1536
#include <cstdio>
#include <algorithm>

using namespace std;

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

pll gcdLcm(ll a, ll b) {
  ll x = a, y = b;
  if (x < y) swap(x, y);
  while (y > 0) {
    ll r = x % y;
    x = y;
    y = r;
  }
  return pll(x, a*b/x);
}

int main() {
  ll a, b;
  while (scanf("%lld %lld", &a, &b) == 2) {
    pll r = gcdLcm(a, b);
    printf("%lld %lld\n", r.first, r.second);
  }
  return 0;
}

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

int main() {
  vector<char> s(4);
  int ans = 700;

  for (int i = 0; i < 3; i++) {
    cin >> s.at(i);
    if (s.at(i) == 'o') ans += 100;
  }

  cout << ans;

  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <string>
#include <vector>

typedef long long ll;
using namespace std;

int main() {
    string s = "", t = "";
    cin >> s >> t;
    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    reverse(t.begin(), t.end());
    if (s < t) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
while True:
    H, W = [int(i) for i in input().split()]
    if H == W == 0:
        break
    for i in range(H):
        if i % 2 == 0:
            for j in range(W):
                if j % 2 == 0:
                    print('#', end='')
                else:
                    print('.', end='')
            else:
                print('')
        else:
            for j in range(W):
                if j % 2 == 0:
                    print('.', end='')
                else:
                    print('#', end='')
            else:
                print('')
    print('')

Measured memory_bytes: 9148
a, b, k = map(int, input().split())
lst1 = []

if k <= b-a:
    for i in range(k):
        lst1.append(a+i)
        lst1.append(b-i)

    lst2 = sorted(list(set(lst1)))

    for i in range(len(lst2)):
        print(lst2[i])

else:
    for i in range(b-a+1):
        print(a+i)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
//const int INF = 1e8;
using namespace std;

int main(){
	string s, t;
	cin >> s >> t;
	rep(i,3){
		if(s[i] != t[2 - i]){
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;
}


Measured memory_bytes: 256
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <list>
#include <numeric>
#include <cstdlib>

bool valid(const std::string &s, size_t k) {
  if (k % 15 == 0) {
    if (s != "FizzBuzz") return false;
  } else if (k % 3 == 0) {
    if (s != "Fizz") return false;
  } else if (k % 5 == 0) {
    if (s != "Buzz") return false;
  } else {
    size_t x=atoi(s.c_str());
    if (x != k) return false;
  }
  return true;
}

int testcase_ends() {
  size_t m, n;
  scanf("%zu %zu", &m, &n);
  if (m == 0 && n == 0)
    return 1;

  std::list<int> pp(m);  // players
  std::iota(pp.begin(), pp.end(), 1);
  auto it=pp.begin();
  for (size_t i=1; i<=n; ++i) {
    char buf[32];
    scanf("%s", buf);
    std::string s=buf;
    if (pp.size() <= 1) continue;

    if (!valid(s, i)) {
      auto tmp=it++;
      pp.erase(tmp);
    } else {
      ++it;
    }
    if (it == pp.end())
      it = pp.begin();
  }
  
  it = pp.begin();
  while (it != pp.end()) {
    printf("%d%c", *it, std::next(it)!=pp.end()? ' ':'\n');
    ++it;
  }
  return 0;
}

int main() {
  while (!testcase_ends()) {}
}



Measured memory_bytes: 2912
import sys
import math
from collections import deque

def insertion_sort(a, n, g):
    ct = 0
    for i in range(g,n):
        v = a[i]
        j = i-g
        while j >= 0 and a[j] > v:
            a[j+g] = a[j]
            j = j-g
            ct += 1
        a[j+g] = v
    return ct

n = int(input())
a = list(map(int, sys.stdin.readlines()))
b = 701
ct= 0
g = deque([x for x in [701,301,132,57,23,10,4,1] if x <= n])
while True:
    b = math.floor(2.25*b)
    if b > n:
        break
    g.appendleft(b)

for i in g:
    ct += insertion_sort(a, n, i)

print(len(g))
print(*g, sep=" ")
print(ct)
print(*a, sep="\n")

Measured memory_bytes: 118832
#include <iostream>
#include <algorithm>
#define llint long long
#define mod 998244353

using namespace std;

llint n;
llint a[100005];

llint gcd(llint a, llint b)
{
	if(b == 0) return a;
	return gcd(b, a%b);
}

int main(void)
{
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	sort(a+1, a+n+1);
	
	llint ans = 1;
	for(int i = 1; i <= n; i++){
		ans *= gcd(i-1, a[i]), ans %= mod;
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 1024
s = int(input())

def f(n):
    if n%2 == 0:
        return n/2
    else:
        return 3*n+1


a = [s]
for i in range(10**6):
    tmp = f(a[i])
    if tmp in a:
        print(i+2)
        exit()
    a.append(f(a[i]))


Measured memory_bytes: 2940
#include <iostream>
#include <iomanip> 
#include <cstdlib>
#include <cmath>
#include<map>
#include<string.h>
#include <algorithm>
#include <bits/stdc++.h> 
#include<vector>
 
using namespace std;
#define rep(i,a,b)    for(int i=a;i<b;i++)
#define repn(i,a,b)   for(int i=a;i>=b;i--)
#define vi vector<int>
#define vb vector<bool>
#define vs vector<string>
#define vl vector<long long int>
//#define viadj[n+1] vector<int>adj[n+1] 
#define sortA(arr)   sort(arr.begin(),arr.end())
#define sortC(arr,n)   sort(arr,arr+n,comparefunc())
#define search(arr,c)  binary_search(arr.begin(),arr.end(),c)
#define pb   push_back
#define ll long long
#define LCM(a,b) boost::math::lcm(a,b)
#define mp make_pair
#define pll pair<long long int,long long int>
 vb isprime(1e7+1,true);
 
struct node{
     ll lenght;};
        
void Sieve(ll maxn){ 
    ll j;isprime[0]=isprime[1]=false;
    rep(i,2,sqrt(maxn)+1)
    {
        if(isprime[i]){
            for(j=i*i;j<=maxn;j+=i){
                isprime[j]=false;
            }
        }
    }
} 
 struct comparefunction{
bool operator()(const pll c,const pll d)const{
    ll lenc=c.second-c.first+1;
    ll lend=d.second-d.first+1;
    if(lenc!=lend)
    return lenc>lend;
    else
    return c.first<d.first;
   
     
}};
 
  
 
   void dfs(ll v,vb visited,vi adj[]) {
    visited[v] = true;
 
    
    for (int u : adj[v]) {
       if (!visited[u])
            dfs(u,visited,adj);
    }
   
    
}
 
 ll modpow(ll x, ll n,ll p){
     if(n==0)
     return 1;
     if(n==1)
     return x%p;
     if(n%2==0)
     return (modpow(x,n/2,p)%p)*(modpow(x,n/2,p)%p);
     else
     return (x%p)* (modpow(x,n/2,p)%p)*(modpow(x,n/2,p)%p);
 }
 
 
 
int main()
{
    
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 
   
    ll check1=0,check2=0,check3=0;
    ll counti=0, i=0,j;
    ll sum=0,count=0;ll t;ll p;
  // cin>>t;
  //while(t--){
 ll n;
 cin>>n;
 ll num1=n%10;
 if(num1==1||num1==0||num1==6||num1==8)
 cout<<"pon";
else if(num1==3)
 cout<<"bon";
 else
 cout<<"hon";
//}
    
}
  



 
   
 
 

Measured memory_bytes: 4400
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; i++)
#define repo(i, n) for(int i=1; i<=n; i++)
#define INF 1001001001
#define INFll 100100100100100
// debug用
#define PrintVec(x) for (auto elementPrintVec: x) { cout << elementPrintVec << " "; } cout << endl;

using namespace std;
using ull = unsigned long long;
using ll = long long;
using P = pair<int, int>;
const int mod = 1000000007;

int main(){
  int n, k;
  cin >> n >> k;
  if(k>(n-1)*(n-2)/2){
    cout << "-1" << endl;
  } else {
    int num=(n-1)*(n-2)/2-k;
    int m=n-1+num;
    cout << m << endl;;
    repo(i, n-1){
      cout << "1 " << i+1 << endl;
    }
    for(int i=2; i<=n && num>0; i++){
      for(int j=i+1; j<=n && num>0; j++){
        cout << i << " " << j << endl;
        num--;
      }
    }
  }
  return 0;
}


Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a) for(int i=0; i<(a); i++)
typedef long long ll;
template<typename T>
struct edge {
  int src, to;
  T cost;
  edge(int to, T cost) : src(-1), to(to), cost(cost) {}
  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}
  edge &operator=(const int &x) {
    to = x;
    return *this;
  }
  operator int() const { return to; }
};
template<typename T>
using Edges = vector<edge<T>>;
template<typename T>
using WeightedGraph = vector<Edges<T>>;
using UnWeightedGraph = vector<vector<int>>;
template<typename T>
using Matrix = vector<vector<T>>;

/////////////////////////////////////////////////////////////////////
const ll inf = 1LL<<60;

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

  int cnt = 0;
  rep(i, h) rep(j, w) if (a[i][j] == '#') cnt++;
  if (cnt == h+w-1) cout << "Possible" << endl;
  else cout << "Impossible" << endl;

  return 0;
}


Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
long long l[90],N;
int main()
{
	cin>>N;
	l[0]=2;
	l[1]=1;
	for(int i=2;i<=N;i++)
	{
		l[i]=l[i-1]+l[i-2];
	}
	cout<<l[N]<<endl;
	return 0;
}

Measured memory_bytes: 256
function Main(s){
  s = s.split("\n");
  var n = s[0].split(" ").map(a=>+a);
  var k = n[1];
  n = n[0];
  var a = s[1].split(" ").map(a=>+a);
  var x = a.findIndex(a=>a===1);
  console.log(Math.ceil((n-1)/(k-1)));
}
Main(require("fs").readFileSync("/dev/stdin","utf8"));

Measured memory_bytes: 24008
import sys


def main():
    input = sys.stdin.buffer.readline
    a, b, c, x, y = map(int, input().split())
    ans = 0
    if 2 * c < a + b:
        m = min(x, y)
        ans += 2 * c * m
        x -= m
        y -= m
    if 2 * c < a:
        ans += 2 * c * x
        x = 0
    if 2 * c < b:
        ans += 2 * c * y
        y = 0
    ans += a * x + b * y
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 9192
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
#include <complex>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <functional>
#include <assert.h>
using ll=long long;
#define int ll
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define SZ(x) ((int)x.size())
#define fi first
#define se second
const int INF = 1e15;
using namespace std;

template<class T> using vc=vector<T>;
template<class T> using vvc=vc<vc<T>>;

using pi=pair<int,int>;
using vi=vc<int>;

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 cnt=0;
vector<int> divisor(int n){
    vector<int> ret;
    for(int i=1; i*i<=n; i++){
        if(n%i==0){
            ret.push_back(i);
            int pos=n/i;
            while(i!=1){
                if(pos%i){
                    if(pos%i==1) cnt++;
                    break;
                }
                pos/=i;
            }
            if(i*i!=n) ret.push_back(n/i);
        }
    }
    sort(begin(ret),end(ret));
    return(ret);
}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(20);

    int N; cin >> N;
    divisor(N);
    int ans=cnt;
    cout << ans + divisor(N-1).size() << endl;
}

Measured memory_bytes: 384
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


n,m = map(int,input().split())
uf = UnionFind(n)
q = []
for i in range(m):
    a,b = map(int,input().split())
    q.append([a-1,b-1])
ans = n*(n-1)//2
l = []
for i in range(m-1,-1,-1):
    a,b = q[i]
    l.append(ans)
    if not uf.same(a,b):
        ans -= uf.size(a)*uf.size(b)
    uf.union(a,b)
for i in l[::-1]:
    print(i)

Measured memory_bytes: 29484
def makestr(lst):
	s = ''
	for i in range(0, len(lst)):
		s = s + lst[i]
	return s

N = int(raw_input())
queue = [[]]
cnt = 0
while(True):
	now = queue.pop(0)
	if now != []:
		if int(makestr(now)) > N: break
		elif '3' in now and '5' in now and '7' in now:
			cnt += 1
	lst = ['3', '5', '7']
	for i in range(0, 3):
		next = []
		for j in range(0, len(now)):
			next.append(now[j])
		next.append(lst[i])
		queue.append(next)

print cnt

Measured memory_bytes: 15492
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
#define rep(i,n) for(int i=0, i##_len=(int)(n); i<i##_len; i++)
#define reps(i,n) for(int i=1 , i##_len=(int)(n);i<=i##_len;i++)
#define rrep(i,n) for(int i=((int)(n)-1);i>=0;i--)
#define rreps(i,n) for(int i=((int)(n));i>0;i--)
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
#define mp make_pair
#define pb push_back
#define solve(a) ((a)?"Yes":"No")
typedef vector<long long> V;
typedef vector<V> VV;
typedef pair<long long , long long> P;
typedef vector<P> VP;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1;} return 0;}
const long long INFLL = 1LL<<62;
const int INF = 1<<30;
const double PI=acos(-1);
ll func(int at,V &dp){
    if(dp[at]==-1){
        dp[at]=func(at-1,dp)+func(at-2,dp);
    }
    return dp[at];
}
int main(){
    int n;
    cin >> n;
    vector<ll>dp(n+3,-1);  
    dp[0]=1LL;
    dp[1]=1LL;

    cout << func(n, dp)<< endl;
}


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

#define MIN(X,Y) ((X)<(Y)?(X):(Y))
#define ABS(X) ((X)>0?(X):-(X))

int main(){
  int n, ans;
  string s;
  
  cin >> s;
  ans = 1000;
  for (int i=0; i<s.size()-2; i++){
    n = (s[i]-'0')*100 + (s[i+1]-'0')*10 + (s[i+2]-'0');
//    cout << n << endl;
    ans = MIN(ans, ABS(n-753));
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<queue>
#include<deque>
#include<map>
#include<vector>
#include<math.h>
long long int mod = 1000000007;
long long modpow(long long a, long long n, long long mod);
long long modinv(long long a, long long mod);
long long int a[200000];
using namespace std;
int main() {
	
	//C
	int n;

	cin >> n;
	int i;
	for (i = 0; i < n; i++) {
		cin >> a[i];
	}
	long long int s = 0;
	long long int m = a[0];
	for (i = 1; i < n; i++) {
		if (a[i] > m) {
			m = a[i];
		}
		else {
			s = s + m - a[i];
		}
	}
	cout << s << endl;
	return 0;

	//B
	/*string s;
	cin >> s;
	int n = 0;
	int i;
	for (i = 0; i < s.length(); i++) {
		n = n + (s[i] - '0');
		n = n % 9;
	}
	if (n == 0) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;

	}
	return 0;*/

	//A
	/*int n, x, t;
	cin >> n >> x >> t;
	cout << ((n - 1) / x) * t + t << endl;

	return 0;
	*/
}
// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
	long long res = 1;
	while (n > 0) {
		if (n & 1) res = res * a % mod;
		a = a * a % mod;
		n >>= 1;
	}
	return res;
}

// a^{-1} mod を計算する
long long modinv(long long a, long long mod) {
	return modpow(a, mod - 2, mod);
}

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

int choice(int A, int B, int X, int Y) {
  if (X > Y) return A;
  if (X < Y) return B;
}

int main() {
  int A, B, C, X, Y, M, m, aorb, s;
  cin >> A >> B >> C >> X >> Y;
  M = max(X, Y);
  m = min(X, Y);
  aorb = choice(A, B, X, Y);
  s = 0;
  if (A + B <= 2 * C) s = A * X + B * Y;
  else s = min(2 * C * M, 2 * C * m + (M - m) * aorb);
  
  cout << s << endl;
}


Measured memory_bytes: 3588
#include <iostream>
#include <vector>
#include <numeric>
#include <cmath>
#include <algorithm>
#include<string>
#include <iomanip>
#define myfor(i,N) for(i=0;i<N;i++)
#define myforFL(i,f,l) for(i=f;i<l;i++)

using namespace std;

int main(void){
	long L;
	float ans;
	cin >> L;
	ans = (L/3.)*(L/3.)*(L/3.);
	cout <<setprecision(10)<< ans << endl;
	return 0;
}

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

// Author - Kevin Mathew
// Birla Institute of Technology, Mesra

ll n;
ld a[3010];
ld dp[3010][3010];

ld solve(ll x, ll rem){
	// cout << x << " " << rem << "\n";
	if(x == n){
		return 1.0;
	}
	if(dp[x][rem] != -1.0)
		return dp[x][rem];

	if(rem > 0)
		return dp[x][rem] = (1-a[x]) * solve(x+1, rem-1) + (a[x]) * solve(x+1, rem);
	else
		return dp[x][rem] = (a[x]) * solve(x+1, rem);
}

void te(){
	cin >> n;
	for(ll i=0;i<n;i++){
		for(ll j=0;j<n;j++)
			dp[i][j] = -1.0;
		cin >> a[i];
	}

	cout << solve(0, ((n/2))) << "\n";
}

int main()
{
	//freopen("input.txt", "r", stdin);		//Comment
	//freopen("output.txt", "w", stdout);		//this out.
	ios::sync_with_stdio(false);			//Not
	cin.tie(NULL);							//this.
	cout.tie(0);							//or this.
	cout << fixed << setprecision(10);

	te();

	return 0;
}

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

int main() {
  int N;
  int L[N];
  cin >> N;
  int max = 0;
  int sum = 0;
  for (int i = 0; i < N; i++) {
    int l;
    cin >> l;
    if (l > max) max = l;
    sum += l;
  }
  if (sum - max > max) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 256
#include <vector>
#include <iostream>
#include <cmath>
#include <cassert>
#include <map>
#include <set>
#include <deque>
#include <algorithm>
using namespace std;

const int maxn = 2e6, mod = 1e9 +7;

int n, m, cnt[maxn], used[maxn];

int main() {
	ios_base::sync_with_stdio(0);
	cin >> n >> m;
	if(n > 0 && m > 0) return cout << "Positive", 0;
	if(n <= 0 && m >= 0) return cout << "Zero", 0;
	if(abs(n - m) % 2 == 1) return cout << "Positive", 0;
	cout << "Negative";
}


//22 84 84 22
//1  2  3 4  2
//

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

int main() {
  
  int N;
  cin >> N;
  
  vector<int> X(N);
  vector<int> Y(N);
  
  for (int i = 0; i < N; i++) {
    cin >> X[i];
    Y[i] = X[i];
  }
  
  sort(Y.begin(), Y.end());
  
  int A = Y[N / 2 - 1];
  int B = Y[N / 2];
  
  for (int i = 0; i < N; i++) {
    if (X[i] <= A) cout << B << endl;
    else cout << A << endl;
  }
  
}

Measured memory_bytes: 3712
#ifdef __LOCAL
  #define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
template<typename T> bool chmax(T &a,T b) {if(a<b) {a=b; return true;} return false;}
template<typename T> bool chmin(T &a,T b) {if(a>b) {a=b; return true;} return false;}
#define itn int
#define fi first
#define se second
#define intmax numeric_limits<int>::max()
#define llmax numeric_limits<ll>::max()
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(int)(n);i>=1;i--)
#define all(vec) vec.begin(),vec.end()
#define sortt(vec) sort((vec).begin(),(vec).end())
#define rsort(vec) sort((vec).rbegin(), (vec).rend())
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef tuple<ll,ll,ll> tlll;
typedef tuple<int,int,int> tiii;
const ll mod=1e9+7;
const int inf=1<<30;
const ll lnf=1ll<<60;

template<typename T>
struct BIT{
  int n;
  vector<T> d;
  BIT(int n=0):n(n),d(n+1){}
  void add(int i,T x=1) {
    for(i++;i<=n;i+= i&-i){
      d[i]+=x;
    }
  }
  T sum(int i){
    T x=0;
    for(i++;i;i-= i&-i){
      x+=d[i];
    }
    return x;
  }
  T sum(int l,int r){  //l~r-1のΣ
    return sum(r-1)-sum(l-1);
  }
  ll tentousuu(vector<T> a){  //aの値を0から始める
    ll ans=0;
    for(int j=0;j<n;j++){
      ans+=j-sum(a[j]);
      add(a[j],1);
    }
    return ans;
  }
};

int main(){
  itn n,q; cin >> n >> q;
  BIT<ll> bit(n);
  rep(i,n){
    itn a; cin >> a;
    bit.add(i,a);
  }
  vector<ll> ans(0);
  rep(i,q){
    itn t,u,v;
    cin >> t >> u >> v;
    if(t==0) bit.add(u,v);
    else ans.push_back(bit.sum(u,v));
  }
  rep(i,ans.size()){
    cout << ans[i] << endl;
  }
  
}

Measured memory_bytes: 10268
use proconio::{fastout, input};
#[allow(unused_mut)]
#[fastout]
fn main() {
    input! {
        n: usize,
        x: usize,
        t: usize
    }
    let a = if n % x == 0 { n / x } else { n / x + 1 };
    let res = a * t;
    println!("{}", res);
}


Measured memory_bytes: 2092
import sys

def main():
    line_odd = sys.stdin.readline().rstrip()
    line_ev = sys.stdin.readline().rstrip()

    len_odd = len(line_odd)
    len_ev = len(line_ev)
    if len_odd > len_ev:
        ans = "".join(["".join(tpl) for tpl in zip(line_odd, line_ev)]) + line_odd[-1]
        print(ans)
    elif len_odd < len_ev:
        ans = "".join(["".join(tpl) for tpl in zip(line_odd, line_ev)]) + line_ev[-1]
        print(ans)
    else:
        ans = "".join(["".join(tpl) for tpl in zip(line_odd, line_ev)])
        print(ans)
    return 0

if __name__ == '__main__':
    sys.exit(main())


Measured memory_bytes: 3064
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define pb push_back
#define pll pair<ll,ll> 
#define mll map<ll,ll>
#define pii pair<int,int>
#define rep(i,n) for(int i=0; i<n; i++)
#define All(x,v) for(auto x:v)
#define arrin(a,n) ll a[n]; rep(i,n) cin>>a[i]
#define vi vector<int>
#define nl "\n"
#define print(arr) All(x,arr) cout<<x<<" "; cout<<nl
#define sz(x) (int)x.size()
#define all(v) v.begin(),v.end()
#define ing(m,ad) rep(i,m){ int u,v; cin>>u>>v; u--;v--; ad[u].pb(v); ad[v].pb(u);}
#define vdsort(v) sort(v.begin(),v.end(),greater<int>())
#define F first
#define S second
#define mod 1000000007
const int MAXN=100005;
int spf[MAXN];
ll fac1[MAXN],fac2[MAXN],inv[MAXN];
ll gcd(ll x, ll y){ return y?gcd(y,x%y):x; }

void sieve(){  
    spf[1] = 1; 
    for (int i=2; i<MAXN; i++)  spf[i] = i; 
    for (int i=4; i<MAXN; i+=2) spf[i] = 2; 
    for (int i=3; i*i<MAXN; i++) { 
        if (spf[i] == i) 
            for (int j=i*i; j<MAXN; j+=i) 
                if (spf[j]==j)  spf[j] = i; 
    } 
} 
vector<int> getFactorization(int x){
    vector<int> ret; 
    while (x != 1) { 
        ret.push_back(spf[x]); 
        x = x / spf[x]; 
    } 
    return ret; 
}

ll exp(ll n, ll m){
    ll a = 1;
    while (m){
        if (m & 1) a = (a * n % mod) % mod;
        m /= 2;
        n = (n*n) % mod;
    }
    return a;
}

void pre(){
    fac1[0]=fac2[0]=inv[1]=1;
    for(int i=1;i<MAXN;i++){
        fac1[i]=(fac1[i-1]*i)%mod;
        if(i>1) inv[i]=( mod - ((ll)(mod/i)*inv[mod%i])%mod ) %mod;
    }
    for(int i=1;i<MAXN;i++) fac2[i]=(fac2[i-1]*inv[i])%mod;
}
ll C(int n,int k){
    if(n<k) return 0;
    return ((fac1[n]*fac2[n-k]%mod)*fac2[k]%mod);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
    int n,t=1;
    // cin>>t;
    while(t--){
        cin>>n;
        if(n==0) cout<<"1\n"; else cout<<"0\n";
    }
    return 0;
}

Measured memory_bytes: 3100
s = input()
def is_gumoziretu(s):
    if s[:len(s)//2] == s[len(s)//2:]:
        return True
    else:
        return False
i = 1
while(True):
    if is_gumoziretu(s[:len(s)-i]):
        print(len(s[:len(s)-i]))
        exit()
    i += 1


Measured memory_bytes: 3060
loop do
  n = gets.to_i
  if n == 0 then break; end

  a = 0
  b = 0

  0..n.times{
    (ap, bp) = gets.split.map(&:to_i)
    if ap > bp then
      a += ap + bp
    elsif ap < bp then
      b += ap + bp
    else
      a += ap
      b += bp
    end
  }

  puts "#{a} #{b}"
end

Measured memory_bytes: 6104
#include<stdio.h>
#include<string.h>

int main()
{
	char s[16],t[16],st[16];
	scanf("%s%s",s,t);
	char ch;
	int a,b;
	scanf("%d%d",&a,&b);
	ch=getchar();
	scanf("%s",st);
	if (strcmp(s,st)==0)	a--; 
	if (strcmp(t,st)==0)	b--;
	printf("%d %d",a,b);
	return 0;	
}


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

int main(){
  int a,b,c,d,e,sum,kotae;
  cin >> a >> b >> c;
  sum=a+b+c;
  d=max(a,b);
  e=max(d,c);
  
  int n;
  cin >> n;
  int i,k;
  k=e;
  for ( i=1;i<=n;i++ ){
    k=k*2;
  }
  kotae=sum-e+k;
  
  cout << kotae << endl;
}

  

Measured memory_bytes: 256
#include <stdio.h>

int main(void){
  int A,B;
  scanf("%d%d",&A,&B);

  int rank[13] = {12,0,1,2,3,4,5,6,7,8,9,10,11};

  A--; B--;
  if(rank[A] > rank[B]) printf("Alice\n");
  else if(rank[A] < rank[B]) printf("Bob\n");
  else printf("Draw\n");
  return 0;
}

Measured memory_bytes: 128
package main

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

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	sc.Scan()
	iv, _ := strconv.Atoi(sc.Text())
	return iv
}

func init() {
	sc.Split(bufio.ScanWords)
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func main() {
	n := scanInt()
	mx := math.MinInt64
	mn := math.MaxInt64
	for i := 0; i < n; i++ {
		a := scanInt()
		mx = max(mx, a)
		mn = min(mn, a)
	}
	fmt.Println(mx - mn)
}


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

int main(){
    int n,k;
    cin >> n >> k;
    int a[n];
    int i_1;
    for(int i=0;i<n;i++){
        cin >> a[i];
        if(a[i] == 1){
            i_1 = i;
        }
    }
    int ans ;
    ans = (n-2+(k-1))/(k-1);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 640
#ベルマンフォード法
#正の閉路がない時は普通のベルマンフォード法
n,m=list(map(int,input().split()))
es=[]
for i in range(m):
  a,b,c=list(map(int,input().split()))
  es.append((a-1,b-1,c))
import sys
def Bellmanford(n,m,s,es):
  d=[-float("INF")]*n
  d[s]=0
  cnt=0
  while(1):
    update=False
    for p,q,r in es:
      if d[p]!=-float("INF") and d[q]<d[p]+r:
        d[q]=d[p]+r
        update=True
    cnt+=1
    if not update:
      break
    if cnt==n-1:
      memo=d[n-1]
    if cnt==n+1:
      #正のループがある
      if d[n-1]>memo:
        print(float("INF"))
        sys.exit()
      else:
        print(d[n-1])
        sys.exit()
  print(d[n-1])
  
Bellmanford(n,m,0,es)  
    
    
      
  
  

  

Measured memory_bytes: 75104
def gcd(x, y):
    if y == 0:
        return x
    
    r = x % y
    return gcd(y, r)

A, B, C, D = [int(x) for x in input().split()]
if C > D:
    E = C * D // gcd(C, D)
else:
    E = C * D // gcd(D, C)

divC = B // C - (A - 1) // C
divD = B // D - (A - 1) // D
divE = B // E - (A - 1) // E
div = divC + divD - divE
ans = B - A + 1 - div

print(ans)

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

using namespace std;

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

#define FOR(i, n, m) for(ll (i)=(m);(i)<(n);++(i))
#define REP(i, n) FOR(i,n,0)
#define OF64 std::setprecision(10)

const ll MOD = 1000000007;
const ll INF = (ll) 1e15;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S;
    cin >> S;
    sort(S.begin(), S.end());
    if (S[0] == S[1] && S[2] == S[3] && S[0] != S[2])
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>

using namespace std;

int main(void){
	int i;
	char ch[10000];

	for(i=0;;i++){
		scanf("%c",&ch[i]);
		if(ch[i]=='\n')
			break;
		if('a'<=ch[i] && ch[i]<='z')
			ch[i]-='a'-'A';
		else if('A'<=ch[i] && ch[i]<='Z')
			ch[i]+='a'-'A';
	}

	printf("%s",ch);

	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int INF = 1e9;
const int MOD = INF+7;
const ll LINF = 1e18;
#define rep(i,N) for(int (i)=0;(i)<(N);++(i))
#define rrep(i,N) for(int (i)=(N-1);(i)>0;--i)
#define FOR(i,j,N) for(int (i)=(j);(i)<(N);++(i))
#define put(n) cout<<(n)<<endl;
#define all(v) v.begin(),v.end()
#define MP make_pair
#define pb push_back


int main(){
   int A,B,C;
   cin >> A >> B >> C;
   int ans = 0;
   ans += min(A,C);
   C -= min(A,C);
   ans += B + min(B,C);
   C -= min(B,C);
   if(C) ++ans;

   cout << ans << endl;
}

Measured memory_bytes: 256
import core.bitop, std.algorithm, std.ascii, std.bigint, std.conv,
    std.functional, std.math, std.numeric, std.range, std.stdio, std.string,
    std.random, std.typecons, std.container;

ulong MAX = 100_100, MOD = 1_000_000_007, INF = 1_000_000_000_000;
alias sread = () => readln.chomp();
alias lread(T = long) = () => readln.chomp.to!(T);
alias aryread(T = long) = () => readln.split.to!(T[]);
alias Pair = Tuple!(string, "s", long, "p");
alias PQueue(T, alias less = "a>b") = BinaryHeap!(Array!T, less);

void main()
{
    long n, a, b;
    scan(n, a, b);
    writeln(max(0, b * (n - 2) - a * (n - 2) + 1));
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}


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

int main() {
    int64_t a, b, k;
    cin >> a >> b >> k;

    if (k <= a){
        cout << a - k << " " << b << endl;
    }
    else if (k - a <= b){
        cout << 0 << " " << b - (k - a) << endl;
    }
    else{
        cout << "0 0" << endl;
    }
}

Measured memory_bytes: 256
import networkx as nx

N = int(input())
S = [list(input()) for i in range(N)]

G = nx.Graph()
for i in range(N):
    G.add_node(i)

for i in range(N):
    for j in range(i, N):
        if S[i][j] == '1':
            G.add_edge(i, j)

if nx.is_bipartite(G):
    ans = nx.diameter(G)+1
    print(ans)
else:
    print(-1)

Measured memory_bytes: 60020
let () =
  let s = read_line () in
  print_endline @@
  match
    List.find (fun i -> s.[i] = 'C') @@
      Array.to_list @@
      Array.init (String.length s) @@
      fun i -> i
  with
  | exception Not_found -> "No"
  | i ->
      if 
        List.exists (( = ) 'F') @@
          Array.to_list @@
          Array.init (String.length s - i - 1) @@
          fun j -> s.[i + j + 1]
      then "Yes"
      else "No"


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

#define EPS (1e-10)
#define rep(i, a, b) for (int i = a; i < (int)(b); ++i)
#define rrep(i, a, b) for (int i = b - 1; i >= (int)(a); --i)
#define all(a) a.begin(), a.end()

using namespace std;
using ll = long long;
using vi = vector<int>;
using vb = vector<bool>;
using vll = vector<ll>;
using vd = vector<double>;
using vvi = vector<vi>;
using vvb = vector<vb>;

constexpr int MOD = 1000000007;

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

    int n;
    cin >> n;

    vi ans(n);
    rep(i, 0, n) {
        int a;
        cin >> a;
        ans[a - 1] = i + 1;
    }
    rep(i, 0, n) {
        cout << ans[i] << " ";
    }
    cout << endl;

    return 0;
}

Measured memory_bytes: 1280
h, w = map(int, input().split())
C = [list(map(int, input().split())) for i in range(10)]
for k in range(10):
    for i in range(10):
        for j in range(10):
            C[i][j] = min(C[i][j], C[i][k] + C[k][j])
A = [list(map(int, input().split())) for i in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if A[i][j] != -1:
            ans += C[A[i][j]][1]
print(ans)

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

int main(){
    int n;
    cin>>n;
    map<string,int> dict;
    rep(i,n){
        string s;
        cin>>s;
        dict[s]++;
    }   
    int m;
    cin>>m;
    rep(i,m){
        string t;
        cin>>t;
        dict[t]--;
    }
    int maxv=0;
    for(auto itr=dict.begin();itr!=dict.end();itr++){
        maxv=max(maxv,itr->second);
    }
    cout<<maxv<<"\n";
    return 0;
}

Measured memory_bytes: 3600
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <queue>
#include <map>
#include <numeric>
#include <unordered_map>
#include <iomanip>
#include <functional>
#include <bitset>
#include <complex>
#include <stack>



#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = (int)(n-1); i >= 0; i--)
#define repi(i,a,b) for(int i=ll(a);i<ll(b);i++)
#define rrepi(i,a,b) for(int i=ll(b);i>=int(a);i--)

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

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

typedef long long ll;

using namespace std;

long long modpow(long long x,long long n,long long mod)
{
  if(n==0)return 1;
  long long res=modpow(x*x%mod,n/2,mod);
  if(n&1)res=res*x%mod;
  return res;
}
long long modinv(long long a,long long mod)
{
  return modpow(a,mod-2,mod);
}
vector<long long> fact,inv;
void init(int n,int mod){
  fact.resize(n);
  inv.resize(n);
  fact[0]=1LL;
  rep(i,n-1){
    fact[i+1]=(long long)fact[i]*(i+1)%mod;
  }
  inv[n-1]=modinv(fact[n-1],mod);
  rrep(i,n-1){
    inv[i]=(long long)inv[i+1]*(i+1)%mod;
  }
}
long long comb(ll a,ll b,ll mod){
  if(b<0||a-b<0)return 0;
  return fact[a]*inv[b]%mod*inv[a-b]%mod;
}
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  ll p;cin>>p;
  ll mod=p;
  init(p,p);
  vector<ll>res(p);
  rep(i,p){
    ll w;cin>>w;
    res[0]+=w;
    ll tj=1;
    rrep(j,p){
      ll td=comb(p-1,j,mod);
      td*=tj;
      tj*=-i;
      tj%=mod;
      res[j]-=td*w;
      res[j]%=mod;
      if(res[j]<0)res[j]+=mod;
    }
  }

  rep(i,p)cout<<res[i]<<" ";
  cout<<endl;
  return 0;

}


Measured memory_bytes: 384
#!/usr/bin/env python3
import heapq
# input = stdin.readline

def solve(n,m,a):
  a = [-x for x in a]
  heapq.heapify(a)
  for _ in range(m):
    x = heapq.heappop(a)
    heapq.heappush(a,-(abs(x)//2))
  return abs(sum(a))


def main():
  N,M = map(int,input().split())
  a = list(sorted(map(int,input().split())))
  print(solve(N,M,a))
  pass

if __name__ == '__main__':
  main()


Measured memory_bytes: 20368
N,H = map(int,input().split())
Data = []
maxPower = 0
for i in range(N):
    a,b = map(int,input().split())
    Data.append([a,b])
    maxPower = max(maxPower,a)

Data2 = list(filter(lambda x:x[1]>=maxPower,Data))
Data2.sort(key=lambda x:x[1],reverse=True)

ans = 0
left = H
for d in Data2:
    left -= d[1]
    ans += 1
    if left <= 0:
        break

if left > 0:
    ans += (left//maxPower)
    if left % maxPower > 0:
        ans += 1

print(ans)


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

class UnionFind {
public:
    std::vector<int> data;
    UnionFind( int n ) {
        data.resize( n, -1 );
    }
    int find( int x ) {
        if ( data[x] < 0 ) {
            return x;
        } else {
            int r = find( data[x] );
            data[x] = r;
            return r;
        }
    }
    void unite( int x, int y ) {
        int r = find( x );
        int s = find( y );
        if ( r != s ) {
            data[r] += data[s];
            data[s] = r;
        }
    }
};

ll solve() {
    ll N, M;
    cin >> N >> M;
    int k, l;
    int c = 1e5;
    UnionFind u(2e5);
    for ( int i = 0; i < N; i++ ) {
        cin >> k;
        for ( int j = 0; j < k; j++ ) {
            cin >> l;
            u.unite(i, c+l-1);
        }
    }
    for ( int i = 1; i < N; i++ ) {
        if ( u.find(0) != u.find(i) ) return false;
    }
    return true;
}

int main() {
    string ans = solve() ? "YES" : "NO";
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 2304
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#include<string>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<sstream>
#include<numeric>
#include<iostream>
#include<algorithm>
#include<functional>

#define For(i,x,y) for (int i=x;i<y;i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second

#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;

typedef long long ll;
typedef double db;
typedef vector<int> Vi;
typedef pair<int,int> pii;

int IN(){
	int c,f,x;
	while (!isdigit(c=getchar())&&c!='-');c=='-'?(f=1,x=0):(f=0,x=c-'0');
	while (isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0';return !f?x:-x;
}

const int N=200000+19;
const int oo=(1<<30)-1;

struct Edge{
	int y,nxt;
} E[N];
map<int,int> M;
int A[N],id[N],chk[N],vis[N],T[N];
int n,Time,z,tot;
Vi V[N],S[N];

void Init(int n,int m){
	for (int i=2;i*i<=n;i++)
		if (n%i==0){
			if (!M.count(i)) M[i]=++tot;
			V[m].pb(M[i]);
			S[M[i]].pb(m);
			while (n%i==0) n/=i;
		}
	if (n>1){
		if (!M.count(n)) M[n]=++tot;
		V[m].pb(M[n]);
		S[M[n]].pb(m);
	}
}
void dfs(int x){
	if (T[x]==Time) return;
	T[x]=Time;
	if (chk[x]){
		if (!z||A[x]<A[z]) z=x;
		chk[x]=0;
	}
	if (x<=n){
		for (int i:V[x]) if (!vis[i]) dfs(i);
	} else{
		for (int i:S[x]) if (!vis[i]) dfs(i);
	}
}
void Reset(){
	Time++;
	For(i,1,n+1)
		if (!vis[i]&&T[i]!=Time){
			z=0;
			dfs(i);
			chk[z]=1;
		}
}

int main(){
//	freopen("E.in","r",stdin);
//	freopen("E.out","w",stdout);
	tot=n=IN();
	For(i,1,n+1) A[i]=IN();
	sort(A+1,A+n+1);
	For(i,1,n+1){
		Init(A[i],i);
		chk[i]=1;
		vis[i]=0;
	}
	Reset();
	For(t,1,n+1){
		int x=0;
		For(i,1,n+1) if (!x||!vis[i]&&chk[i]&&A[i]>A[x]) x=i;
		printf("%d ",A[x]);
		vis[x]=1;
		for (int i:V[x]){
			for (int y:S[i]) if (y!=x&&!vis[y]) chk[y]=1;
		}
		Reset();
	}
	puts("");
}

Measured memory_bytes: 14848
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int x = sc.nextInt();
        int[] c = new int[n];
        int[][] a = new int[n][m];
        for (int i=0;i<n;i++){
            c[i]=sc.nextInt();
            for (int j=0;j<m;j++)a[i][j]=sc.nextInt();
        }
        int ans = Integer.MAX_VALUE;
        for (int i=0;i<Math.pow(2,n);i++){
            String s = Integer.toBinaryString(i);
            while (s.length()<n)s="0"+s;
            int instance = 0;
            int[] intel = new int[m];
            for (int j=0;j<n;j++){
                if (s.charAt(j)=='1'){
                    instance+=c[j];
                    for (int k=0;k<m;k++){
                        intel[k]+=a[j][k];
                    }
                }
            }
            boolean b=true;
            for (int j=0;j<m;j++){
                if (intel[j]<x)b=false;
            }
            if (b)ans=Math.min(ans,instance);
        }
        if (ans==Integer.MAX_VALUE)System.out.println(-1);
        else System.out.println(ans);
    }
}


Measured memory_bytes: 40896
#include <bits/stdc++.h>
#define ll long long int
const ll mod = 1e9 + 7;

using namespace std;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	char c;
	cin >> c;
	if (c >= 'A' && c <= 'Z') cout << 'A';
	else cout << 'a';
	return 0;
}


Measured memory_bytes: 3568
fun main(args: Array<String>) {
    val s = readLine()!!
    val t = readLine()!!

    (0..s.length - t.length)
            .filter { i -> (t.indices).all { j -> s[i + j] == t[j] || s[i + j] == '?' } }
            .map { s.slice(0 until it) + t + s.slice(it + t.length until s.length) }
            .map { it.replace('?', 'a') }
            .min()
            .let { println(it ?: "UNRESTORABLE") }
}


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

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

int N,K;

int main(){
	cin >> N >> K;
	vector<int> V(N);
	rep(i,N){ cin >> V[i]; }

	ll ans = 0;
	for(int l=0; l<=K; l++){
		for(int r=0; r<=K-l; r++){
			if(l+r > N)continue;
			int d = K-l-r;
			vector<int> S;
			for(int i=0; i<l; i++){ S.push_back(V[i]); }
			for(int i=N-r; i<N; i++){ S.push_back(V[i]); }

			sort(S.begin(),S.end());
			for(int i=0; i<d && i<(int)S.size(); i++){ S[i]=max(S[i],0); }
			ans = max(ans,accumulate(S.begin(),S.end(),0LL));
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 256