akhauriyash/Code-Regression huggingface dataset:
# -*- coding: utf-8 -*-
import heapq
x,y,z,k = map(int, input().split())
al = list(map(int, input().split()))
bl = list(map(int, input().split()))
cl = list(map(int, input().split()))

al.sort(reverse=True)
bl.sort(reverse=True)
cl.sort(reverse=True)
regist = set()
regist.add((0,0,0))
q = [(-1*(al[0]+bl[0]+cl[0]),0,0,0)]
heapq.heapify(q)
for _ in range(k):
    s,ai,bi,ci = heapq.heappop(q)
    print(-s,flush=True)

    if ai+1<x and (ai+1,bi,ci) not in regist:
        heapq.heappush(q, (-1*(al[ai+1]+bl[bi]+cl[ci]), ai+1,bi,ci))
        regist.add((ai+1,bi,ci))

    if bi+1<y and (ai,bi+1,ci) not in regist:
        heapq.heappush(q, (-1*(al[ai]+bl[bi+1]+cl[ci]), ai,bi+1,ci))
        regist.add((ai,bi+1,ci))

    if ci+1<z and (ai,bi,ci+1) not in regist:
        heapq.heappush(q, (-1*(al[ai]+bl[bi]+cl[ci+1]), ai,bi,ci+1))
        regist.add((ai,bi,ci+1))


Measured memory_bytes: 4848
#include<iostream>
using namespace std;
int main()
{
	int n;
	cin>>n;
	int a[n],i,f,sum=0;
	for(i=0;i<=n-1;i++) cin>>a[i];
	
	for(i=0;i<=n-1;i++) sum+=a[i];
	f=sum-n;
	cout<<f<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void){
  char s[15] = {};
  int num[15] = {};
  int N;//文字列sの長さ
  int X;
  int min;//abs(X - 753)の最小値
  int i;//カウンタ

  scanf("%s", s);
  N = strlen(s);
  for(i = 0; i < N; i++){
    num[i] = s[i] - '0';
  }

  X = num[0]*100 + num[1]*10 + num[2];
  min = abs(X - 753);
  for(i = 1; i < N-2; i++){
    X = num[i]*100 + num[i+1]*10 + num[i+2];
    if(abs(X - 753) < min){
      min = abs(X - 753);
    }
  }

  printf("%d\n", min);
  return 0;
}


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

const int mod = 1e9+7;
const int INF = 2000000;
const double PI = acos(-1.0);

int main() {
    
    string s;
    cin >> s;
    int ans;
    if(s == "RRR") ans = 3;
    else if(s == "RRS" || s == "SRR") ans = 2;
    else if(s == "SSS") ans = 0;
    else ans = 1;
    cout << ans << endl;
}

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

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    
    return divisors

if len(A) <= 2:
    print(max(A))
    exit()
else:
    all_divisors = list(set(make_divisors(A[0]) + make_divisors(A[1])))

ans = 1
for divisor in all_divisors:
    cnt = 0
    for a in A:
        if a % divisor != 0:
            cnt += 1
        if cnt == 2:
            break
    if cnt < 2:
        ans = max(ans, divisor)

print(ans)

Measured memory_bytes: 14400
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <time.h>
#include <list>

using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define reps(x,c) for(auto x:c)
#define all(x) begin(x), end(x)
#define pb(a) emplace_back(a) 
#define mp(a,b) make_pair((a),(b))
#define pl pair<ll,ll>
#define INF 2147483600
#define MOD 1000000007
#define fi first
#define se second
#define dbg(x) cout << #x"="<< (x) << endl
#define dbgv(x) cout<<#x<<endl;reps(y,x){cout<<y<<" ";}cout<<endl

ll c[5][5];
int main(){
  rep(i,3){
    rep(j,3){
      cin>>c[i+1][j+1];
    }
  }
  ll a,b,d,e,f,g;
  a=c[1][1]+c[2][2]+c[3][3];
  b=c[1][2]+c[2][3]+c[3][1];
  d=c[1][3]+c[2][1]+c[3][2];
  e=c[1][3]+c[2][2]+c[3][1];
  f=c[1][2]+c[2][1]+c[3][3];
  g=c[1][1]+c[2][3]+c[3][2];
  if(a==b&&b==d&&d==e&&e==f&&f==g){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
  return 0;
}

Measured memory_bytes: 256
import sys

def main(lines):
  a = list(map(int, lines[0].split()))
  a.sort()
  print(a[2]*10 + a[1] + a[0])
  


if __name__ == '__main__':
    lines = []
    for l in sys.stdin:
        lines.append(l.rstrip('\r\n'))
    main(lines)

Measured memory_bytes: 3060
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val x = sc.nextInt()
  var y = x % 100
  for (i <- 1 to (x / 100)) {
    y match {
      case a if a >= 5 => y -= 5
      case 4 => y -= 4
      case 3 => y -= 3
      case 2 => y -= 2
      case 1 => y -= 1
      case 0 => y
    }
  }
  println(if (y == 0) '1' else '0')
}

Measured memory_bytes: 55396
#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int main()
{
    long int k,t,arr[105],sum,ans;

    while(scanf("%ld %ld",&k,&t)==2)
    {
        for(int i=0; i<t; i++)
        {
            scanf("%ld",&arr[i]);
        }

        sort(arr, arr+t);

        sum=0;

        for(int i=0; i<t-1; i++)
        {
            sum+=arr[i];
        }

        if(arr[t-1]<=sum)
            printf("0\n");

        else
        {
            ans=arr[t-1]-sum;

            printf("%ld\n",ans-1);
        }
    }

    return (0);
}


Measured memory_bytes: 256
MAX_V = 100100
MAX_N = 101
INF = pow(2, 63)

N, W = map(int, input().split())
w = [0 for _ in range(N)]
v = [0 for _ in range(N)]
for i in range(N):
    w[i], v[i] = map(int, input().split())

dp = [[INF for _ in range(MAX_V)] for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
    for sum_v in range(MAX_V):
        # print(i, sum_v, sum_v - v[i] >= 0)
        if sum_v - v[i] >= 0:
            dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v - v[i]] + w[i])
        dp[i+1][sum_v] = min(dp[i+1][sum_v], dp[i][sum_v])
        # print(dp[i + 1][sum_v])

ans = max([i for i in range(len(dp[N])) if dp[N][i] <= W])
# for l in dp:
#     print([n for n in l if not n == INF])

print(ans)


Measured memory_bytes: 173640
#include <cstdio>
#include <vector>

int n, m;
std::vector<int> v[51];

int main(){
	scanf("%d %d", &n, &m);
	for(int i=0; i<m; ++i){
		int a, b;
		scanf("%d %d", &a, &b);
		v[a-1].push_back(b-1);
		v[b-1].push_back(a-1);
	}
	for(int i=0; i<n; ++i)
		printf("%d\n", (int)v[i].size());
}

Measured memory_bytes: 380
#include <stdio.h>

int main(void)
{
    int i, j;
    int in_num;
    int row, column;
    int all_sum = 0;

    scanf("%d %d", &row, &column);
    int in_spread[row][column];
    int row_sum[row];
    int column_sum[column];
    int out_spread[row + 1][column + 1];

    for (i = 0; i < row; i++){
        for (j = 0; j < column; j++){
            scanf("%d", &in_num);
            in_spread[i][j] = in_num;
            all_sum += in_num;
        }
    }

    for (i = 0; i < row; i++){
        row_sum[i] = 0;
        for (j = 0; j < column; j++){
            row_sum[i] += in_spread[i][j];
        }
    }

    for (j = 0; j < column; j++){
        column_sum[j] = 0;
        for (i = 0; i < row; i++){
            column_sum[j] += in_spread[i][j];
        }
    }

    for (i = 0; i < row; i++){
        for (j = 0; j < column; j++){
            out_spread[i][j] = in_spread[i][j];
        }
    }
    for (i = 0; i < row; i++){
        out_spread[i][column] = row_sum[i];
    }
    for (j = 0; j < column; j++){
        out_spread[row][j] = column_sum[j];
    }
    out_spread[row][column] = all_sum;

    for (i = 0; i < row + 1; i++){
        for (j = 0; j < column + 1; j++){
            if (j){
                printf(" ");
            }
            printf("%d", out_spread[i][j]);
        }
        printf("\n");
    }

    return 0;
}

Measured memory_bytes: 684
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i,N) for(int i = 0; i < (N); i++)
#define erep(i,N) for(int i = N - 1; i >= 0; i--)
const ll INF = 1000000000;
//const ll MOD = 1000000007;
const ld PI = (acos(-1));
using Graph = vector<vector<int>>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true;} return false;}
typedef pair<int, int> pair;
double rad(double a) {return a * 180 / PI;}

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号 (例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

//dpTable
int dp[100050];

int main(){
    int N;
    cin >> N;
    vector<ll> A(N);
    rep (i,N) {
        cin >> A.at(i);
    }
    ll ans = 0;
    for (int i = 1; i < N; i++) {
        if (A.at(i) < A.at(i - 1)) {
            ans += (A.at(i - 1) - A.at(i));
            A.at(i) = A.at(i - 1);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4748
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#define ll long long
#define endl '\n'
using namespace std;

int N, M;
vector<int> adj[200001];
bool visited[200001];

bool dfs(int cur, bool flag)
{
  visited[cur] = true;
  
  for(int i = 0; i < adj[cur].size(); i++)
    {
      int next = adj[cur][i];
      if(next == N) return true;
      if(visited[next]) continue;
      if(flag)
	if(dfs(next, false))
	  return true;
    }

  return false;
}

int main(void)
{
  cin.tie(NULL); ios_base::sync_with_stdio(false);
  cin >> N >> M;
  while(M--)
    {
      int a, b; cin >> a >> b;
      adj[a].push_back(b);
      adj[b].push_back(a);
    }
  if(dfs(1, true))
    cout << "POSSIBLE" << endl;
  else
    cout << "IMPOSSIBLE" << endl;

  
  return 0;
}

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

int minReach(int arr[], int n, int k)
{
    int dp[n+1];

    dp[1] = 0;

    for(int i=2; i<=n; i++)
    {
        int jump = INT_MAX;

        for(int j=i-k; j<i; j++)
        {
            if(j<1)
                continue;

            int tmp = dp[j] + abs(arr[j]-arr[i]);

            if(tmp<jump)
                jump=tmp;
        }

        dp[i]=jump;
    }

    return dp[n];
}

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

    int arr[n+1];

    for(int i=1; i<=n; i++)
        cin>>arr[i];

    cout<<minReach(arr,n,k)<<endl;

    return 0;
}


Measured memory_bytes: 4388
N, u, v = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)


def dfs(v):
    dist = [-1 for _ in range(N+1)]
    stack = [v]
    dist[v] = 0
    while stack:
        v = stack.pop()
        dist_x = dist[v] + 1
        for child in graph[v]:
            if 0 <= dist[child]:
                continue
            dist[child] = dist_x
            stack.append(child)
    return dist


def solve():
    dist_u, dist_v = dfs(u), dfs(v)
    
    ans = 0
    for a, b in zip(dist_u[1:], dist_v[1:]):
        if a < b:
            ans = max(ans, b-1)
    print(ans)


if __name__ == '__main__':
    solve()


Measured memory_bytes: 30096
#pragma GCC optimize(3 , "Ofast" , "inline")

#include <bits/stdc++.h>

#define rep(i , a , b) for(register int i=(a);i<=(b);i++)
#define per(i , a , b) for(register int i=(a);i>=(b);i--)


using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int , int> pi;

template<class T>
inline void read (T &x) {
    x = 0;
    int sign = 1;
    char c = getchar ();
    while (c < '0' || c > '9') {
        if ( c == '-' ) sign = - 1;
        c = getchar ();
    }
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar ();
    }
    x = x * sign;
}

const int maxn = 2e5 + 10;
const int inf = int (1e9);
const ll INF = ll (1e18);
const double PI = acos (- 1);
const int mod = 998244353;
const double eps = 1e-8;

int n;
ll k;
ll cnt[65];


ll qpow(ll a,ll b) {
    ll ans = 1;
    while (b) {
        if(b&1) ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}
int main () {
    read (n);
    read (k);
    ll ma = 1;
    rep (i , 1 , n) {
        ll x;
        read (x);
        ll j = 0;
        while (x) {
            cnt[j]+=(x&1);
            x/=2;
            j++;
        }
        ma = max (ma , j);
    }
    ll kk = k;
    ll j = 0;
    while (kk) {
        kk /= 2;
        j ++;
    }
    ma = max (ma , j);
    bool f = 0;
    per (i , ma - 1 , 0) {
        if ( f ) {
            if ( cnt[ i ] < n - cnt[ i ] ) {
                cnt[ i ] = n - cnt[ i ];
            }
            continue;
        }
        if ( cnt[ i ] < n - cnt[ i ] ) {
            if (( k >> i ) & 1 ) {
                cnt[ i ] = n - cnt[ i ];
            }
        } else {
            if (( k >> i ) & 1 ) {
                f = 1;
            }
        }
    }
    ll ans = 0;
    rep (i,0,ma-1) {
        ans=ans+1ll*cnt[i]*qpow(2,i);
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int i,a;
  int check[30];
   for(i=0;i<30;i++){
       check[i]=0;
   }
  for(i=0;i<28;i++){
      cin>>a;
      check[a-1]=1;
  }
  for(i=0;i<30;i++){
      if(check[i]==0){
          cout<<i+1<<endl;
      }
  }
  
    
}



Measured memory_bytes: 3088
#include<iostream>
using namespace std;
 int gcd(int p,int q){
   if (p%q==0)return q;
   return gcd(q,p%q);
 }

int main(){
  int K;
  cin>>K;
  int ans=0;
  for(int a=1;a<=K;a++){
    for(int b=1;b<=K;b++){
      for(int c=1;c<=K;c++){
        ans+=gcd(a,gcd(b,c));
      }
    }
  }
 cout<<ans<<endl;
 
}
     


Measured memory_bytes: 3636
a = list(map(int,input().split(" ")))
if a[0] == 1 and a[1] == 1:
  print("Draw")
elif a[0] == 1:
  print("Alice")
elif a[1] == 1:
  print("Bob")
else:
  if a[0] > a[1]:
    print("Alice")
  elif a[0] == a[1]:
    print("Draw")
  else:
    print("Bob")


Measured memory_bytes: 3060
n = int(input())
h = list(map(int,input().split()))
A = []
ans = 0
res = 0
for i in range(n-1):
    if h[i]>=h[i+1]:
        ans += 1

    else:
        res = max(res,ans)
        ans = 0


res = max(res,ans)        
print(res)


Measured memory_bytes: 85104
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;
using pil = pair<int, ll>;
using uint = unsigned int;
template <typename T>
using Graph = vector<vector<T>>;
const int MOD = 10007;
const ld PI = acosl(-1);

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

    int X;
    cin >> X;
    cout << (30 <= X ? "Yes" : "No") << endl;

    return 0;
}


Measured memory_bytes: 3648
/*
 * C言語のサンプルプログラム - Webkaru
 * - 入力した文字がアルファベットの小文字か大文字かを判定 -
 */
#include<stdio.h>
 
int main(void){
 
  int i;
 
  /* 文字 */
  char moji;
 
  /* 文字を入力 */
  printf(" ");
  scanf("%c", &moji);
 
  /* アルファベットの小文字か大文字かを判定 */
  if((moji>= 'a') && (moji<='z')){
    printf("a\n");
  }
  else if((moji>= 'A') && (moji<='Z')){
    printf("A\n");
  }
 
 
  return 0;
}

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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#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 all(x) (x).begin(),(x).end()

using namespace std;
using ll = long long;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> P;
 
const int INF = 1e9;
//const ll INF = 1e18;
const double EPS = 1e-10;
const int MOD = 1e9+7;
const double PI = acos(-1.0);

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

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

int main()
{
  int temp;
  int input_seq[200];
  int input_num;
  int min = 1200;
  int max = 0;
  cin >> input_num;
  for(int i = 0; i<input_num;i++)
  {
    cin >> input_seq[i];
  }
  for(int i = 0; i<input_num;i++)
  {
    cout << input_seq[input_num - i - 1];
    if(i < input_num - 1)cout << " ";
  }
  cout << endl;
  return 0;
}



Measured memory_bytes: 3096
L = [int(input()) for i in range(5)]
l = [i*(-1)//10*10*(-1) for i in L]
l1 = [i%10 for i in L]
l2 = sorted(list(set(l1)))
if l2[0] == 0:
  if len(l2) == 1:
    print(sum(L))
  else:
    print(sum(l)-l[l1.index(l2[1])]+L[l1.index(l2[1])])
else:
  print(sum(l)-l[l1.index(l2[0])]+L[l1.index(l2[0])])

Measured memory_bytes: 3064
#define _USE_MATH_DEFINES
    #include <bits/stdc++.h>
    #define ll  long long
    #define pb push_back
    #define mp make_pair
    #define ff first
    #define ss second
    #define vi vector<int>
    #define br cout <<"\n";
    #define all(x)  (x).begin(),(x).end()
    #define tr(c,i) for(auto i : c)
    #define pii pair< int,int >
    #define fast_io() ios_base::sync_with_stdio(false);cin.tie(nullptr)
    #define pq priority_queue< pair<ll,pii> ,vector<pair<ll,pii>>,greater <pair<ll,pii>> >p;//container adapter makes ascending q
    #define er(x) cout << x << " "
    #define err(x,y) cout << x << " "<<y
    const int M = 200005;
    using namespace std;
    clock_t time_p=clock();
    void dem()
    {
        time_p=clock()-time_p;
        cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
    }
    using namespace std ;
    const int MAX =  1000 * 1000 + 10;
    const int dx[] = { 1, -1 , 0 , 0  };
    const int dy [] = { 0 ,0 , 1 , -1  };
    const int MOD = 1000 * 1000 * 1000 + 9 ;
    int main (){
    int a , b ;
    cin >> a >> b ;

    cout << max ( 0 ,  a  - (2* b)  ) ;

        return 0 ;
    }



Measured memory_bytes: 384
H,W,K =map(int,input().split()) 
L = [list(input()) for i in range(H)]
from itertools import product
li = [0,1]
ans = 0
for h in product(li,repeat = H):
    for w in product(li,repeat = W):
        cnt = 0
        for j in range(H):
            for i in range(W):
                if h[j] == 0 and w[i] == 0:
                    if L[j][i] == "#":
                        cnt +=1
        if cnt == K:
            ans +=1
print(ans)

Measured memory_bytes: 9108
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "iomanip"
#include "random"

using namespace std;

const long long int MOD = 1000000007;
const long double EPS = 0.00000001;
const long double PI = 3.1415926535897932384626433;

long long int N, M, K, H, W, L, R;



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

	cin >> N >> M >> K;
	vector<bool>flag(5000);
	int box = 0;
	while (box < 4000) {
		for (int i = box; i <= box + N; i++) {
			flag[i] = true;
		}
		box += N + M;
	}
	for (int i = 0; i < 5000; i++) {
		if (flag[i] && i % 60 == K) {
			cout << i << endl;
			return 0;
		}
	}
	cout << "-1\n";
	return 0;
}

Measured memory_bytes: 3212
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define loop(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  loop(i,0,n)
#define all(c) c.begin(),c.end()
#define vi vector<int>
#define vl vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>

ll int cnt=0;
vi g;

void Acout(int A[],int N){
    rep(i,N){
        if(i)cout<<" ";
        cout<<A[i];
    }
    cout<<endl;
}

void insertsort(int A[],int N,int g){
    int v;
    int j;
    for(int i=g;i<N;i++){
        j=i-g;
        v=A[i];
        while(j>=0 && A[j]>v){
            A[j+g] = A[j];
            j = j-g;
            cnt++;
        }
        A[j+g]=v;
    }
}

void shellsort(int A[],int N){
    int h=1;
    while(1){
        if(h>N)break;
        g.push_back(h);
        h=3*h+1;
    }
    for(int i=g.size()-1;i>=0;i--){
        insertsort(A,N,g[i]);
    }
}

int main(){
    int N;
    cin>>N;
    int A[N];
    rep(i,N)cin>>A[i];

    shellsort(A,N);

    cout<<g.size()<<endl;
    for(int i=g.size()-1;i>=0;i--){
        printf("%d",g[i]);
        if(i)printf(" ");
    }
    printf("\n");
    printf("%d\n",cnt);
    rep(i,N)cout<<A[i]<<endl;
}


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

int main() {
  ll N;cin>>N;
  vector<ll> A(N+1);
  for(int i=1;i<=N;i++) cin>>A[i];
  
  sort(A.begin(),A.end());
  for(int i=1;i<=N-1;i++){
    if(A[i]==A[i+1]){
      cout << "NO" << endl;
      return 0;
    }
  }
  
  cout << "YES" << endl;
}


Measured memory_bytes: 4780
n=int(input())
l=sorted([(v,i+1) for i,v in enumerate(list(map(int,input().split())))],reverse=1)
dp=[[0]*(n+1) for i in range(n+1)]
for ko in range(1,n+1):
    for x in range(ko+1):
        ret=0
        v,i=l[ko-1]
        y=ko-x
        if y>=1:ret=max(ret,dp[x][y-1]+abs(n-y+1-i)*v)
        if x>=1:ret=max(ret,dp[x-1][y]+abs(x-i)*v)
        dp[x][y]=ret
print(max(dp[a][n-a] for a in range(n+1)))

Measured memory_bytes: 100596
#include <bits/stdc++.h>
#define SZ(c)       int(c.size())
#define FOR(i,a,b)  for (int i=a; i<(b); ++i)
#define DOWN(i,a,b) for (int i=(a)-1; i>=(b); --i)
using namespace std;
using i64 = long long;

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout<<fixed<<setprecision(10);

  string s;
  cin>>s;

  int n=SZ(s);
  int res=n;
  FOR(i,0,n-1) {
    if (s[i]!=s[i+1]) res=min(res,max(i+1,n-i-1));
  }
  cout<<res<<endl;

  return 0;
}


Measured memory_bytes: 512
#include <iostream>
using namespace std;
int main() {
    int ABCD,a,b,c,d;
    cin >> ABCD;
    a=ABCD/1000;
    b=(ABCD-(a*1000))/100;
    c=(ABCD-(a*1000)-(b*100))/10;
    d=(ABCD-(a*1000)-(b*100)-(c*10));

    if(a+b+c+d==7){
        cout<<a<<"+"<<b<<"+"<<c<<"+"<<d<<"=7"<<endl;
    }else if(a+b+c-d==7) {
        cout << a << "+" << b << "+" << c << "-"<<d<<"=7" << endl;
    }else if(a+b-c+d==7) {
        cout << a << "+" << b << "-" << c << "+" << d << "=7" << endl;
    }else if(a+b-c-d==7){
        cout << a << "+" << b << "-" << c << "-" << d << "=7" << endl;
    }else if(a-b+c+d==7){
        cout << a << "-" << b << "+" << c << "+" << d << "=7" << endl;
    }else if(a-b+c-d==7){
        cout << a << "-" << b << "+" << c << "-" << d << "=7" << endl;
    }else if(a-b-c+d==7){
        cout << a << "-" << b << "-" << c << "+" << d << "=7" << endl;
    }else if(a-b-c-d==7){
        cout << a << "-" << b << "-" << c << "-" << d << "=7" << endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
//#include <iomanip>
//#include <string>
#include <algorithm>
#include <utility>
//#include <stack>
//#include <queue>
//#include <tuple>
#include <set>
//#include <map>
//#include <unordered_map>
#include <vector>
//#include <functional>
//#include <bitset>
//#include <cmath>
using namespace std;

typedef long long lint;
typedef unsigned long long ulint;
#define MOD 1000000007

void add(lint *bit, lint N, lint i,lint x){
    for(lint j=i+1;j<=N;j+=(j&-j)) bit[j]+=x;
}
lint sum(lint *bit, lint N, lint i){
    lint r=0LL;
    for(lint j=i+1;j>0;j-=(j&-j)) r+=bit[j];
    return r;
}

int main(){
    lint N,K;
    cin >> N >> K;
    lint A[200001];
    pair<lint,lint> B[200001];
    lint s=0;
    A[0]=0;
    B[0]=make_pair(0LL,0LL);
    for(lint i=0;i<N;i++){
        lint a;
        cin >> a;
        s+=a;
        A[i+1]=s-(i+1)*K;
        B[i+1]=make_pair(A[i+1],i+1);
    }
    sort(B,B+N+1);
    lint bit[200001];
    for(lint i=0;i<=N;i++) bit[i]=0;

    lint ans=0LL;

    lint cur=B[0].first, ii=0;
    A[B[0].second]=ii;
    for(lint i=1;i<=N;i++){
        if(B[i].first==cur){
            A[B[i].second]=ii;
        }else{
            ii++;
            A[B[i].second]=ii;
            cur=B[i].first;
        }
    }
    for(int i=0;i<=N;i++){
        ans+=sum(bit,N+1,A[i]);
        add(bit,N+1,A[i],1LL);
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 6528
use proconio::marker::*;
use proconio::*;
use std::cmp::max;

fn main() {
    input! {
        n: usize,
        a: [i64; n],
    };
    let mut ans = 0;
    let mut pre = a[0];
    for &x in a.iter().skip(1) {
        ans += max(pre - x, 0);
        pre = max(x, pre);
    }

    println!("{}", ans);
}


Measured memory_bytes: 5480
n = int(input())
import math
ans1 = 0
ans2 = 0
fn = math.factorial(n)
prime = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47]

for p in prime:
    if fn%(p**74) == 0:
        ans1 += 1
    for q in prime:
            if p != q:
                if fn%((p**14)*(q**4)) == 0:
                    ans1 += 1
                if fn%((p**24)*(q**2)) == 0:
                    ans1 += 1
                for r in prime:
                    if p != r and q != r:
                        if fn%((p**4)*(q**4)*(r**2)) == 0:
                            ans2 += 1
print(ans1+int(ans2/2))
                    

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ll long long int
const int INF = 2147483647;
const ll MOD = 1000000007;

using namespace std;

int main() {
  int n, t;
  cin >> n >> t;
  vector<int> a(n), cum(n + 1);
  cum[0] = 0;
  REP(i, n) { cin >> a[i]; }

  cum[n] = 0;
  for (int i = n - 1; i >= 0; i--) {
    cum[i] = max(cum[i + 1], a[i]);
  }

  int m = 0;
  REP(i, n) { m = max(m, cum[i + 1] - a[i]); }
  int ans = 0;
  REP(i, n) {
    if (m == cum[i + 1] - a[i])
      ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, a) for (int i = (int)0; i < (int)a; ++i)
#define rrep(i, a) for (int i = (int)a - 1; i >= 0; --i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define RREP(i, a, b) for (int i = (int)a - 1; i >= b; --i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using ll = long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;

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

ll gcd(ll n, ll m)
{
	ll tmp;
	while (m != 0)
	{
		tmp = n % m;
		n = m;
		m = tmp;
	}
	return n;
}

ll lcm(ll n, ll m)
{
	return abs(n) / gcd(n, m) * abs(m); //gl=xy
}

using namespace std;

void solve()
{
  int t;
  cin>>t;
  while(t--){
    ll a,b,c,d;
    cin>>a>>b>>c>>d;
    if(a<b){
      cout<<"No\n";
    }
    else if(b>d){
      cout<<"No\n";
    }
    else if(c+1>=b){
      cout<<"Yes\n";
    }
    else {
      ll g=gcd(b,d);
      ll x=a+g*((b-a-1)/g);
      while(x>=b){
        x-=g;
      }
      if(x>c){
        cout<<"No\n";
      }
      else{
        cout<<"Yes\n";
      }
    }
  }
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}


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

using namespace std;

using lint = long long;
using ldouble = long double;

bool solve() {
    vector<pair<int, int>> cakes;
    int n;
    {
        int w, h;
        cin >> n >> w >> h;
        if (w == 0) return false;
        cakes.emplace_back(w, h);
    }

    for (int i = 0; i < n; ++i) {
        int id, s;
        cin >> id >> s;
        --id;

        int w, h;
        tie(w, h) = cakes[id];
        cakes.erase(cakes.begin() + id);

        s %= w + h;
        if (s < w) {
            if (s > w - s) s = w - s;
            cakes.emplace_back(s, h);
            cakes.emplace_back(w - s, h);
        } else {
            s -= w;
            if (s > h - s) s = h - s;
            cakes.emplace_back(w, s);
            cakes.emplace_back(w, h - s);
        }
    }

    sort(cakes.begin(), cakes.end(), [](auto p, auto q) {
        return p.first * p.second < q.first * q.second;
    });

    for (int i = 0; i < cakes.size(); ++i) {
        cout << cakes[i].first * cakes[i].second << " \n"[i + 1 == cakes.size()];
    }
    return true;
}

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



Measured memory_bytes: 3004
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


struct Precision{
  Precision(){
    cout<<fixed<<setprecision(12);
  }
}precision_beet;

//INSERT ABOVE HERE
signed main(){
  Int n,k;
  cin>>n>>k;
  vector<Int> ps(n);
  for(Int i=0;i<n;i++) cin>>ps[i];

  vector<Int> sm(n+1,0);
  for(Int i=0;i<n;i++) sm[i+1]=sm[i]+ps[i]+1;

  Int ans=0;
  for(Int i=0;i+k<=n;i++)
    chmax(ans,sm[i+k]-sm[i]);

  cout<<double(ans)/2<<endl;
  return 0;
}


Measured memory_bytes: 3328
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

class UnionFind {
public:
	vector<int> par;
	
	UnionFind() {}
	UnionFind(int n) {
		par.resize(n);
		for (int i = 0; i < n; i++) par[i] = i;
	}
	
	int root(int a) {
		if (par[a] == a)return a;
		else return par[a] = root(par[a]);
	}

	void unite(int a, int b) {
		int x = root(a);
		int y = root(b);
		if (x == y)return;
		par[x] = y;
	}

	bool same(int a, int b) {
		return root(a) == root(b);
	}

};

int main() {
	int n, q,com,x,y;
	cin >> n >> q;
	UnionFind UF(n);
	while (q--) {
		cin >> com >> x >> y;
		if (!com)UF.unite(x, y);
		if (com)cout << UF.same(x, y) << endl;
	}
}

Measured memory_bytes: 3192
#include <iostream>
#include <vector>
#include <algorithm>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> s(n);
    FOR(i, 0, n){
        cin >> s[i];
    }
    
    int q;
    cin >> q;
    vector<int> t(q);
    int cnt=0;
    FOR(i, 0, q){
        cin >> t[i];
        if (binary_search(s.begin(), s.end(), t[i])) {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}



Measured memory_bytes: 3272
#include <iostream>
#include <string>

using namespace std;

int main()
{
    string s;
    cin >> s;
    int g = 0;
    char prev = ' ';
    for (int i = 0; i < s.size(); ++i) {
        if (s[i] != prev) {
            ++g;
        }
        prev = s[i];
    }
    cout << g-1 << endl;
    return 0;
}

Measured memory_bytes: 512
<?php
// D 解説の解放で
fscanf(STDIN, '%d', $k);
$q = new SplQueue();
for ($i = 1; $i <= 9; $i++) {
    $q->enqueue($i);
}
$cnt = 1;
while (true) {
    $cur = $q->dequeue();
    if ($cnt === $k) break;
    $btm = $cur % 10;
    if ($btm !== 0) $q->enqueue($cur * 10 + $btm - 1);
    $q->enqueue($cur * 10 + $btm);
    if ($btm !== 9) $q->enqueue($cur * 10 + $btm + 1);
    $cnt++;
}
echo $cur;

Measured memory_bytes: 10744
#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define  For(i,a,b) for(int i=a,i##E=b;i<=i##E;++i)
#define rFor(i,a,b) for(int i=a,i##E=b;i>=i##E;--i)
typedef long long LL;
using namespace std;
const int N=200010;
const int inf=0x3f3f3f3f;
template<typename T>inline bool chkmin(T &a,const T &b){return a>b?a=b,1:0;}
template<typename T>inline bool chkmax(T &a,const T &b){return a<b?a=b,1:0;}
template<typename T>inline void read(T &x)
{
	x=0;int _f(0);char ch=getchar();
	while(!isdigit(ch))_f|=(ch=='-'),ch=getchar();
	while( isdigit(ch))x=x*10+ch-'0',ch=getchar();
	x=_f?-x:x;
}
inline void file()
{
#ifdef ztzshiwo
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
}
int n,Min[1<<26],x[N];
char s[N];
int main()
{
	file();
	mem(Min,inf);
	scanf("%s",s+1);
	n=strlen(s+1);
	Min[0]=0;
	For(i,1,n)
	{
		x[i]=x[i-1]^(1<<(s[i]-'a'));
		int ret=Min[x[i]];
		For(j,0,25)chkmin(ret,Min[x[i]^(1<<j)]);
		chkmin(Min[x[i]],ret+1);
	}
	printf("%d\n",Min[x[n]]==0?1:Min[x[n]]);
	return 0;
}


Measured memory_bytes: 263424
# -*- coding: utf-8 -*-
import sys
input = sys.stdin.readline

a,b = list(map(int,input().split()))
if a==0 and b==0:
    ret = 0
else:
    if a==0:
        a = 1

def bid_cnt(n):
    bid_list = [0 for i in range(40)]
    bid_list[0] = n//2+n%2
    i = 1
    two_i = 2**i
    while two_i <= n:
        if (n//two_i)%2==0:
            bid_list[i]==0
        else:
            bid_list[i] = (n//two_i)%2+(n%two_i)
        i+=1
        two_i = 2**i
    return bid_list

a_bid_cnt = bid_cnt(a-1)
b_bid_cnt = bid_cnt(b)
ab_bid_cnt_dif = [(i-j)%2 for i,j in zip(b_bid_cnt,a_bid_cnt)]
print(sum([v*2**i for i,v in enumerate(ab_bid_cnt_dif)] ))

Measured memory_bytes: 3064
#include <iostream>
using namespace std;
int main(void){
    string s;
    cin>>s;
    int a=(s[0]-'0')*10+s[1]-'0';
    int b=(s[2]-'0')*10+s[3]-'0';
    bool yymm=false;
    bool mmyy=false;
    if(a<=12&&a!=0) mmyy=true;
    if(b<=12&&b!=0) yymm=true;
    if(mmyy&&yymm){
        cout<<"AMBIGUOUS"<<endl;
    }else if(mmyy){
        cout<<"MMYY"<<endl;
    }else if(yymm){
        cout<<"YYMM"<<endl;
    }else{
        cout<<"NA"<<endl;
    }
}


Measured memory_bytes: 3600
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
#define ll long long
#define IO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
const int N = 1e2 + 5, M = 3e5 + 5;

int a[N];
int b[N];

int main(){
    int n;
    scanf("%d", &n);
    for(int i = 1 ; i < n ; ++i)
        scanf("%d", b + i), a[i] = b[i];
    a[n] = a[n - 1];
    for(int i = 2 ; i <= n ; ++i)
        a[i] = min(a[i], b[i - 1]);
    int ans = 0;
    for(int i = 1 ; i <= n ; ++i)
        ans += a[i];
    printf("%d\n", ans);
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector> 
#include<limits>
#include<numeric>
#include<type_traits>
#include<math.h>
#include<fstream>
#include<set>
using namespace std;
typedef long long ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define out(str) cout << str << endl
#define ALL(a) (a).begin(),(a).end()
#define INF (1<<29)

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; }

int N,Q,a,b,p,x;
bool visited[200010];
vector<int> G[200010];
int ans[200010],c[200010];


void dfs(int cost,int now){
    visited[now]=true;
    cost+=c[now];
    ans[now]=cost;
    for(int to:G[now]){
        if(!visited[to])dfs(cost,to);
    }
    return;
}

int main(){
    // ifstream in("input.txt");
    // cin.rdbuf(in.rdbuf());
    cin>>N>>Q;
    rep(i,N){
        ans[i]=0;
        c[i]=0;
        visited[i]=false;
    }
    rep(i,N-1){
        cin>>a>>b;
        a--;
        b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    rep(i,Q){
        cin>>p>>x;
        p--;
        c[p]+=x;
    }
    dfs(0,0);
    rep(i,N){
        cout<<ans[i]<<" ";
    }
    cout<<endl;



    

}


Measured memory_bytes: 21376
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>
#include<math.h>
struct Point {
  double x;
  double y;
};
struct Point *p;
double **dist;
double btsp(int size);
int main(void)
{
  int i, n;
  scanf("%d", &n);
  p = (struct Point*)malloc(sizeof(struct Point) * n);
  dist = (double**)malloc(sizeof(double*) * n);
  for (i = 0; i < n; i++) {
    dist[i] = (double*)malloc(sizeof(double) * n);
    scanf("%lf%lf", &p[i].x, &p[i].y);
  }
  printf("%f\n", btsp(n));
  for (i = 0; i < n; i++) free(dist[i]);
  free(dist);
  free(p);
}
double btsp(int size)
{
  int i, j, k;
  double t, ans;
  for (j = 0; j < size; j++) {
    for (i = 0; i < j; i++) {
      if (i == 0 && j == 1) dist[i][j] = hypot(p[i].x - p[j].x, p[i].y - p[j].y);
      else if (i < j - 1) dist[i][j] = dist[i][j-1] +  hypot(p[j-1].x - p[j].x, p[j-1].y - p[j].y);
      else {
        dist[i][j] = INT_MAX;
        for (k = 0; k < i; k++){
          t = dist[k][i] +  hypot(p[k].x - p[j].x, p[k].y - p[j].y);
          if (t < dist[i][j]) dist[i][j] = t;
        }
      }
    }
  }
  ans = INT_MAX;
  for (i = size - 2; i >= 0; i--) {
    t = dist[i][size-1] +  hypot(p[i].x - p[size-1].x, p[i].y - p[size-1].y);
    if (t < ans) ans = t;
  }
  return ans;
}


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

using namespace std;

int main () {
	int A, B, C;
	int K;
	cin >> A >> B >> C >> K;
	int ans = 0;
	if (A >= B && A >= C) {
		ans += B+C;
		ans += A * pow(2,K);
	} else if (B >= C && B >= A) {
		ans += C+A;
		ans += B * pow(2,K);
	} else if (C >= A && C >= B) {
		ans += A+B;
		ans += C * pow(2,K);
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
int date[8][4]={
	{2,1,4,4},
	{3,0,2,5},
	{3,1,3,6},
	{2,2,7,7},
	{2,0,5,5},
	{3,1,4,6},
	{3,2,5,7},
	{2,3,6,6}
};
int main(){
	map<string,int>time;
	queue<string>name;
	time["01234567"]=0;
	name.push("01234567");
	string str,STR;
	while(name.empty()==0){
		str=name.front();
		int pos=0;
		for(int i=0;i<str.size();i++)if(str[i]=='0')pos=i;
		for(int i=1;i<=date[pos][0];i++){
			STR=str;
			swap(STR[pos],STR[date[pos][i]]);
			if(time[STR]==0&&STR!="01234567"){
				time[STR]=time[str]+1;
				name.push(STR);
			}
		}
		name.pop();
	}
	while(getline(cin,STR)){
		str="";
		for(int i=0;i<STR.size();i+=2)str+=STR[i];
		cout<<time[str]<<endl;
	}
	
	return 0;
}


Measured memory_bytes: 3428
#include<bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define ri(x) scanf("%d",&(x))
#define ri2(x,y) scanf("%d %d",&(x),&(y))
#define ri3(x,y,z) scanf("%d %d %d",&(x),&(y),&(z))
#define rll(x) scanf("%lld",&(x))
#define rll2(x,y) scanf("%lld %lld",&(x),&(y))
#define rll3(x,y,z) scanf("%lld %lld %lld",&(x),&(y),&(z))
#define gc(x) ((x) = getchar())
using namespace::std;

const long double PI = acos(-1);
const long long MOD = 1000000000 +7;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> tll;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<pll> vpll;
typedef vector<tll> vtll;
typedef vector<string> vs;
typedef set<int> si;
typedef set<ii> sii;
typedef set<iii> siii;

ll gcd(ll a, ll b){ return b==0?a:gcd(b,a%b);}

ll add(ll a, ll b, ll m = MOD){
	if(a >= m) a %= m;
	if(b >= m) b %= m;
	if(a < 0) a += m;
	if(b < 0) b += m;
	ll res = a+b;
	if(res >= m or res <= -m) res %= m;
	if(res < 0) res += m;
	return res;
}

ll mul(ll a, ll b, ll m = MOD){
	if(a >= m) a %= m;
	if(b >= m) b %= m;
	if(a < 0) a += m;
	if(b < 0) b += m;
	ll res = a*b;
	if(res >= m or res <= -m) res %= m;
	if(res < 0) res += m;
	return res;
}

ll pow_mod(ll a, ll b, ll m = MOD){
	ll res = 1LL;
	a = a%m;
	while(b){
		if(b&1) res = mul(res,a,m);
		b >>= 1;
		a = mul(a,a,m);
	}
	return res;
}

ll fastexp(ll a, ll b){
	ll res = 1LL;
	while(b){
		if(b&1) res = res*a;
		b >>= 1;
		a *= a;
	}
	return res;
}

int gcdExtendido(int a, int b, int *x, int *y){
	if(a == 0){
		*x = 0;
		*y = 1;
		return b;
	}
	int x1, y1;
	int gcd = gcdExtendido(b%a,a,&x1,&y1);
	
	*x = y1-(b/a)*x1;
	*y = x1;
	return gcd;
}

int modInverso(int a, int m){
	int x, y;
	int g = gcdExtendido(a,m,&x,&y);
	if(g!=1) return -1;
	else return (x%m + m)%m;
}

/****************************************
*************P*L*A*N*T*I*L*L*A************
*****************************************/

const int N = 5000+5;

int n;
int k;
int c[N];
int p[N];
ll prefix[N];
ll maxpre[N];

ll solve(int pos){
	int x = pos;
	int len = 0;
	do{
		x = p[x];
		len++;
		prefix[len] = prefix[len - 1] + c[x];
	}while(x != pos);
	for(int i = 1; i <= len; i++){
		maxpre[i] = prefix[i];
		if(i > 1) maxpre[i] = max(maxpre[i], maxpre[i - 1]);
	}
	ll res = 0LL;
	if(k >= len){
		res = maxpre[len];
		if(prefix[len] >= 0){
			for(int r = 0; r <= len; r++){
				res = max(res, prefix[len] * ((k - r) / len) + maxpre[r]);
			}
		}
	}
	else{
		res = maxpre[k];
	}
	return res;
}

int main(){
	ri2(n, k);
	for(int i = 1; i <= n; i++) ri(p[i]);
	for(int i = 1; i <= n; i++) ri(c[i]);
	ll ans = LLONG_MIN;
	for(int i = 1; i <= n; i++){
		ans = max(ans, solve(i));
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 3948
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INF INT_MAX // 2147483647
#define INFLL LLONG_MAX // 9223372036854775807
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define per(i, n) for(ll i=((ll)(n))-1; i>=0; i--)
#define perf(i, n) for(ll i=((ll)(n)); i>0; i--)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
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; }
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);
    ll n, k;
    cin >> n >> k;
    vi a(n+1, 0);
    vi loop(0);
    repf(i, n) cin >> a[i];


    vector<bool> chk(n+1, true);
    loop.push_back(1);
    chk[1] = false;
    ll next = a[1];
    ll loop_cnt = 1;

    if(k<100000000){
        rep(i, k-1) next = a[next];
        cout << next << endl;
        return 0;
    }

    while(chk[next]){
        loop.push_back(next);
        chk[next] = false;
        next = a[next];
        loop_cnt++;
        if(loop_cnt > k) break;
    }

    // ループを抜けた時のnextがループの始点
    auto p = find(all(loop), next);
    ll nonloop = p - loop.begin();
    ll loopsize = loop.size() - nonloop;
    if(k<=nonloop){
        cout << loop[k] << endl;
    }
    else{
        k = (k - nonloop)%loopsize;
        cout << loop[nonloop+k] << endl;
    }
}

Measured memory_bytes: 6884
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		HashSet<Integer> set = new HashSet<>();
		for(int i=0; i<N; i++) {
			set.add(sc.nextInt());
		}

		System.out.println(set.size()==N ? "YES" : "NO");
		sc.close();
	}
}


Measured memory_bytes: 102544
#include<stdio.h>
#include<math.h>

struct Point{ double x,y; };

void koch(int n, Point a, Point b){
	if(n == 0)return;
	Point s, t, u;
	double th = M_PI * 60.0 / 180.0;
	
	s.x = (2.0 * a.x + 1.0 * b.x) / 3.0;
	s.y = (2.0 * a.y + 1.0 * b.y) / 3.0;
	t.x = (1.0 * a.x + 2.0 * b.x) / 3.0;
	t.y = (1.0 * a.y + 2.0 * b.y) / 3.0;
	u.x = (t.x - s.x) * cos(th) - (t.y - s.y) * sin(th) + s.x;
	u.y = (t.x - s.x) * sin(th) + (t.y - s.y) * cos(th) + s.y;
	
	koch(n-1, a, s);
	printf("%.8f %.8f\n", s.x, s.y);
	koch(n-1, s, u);
	printf("%.8f %.8f\n", u.x, u.y);
	koch(n-1, u, t);
	printf("%.8f %.8f\n", t.x, t.y);
	koch(n-1, t, b);
}
int main(){
	Point a,b;
	int n;
	
	scanf("%d",&n);
	
	a.x=0;
	a.y=0;
	b.x=100;
	b.y=0;
	
	printf("%.8f %.8f\n", a.x, a.y);
	koch(n, a, b);
	printf("%.8f %.8f\n", b.x, b.y);
	
	return 0;
}


Measured memory_bytes: 2672
#include <iostream>
#include <vector>
#include <queue>
#include <sstream>
#include <algorithm>
#include <bitset>
#include <limits>
#include <map>
#include <cmath>
#include <set>

using namespace std;

int group(int n)
{
    if (n == 2) return 1;
    else if (n == 4 || n == 6 || n == 9 || n == 11) return 2;
    else return 3;
}

int main()
{
    int a, b;
    cin >> a >> b;
    if (group(a) == group(b))
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author yosiiii
 */


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

class PIndependentSet {
public:
    int n;
    vector<vector<int>> ab;
    ll mod=1e9+7;
    vector<vector<ll>> dp;
    vector<bool> f;
	void solve(std::istream& in, std::ostream& out) {
        in >> n;
        ab=vector<vector<int>>(n);
        dp=vector<vector<ll>>(n,vector<ll>(2,1));
        f=vector<bool>(n,true);
        rep(i,n-1){
            int a,b;
            in >> a >> b;
            a--;
            b--;
            ab[a].push_back(b);
            ab[b].push_back(a);
        }
        f[0]=false;
        dfs(0);
        out << (dp[0][0]+dp[0][1])%mod << endl;
	}
	void dfs(int node){
	    vector<int> nx;
	    for(int i=0;i<ab[node].size();i++) {
            if (f[ab[node][i]]) {
                f[ab[node][i]]=false;
                nx.push_back(ab[node][i]);
                dfs(ab[node][i]);
            }
        }
	    if(nx.size()==0){
	        dp[node][0]=1;
	        dp[node][1]=1;
	    }else{
	        rep(i,nx.size()){
	            dp[node][0]*=(dp[nx[i]][0]+dp[nx[i]][1])%mod;
	            dp[node][1]*=(dp[nx[i]][0])%mod;
	            dp[node][0]%=mod;
	            dp[node][1]%=mod;
	        }
	    }
	}
};


int main() {
	PIndependentSet solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


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

int main() {
	long long N;
	cin >> N;
	long long factor=1;
	long long A;
	long long B;
	for (long long i=1; i*i<=N; i++){
		if (N%i==0){
			if (i>factor) factor=i;	
		}
	}
	A=factor;
	B=N/factor;
	string ss1 = to_string(A);
	string ss2 = to_string(B);
	int len = ss1.length()>ss2.length()? ss1.length():ss2.length();
	cout << len<< '\n';
	
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
    public static void main(String args[])
    {
        Scanner sc=new Scanner(System.in);     
        String s1=sc.next();
        long size=s1.length();
        String ans="";
        for(long i=0;i<size;i++)
        {
        	ans+="x";
        	
        	
        }
        		System.out.println(ans);
       



        }
    
}

Measured memory_bytes: 22868
#include <iostream>
#include <algorithm>
#include <set>
#include <list>

using namespace std;

const int MAX = 1e5 + 9;
const long long INF = 1e18 + 9;

bool cmp(const pair<long long, int> &a, const pair<long long, int> &b) {
	return a.first > b.first;
}

pair<long long, int> a[MAX];
int kind[MAX];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> a[i].second >> a[i].first;
	}
	sort(a, a + n, cmp);
	/*
	for (int i = 0; i < n; i++) {
		auto sushi = a[i];
		cerr << sushi.first << ' ' << sushi.second << '\n';
	}
	cerr << '\n';
	*/
	multiset<pair<long long, int>> s;
	list<pair<long, long>> b;
	int cnt = 0;
	long long sum = 0;
	for (int i = 0; i < k; i++) {
		if (!kind[a[i].second]) {
			cnt++;
			s.insert(make_pair(INF, a[i].second));
		} else {
			s.insert(a[i]);
		}
		kind[a[i].second]++;
		sum += a[i].first * 1LL;
	}
	for (int i = k; i < n; i++) {
		b.push_back(make_pair(a[i].first, a[i].second));
	}
//	cerr << cnt << ' ' << sum << '\n';
	long long ret = cnt * cnt * 1LL + sum * 1LL;
	while (!b.empty() && (*s.begin()).first != INF) {
		if (!kind[(*b.begin()).second]) {
			sum -= (*s.begin()).first * 1LL;
			sum += (*b.begin()).first * 1LL;
			kind[(*s.begin()).second]--;
			kind[(*b.begin()).second]++;
			s.erase(s.begin());
			cnt++;
			s.insert(make_pair(INF, (*b.begin()).second));
			ret = max(ret, cnt * cnt * 1LL + sum * 1LL) * 1LL;
			/*
			for (auto sushi : s) {
				cerr << sushi.first << ' ' << sushi.second << '\n';
			}
			cerr << '\n';
			*/
		}
		b.pop_front();
	}
	//cerr << cnt << ' ' << sum << '\n';
	cout << ret << '\n';
	
	return 0;
}


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

int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}

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

  int l[N];
  int i;
  for(i = 0; i < N; i++)
    cin >> l[i];
  
  std::qsort(l,N,4,compare_int);

  int j, k, m;
  int sum;
  int count = 0;
  for(j = N-1; j > 1 ; j--)
    {
      
      for(k = j-1; k > 0 ; k--)
	{
	  if(l[j]>2*l[k])
	    break;
	  
	  for(m = k-1; m > -1; m--)
	    {
	      sum = l[k] + l[m];

	      if(l[j] < sum && sum <= 2*l[j])
		{
		  count++;
		}

	    }
	}
    }
  cout << count << endl;

  return 0;
}
      


Measured memory_bytes: 256